Tối ưu hóa kết hợp khóa từ điển một phần

Question

Tôi có một từ điển sử dụng bộ 4 phần làm khóa. Tôi cần phải tìm tất cả các phím trong từ điển mà một phần phù hợp với một số bộ dữ liệu khác. Tôi có một số mã mà làm điều này nhưng nó chậm và cần tối ưu hóa.

Đây là những gì tôi sau:

Keys: 
(1, 2, 3, 4) 
(1, 3, 5, 2) 
(2, 4, 8, 7) 
(1, 4, 3, 4) 
Match: 
(1, None, 3, None) 
Result: 
[(1, 2, 3, 4), (1, 4, 3, 4)] 

đang hiện tại:

def GetTuples(self, keyWords): 
    tuples = [] 
    for k in self.chain.iterkeys(): 
     match = True 
     for i in range(self.order): 
      if keyWords[i] is not None and keyWords[i] != k[i]: 
       match = False 
       break 
     if match is True: 
      tuples.append(k) 
    return tuples 

• từ khóa là một danh sách có chứa các giá trị tôi muốn để phù hợp với
• self.chain là điển
• self.order là kích thước của bộ tẩu
• len (keyWords) luôn = len (k)
• 'Không' được coi là thẻ hoang dã
• Từ điển là khá lớn (phương pháp này đang chạy ~ 800ms để chạy và khoảng 300MB), vì vậy không gian cũng là xem xét

Về cơ bản, tôi đang tìm kiếm tối ưu hóa cho phương pháp này hoặc cách lưu trữ dữ liệu này tốt hơn.

Answer 1

gì về chỉ sử dụng một cơ sở dữ liệu?

Tôi thích SQLite + SQLAlchemy ngay cả đối với các dự án đơn giản, nhưng đồng bằng sqlite3 có thể có đường cong học tập nhẹ nhàng hơn.

Đặt chỉ mục trên mỗi cột khóa sẽ giải quyết vấn đề về tốc độ.

Answer 2

Có lẽ bạn có thể tăng tốc nó bằng cách duy trì các chỉ mục cho khóa của bạn. Về cơ bản, một cái gì đó như thế này:

self.indices[2][5] 

sẽ chứa một set của tất cả các phím có 5 ở vị trí thứ ba của khóa.

Sau đó, bạn chỉ có thể làm bộ giao nhau giữa các mục chỉ số có liên quan để có được những bộ chìa khóa:

matching_keys = None 

for i in range(self.order): 
    if keyWords[i] is not None: 
     if matching_keys is None: 
      matching_keys = self.indices[i][keyWords[i]] 
     else: 
      matching_keys &= self.indices[i][keyWords[i]] 

matching_keys = list(matching_keys) if matching_keys else [] 

Answer 3

riffing về câu trả lời của Amber:

>>> from collections import defaultdict 
>>> index = defaultdict(lambda:defaultdict(set)) 
>>> keys = [(1, 2, 3, 4), 
...   (1, 3, 5, 2), 
...   (2, 4, 8, 7), 
...   (1, 4, 3, 4), 
...   ] 
>>> for key in keys: 
...  for i, val in enumerate(key): 
...   index[i][val].add(key) 
... 
>>> def match(goal): 
...  res = [] 
...  for i, val in enumerate(goal): 
...   if val is not None: 
...    res.append(index[i][val]) 
...  return reduce(set.intersection, res) 
... 
>>> match((1, None, 3, None)) 
set([(1, 4, 3, 4), (1, 2, 3, 4)]) 

Answer 4

Bạn không thể tối ưu hóa thêm nếu bạn lưu trữ dữ liệu bằng một từ điển đơn giản vì nó không cung cấp gì nhanh hơn, sau đó truy cập tuần tự tới tất cả các phần tử trong từ điển của bạn theo một số thứ tự không thể đoán trước. Điều này có nghĩa là giải pháp của bạn không nhanh hơn O(n).

Hiện tại, cơ sở dữ liệu. Cơ sở dữ liệu không phải là một giải pháp phổ quát cho bất kỳ vấn đề (phức tạp đủ). Bạn có thể ước tính đáng tin cậy về tốc độ/độ phức tạp của các tra cứu như vậy đối với một cơ sở dữ liệu không? Nếu bạn cuộn xuống cuối câu trả lời này, bạn sẽ thấy rằng đối với bộ dữ liệu lớn, hiệu suất cơ sở dữ liệu có thể tồi tệ hơn nhiều so với cấu trúc dữ liệu thông minh.

