优化部分字典键匹配
我有一个字典，它的键是由四个值组成的元组。我需要找出字典中与另一个元组部分匹配的所有键。我有一些代码可以做到这一点，但运行得很慢，需要优化。
我想要的结果是：
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
- keyWords 是一个列表，里面包含我想要匹配的值
- self.chain 是那个字典
- self.order 是元组的大小
- len(keyWords) 总是等于 len(k)
- ‘None’ 被视为通配符
- 这个字典非常大（这个方法运行大约需要 800 毫秒，内存占用大约 300MB），所以空间也是一个考虑因素
我基本上在寻找这个方法的优化方案，或者更好的存储这些数据的方法。
4 个回答
也许你可以通过为你的键维护索引来加快速度。简单来说，就是像这样：
self.indices[2][5]
这个会包含一个set，里面有所有在键的第三个位置上是5的键。
然后你只需要对相关的索引条目进行集合交集操作，就能得到这些键的集合：
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 []
如果你把数据存储在普通的字典里，就无法进一步优化，因为字典的访问速度并没有比顺序访问所有元素快，顺序访问的顺序也不固定。这意味着你的解决方案的速度不会比 O(n) 更快。
接下来谈谈数据库。数据库并不是解决所有（复杂）问题的万能工具。你能准确估计数据库查找的速度和复杂度吗？如果你往下滚动到这个回复的底部，你会发现对于大数据集，数据库的性能可能比一些聪明的数据结构要差得多。
在这种情况下，你需要的是一个手动设计的数据结构。选择有很多，具体取决于你对这些数据的其他操作。例如：你可以保持 N 组按 n 元组元素排序的列表。这样你可以快速选择 N 组只匹配一个元组元素在 n 位置的排序集合，然后找到它们的交集来得到结果。这种方法的平均性能是 O(log n)*O(m)，其中 m 是一个子集中的平均元素数量。
或者你可以把你的项目存储在一个 k-d 树中，这意味着插入的时间复杂度是 O(log n)，但你可以像上面那样在 O(log n) 的时间内进行查询。这里有一个使用 SciPy 中 k-d 树实现的 Python 示例：
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