python - 用部分关键字搜索python dict的最快方法

Question

确定 dict 是否包含以特定字符串开头的键的最快方法是什么？我们能比线性做得更好吗？当我们只知道一个键的开始时，我们如何实现 O(1) 操作？

这是当前的解决方案：

for key in dict.keys():
    if key.start_with(str):
        return True
return False

Answer 1

不预处理字典，O(n)是你能做的最好的。不过，它不必很复杂：

any(key.startswith(mystr) for key in mydict)

（不要使用dictandstr作为变量名，那些已经是两个内置函数的名字了。）

如果您可以预处理字典，请考虑将键放在前缀树（又名trie）中。维基百科文章中甚至还有一个Python 实现。

Answer 2

您可以将插入键的所有前缀放入字典，因此对于键，foo您将插入f,fo和foo. 您将进行 O(1) 查找，但您会花时间进行预处理（O(k)，其中 k 是密钥长度），并浪费大量内存：

def insert_with_prefixes(key, value, dict_):
  prefixes = (key[:i+1] for i in xrange(len(key)))
  dict_.update((prefix, value) for prefix in prefixes)

对于日常使用，我会（并且我会）使用arshajii回答中的方法。当然，请记住短前缀可能会发生许多冲突（这里：）"h"：

>>> a = {}
>>> insert_with_prefixes('hello', 'world', a)
>>> insert_with_prefixes('homo', 'sapiens', a)
>>> a
{'h': 'sapiens', 'hom': 'sapiens', 'homo': 'sapiens', 'ho': 'sapiens', 
 'hel': 'world', 'hell': 'world', 'hello': 'world', 'he': 'world'}