Điều bạn cần ở đây là cấu trúc dữ liệu thủ công. Có một số lựa chọn, nó phụ thuộc rất nhiều vào những thứ khác mà bạn đang làm với dữ liệu này.Ví dụ: bạn có thể giữ N bộ danh sách được sắp xếp của các khóa của mình, mỗi danh sách được sắp xếp theo yếu tố tuple n. Sau đó, bạn có thể nhanh chóng chọn N các bộ phần tử được sắp xếp phù hợp với chỉ một phần tử tuple ở vị trí n và tìm giao điểm của chúng để nhận kết quả. Điều này sẽ cho hiệu suất trung bình là O(log n)*O(m) trong đó m là số phần tử trung bình trong một tập hợp con.

Hoặc bạn có thể lưu trữ các mục của bạn trong cây k-d, điều này có nghĩa là bạn phải trả O(log n) giá chèn, nhưng bạn có thể thực hiện các truy vấn như số trên trong thời gian O(log n). Dưới đây là một ví dụ trong python, sử dụng k-d thực hiện cây từ scipy:

from scipy.spatial import kdtree 
import itertools 
import random 

random.seed(1) 
data = list(itertools.permutations(range(10), 4)) 
random.shuffle(data) 
data = data[:(len(data)/2)] 

tree = kdtree.KDTree(data) 

def match(a, b): 
    assert len(a) == len(b) 
    for i, v in enumerate(a): 
     if v != b[i] and (v is not None) and (b[i] is not None): 
      return False 
    return True 

def find_like(kdtree, needle): 
    assert len(needle) == kdtree.m 
    def do_find(tree, needle): 
     if hasattr(tree, 'idx'): 
      return list(itertools.ifilter(lambda x: match(needle, x), 
              kdtree.data[tree.idx])) 
     if needle[tree.split_dim] is None: 
      return do_find(tree.less, needle) + do_find(tree.greater, needle) 
     if needle[tree.split_dim] <= tree.split: 
      return do_find(tree.less, needle) 
     else: 
      return do_find(tree.greater, needle) 
    return do_find(kdtree.tree, needle) 

def find_like_bf(kdtree, needle): 
    assert len(needle) == kdtree.m 
    return list(itertools.ifilter(lambda x: match(needle, x), 
            kdtree.data)) 

import timeit 
print "k-d tree:" 
print "%.2f sec" % timeit.timeit("find_like(tree, (1, None, 2, None))", 
           "from __main__ import find_like, tree", 
           number=1000) 
print "brute force:" 
print "%.2f sec" % timeit.timeit("find_like_bf(tree, (1, None, 2, None))", 
           "from __main__ import find_like_bf, tree", 
           number=1000) 

Và chạy thử nghiệm kết quả:

$ python lookup.py 
k-d tree: 
0.89 sec 
brute force: 
6.92 sec 

Chỉ cần cho vui, cũng nói thêm cơ sở dữ liệu dựa trên giải pháp benchmark. Mã khởi tạo thay đổi từ trên xuống:

random.seed(1) 
data = list(itertools.permutations(range(30), 4)) 
random.shuffle(data) 

Bây giờ, các "cơ sở dữ liệu" thực hiện:

import sqlite3 

db = sqlite3.connect(":memory:") 
db.execute("CREATE TABLE a (x1 INTEGER, x2 INTEGER, x3 INTEGER, x4 INTEGER)") 
db.execute("CREATE INDEX x1 ON a(x1)") 
db.execute("CREATE INDEX x2 ON a(x2)") 
db.execute("CREATE INDEX x3 ON a(x3)") 
db.execute("CREATE INDEX x4 ON a(x4)") 

db.executemany("INSERT INTO a VALUES (?, ?, ?, ?)", 
       [[int(x) for x in value] for value in tree.data]) 

def db_test(): 
    cur = db.cursor() 
    cur.execute("SELECT * FROM a WHERE x1=? AND x3=?", (1, 2)) 
    return cur.fetchall() 

print "sqlite db:" 
print "%.2f sec" % timeit.timeit("db_test()", 
           "from __main__ import db_test", 
           number=100) 

Và kiểm tra kết quả, giảm 100 chạy mỗi điểm chuẩn (đối với kết quả là 657.720 phần tử tập hợp các phím) :

$ python lookup.py 
building tree 
done in 6.97 sec 
building db 
done in 11.59 sec 
k-d tree: 
1.90 sec 
sqlite db: 
2.31 sec 

Điều đáng nói là cây xây dựng mất gần gấp đôi thời gian sau đó chèn dữ liệu thử nghiệm này vào cơ sở dữ liệu.

Toàn bộ nguồn tại đây: https://gist.github.com/1261449