词典键的搜索
词典键的搜索
提问于 2011-03-02 22:46:32
我想知道如何对python字典中的键执行某种索引。这本字典大约有几分。400,000项，所以我试图避免线性搜索。
基本上，我正在试图找出userinput是否在任何一个丁字键中。
for keys in dict:
if userinput in keys:
DoSomething()
break这将是我试图做的一个例子。有没有一种更直接的搜索方式，没有循环？或者什么是更有效的方法。
澄清：userinput并不是真正的密钥(如userinput可能是log，而关键是logfile )
编辑:任何列表/缓存创建，预处理或组织，可以在搜索之前完成是可以接受的。唯一需要快速的是寻找钥匙。
回答 5
Stack Overflow用户
发布于 2011-03-02 22:57:57
如果您只需要查找以前缀开头的键，则可以使用trie。存在更复杂的数据结构来查找键，其中任何地方都包含一个子字符串，但是它们占用了更多的存储空间，因此这是一种空时交换。
Stack Overflow用户
发布于 2011-03-03 00:12:44
如果您只需要查找以前缀开头的键，则可以使用二进制搜索。像这样的东西就能完成任务：
import bisect
words = sorted("""
a b c stack stacey stackoverflow stacked star stare x y z
""".split())
n = len(words)
print n, "words"
print words
print
tests = sorted("""
r s ss st sta stack star stare stop su t
""".split())
for test in tests:
i = bisect.bisect_left(words, test)
if words[i] < test: i += 1
print test, i
while i < n and words[i].startswith(test):
print i, words[i]
i += 1输出：
12 words
['a', 'b', 'c', 'stacey', 'stack', 'stacked', 'stackoverflow', 'star', 'stare',
'x', 'y', 'z']
r 3
s 3
3 stacey
4 stack
5 stacked
6 stackoverflow
7 star
8 stare
ss 3
st 3
3 stacey
4 stack
5 stacked
6 stackoverflow
7 star
8 stare
sta 3
3 stacey
4 stack
5 stacked
6 stackoverflow
7 star
8 stare
stack 4
4 stack
5 stacked
6 stackoverflow
star 7
7 star
8 stare
stare 8
8 stare
stop 9
su 9
t 9Stack Overflow用户
发布于 2011-03-03 15:06:16
您可以使用适当的分隔符将所有键连接到一个长字符串中，并使用字符串的find方法。太快了。
也许这段代码对你有帮助。search方法返回一个字典值列表，其键包含子字符串key。
class DictLookupBySubstr(object):
def __init__(self, dictionary, separator='\n'):
self.dic = dictionary
self.sep = separator
self.txt = separator.join(dictionary.keys())+separator
def search(self, key):
res = []
i = self.txt.find(key)
while i >= 0:
left = self.txt.rfind(self.sep, 0, i) + 1
right = self.txt.find(self.sep, i)
dic_key = self.txt[left:right]
res.append(self.dic[dic_key])
i = self.txt.find(key, right+1)
return res页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5174506
复制相关文章
相似问题
腾讯云开发者
