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

Question

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

这是目前的解决方案:

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

Answer 1

如果不对 dict 进行预处理，O(n) 是您能做的最好的。不过，它不必很复杂:

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

(不要使用dict 和str 作为变量名，它们已经是两个built-in functions 的名称。)

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