优化部分字典键匹配

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