優化部分字典鍵匹配

Question

我有一個使用4元組的字典，因爲它是關鍵。我需要找到字典中與其他元組部分匹配的所有密鑰。我有一些這樣做的代碼，但它很慢，需要優化。

這裏是我後：

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)] 

當前代碼：

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 

• 關鍵詞是包含我想匹配
• self.chain的值的列表是字典
• self.order是元組的大小
• LEN（關鍵字）總是= LEN（K）
• 「無」被認爲是外卡
• 本字典是相當巨大的（這種方法正在〜800ms的運行，並約300MB），因此空間也是考慮

我基本上尋找這種方法的優化，或更好的方式來存儲這些數據。

Answer 1

怎麼樣只使用一個數據庫？

即使對於簡單的項目，我也更喜歡SQLite + SQLAlchemy，但普通的sqlite3可能會有一個溫和的學習曲線。

在每個關鍵列上添加索引應該注意速度問題。

Answer 2

也許你可以通過維護你的密鑰索引來加速它。從本質上講，是這樣的：

self.indices[2][5] 

將包含所有在關鍵的第三個位置有5鍵的一個set。

然後，你可以簡單地做相關的索引條目之間的交集來獲得密鑰的集合：

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對琥珀的回答是：

>>> 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

如果您將數據存儲在普通字典中，則無法進一步優化，因爲它無法提供更快的速度，因此無法以不可預知的順序順序訪問字典中的所有元素。這意味着您的解決方案不會更快，然後O(n)。

現在，數據庫。數據庫不是任何（複雜的）問題的通用解決方案。您能否可靠地估計數據庫的這種查找的速度/複雜性？如果您滾動到本答覆的底部，您將看到，對於大型數據集，數據庫性能可能比智能數據結構差得多。

這裏您需要的是手工製作的數據結構。有很多選擇，它強烈依賴於你對這些數據做的其他事情。例如：你可以保持N套鑰匙的分類列表，每個由n個元組元素排序。然後你就可以快速選擇N有序集合在n位置匹配只有一個元組元素的元素，並找到它們的交集得到的結果。這會給出O(log n)*O(m)的平均性能，其中m是一個子集中元素的平均數量。

或者你可以保存在一個K-d樹項目，這意味着你要付出O(log n)插入價格，但你可以在O(log n)時間做查詢，如在一個以上。這裏是一個Python例如，使用K-d樹實現從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) 

並試運行結果：

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

只是爲了好玩，還增加了基於數據庫的解決方案基準。初始化代碼改變從上方到：

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

現在，「數據庫」的實現：

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) 

和測試結果，減少了100次每基準（對於所得657720-元件組鍵） ：

$ 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 

還值得一提的是，建築樹花了將近兩倍的時間更少，然後插入該組測試數據到數據庫中。

完整源在這裏：https://gist.github.com/1261449