-- 我刚刚解析了一个大文件,并创建了一个包含 42.000 个字符串/单词的列表。我想查询 [针对此列表] 以检查给定的单词/字符串是否属于它。所以我的问题是:
这种查找最有效的方法是什么?
第一种方法是对列表进行排序(list.sort()
),然后使用
>> if word in list: print 'word'
这真的是微不足道的,我相信有更好的方法来做到这一点。我的目标是应用快速查找来查找给定字符串是否在此列表中。如果您对其他数据结构有任何想法,欢迎提出。然而,我现在想避免使用更复杂的数据结构,比如 Tries 等。我有兴趣听到关于快速查找或任何其他 python 库方法的想法(或技巧),这些方法可能比简单的 in
。
我也想知道搜索项的索引
最佳答案
不要创建list
,创建set
。它在恒定时间内进行查找。
如果您不想要集合的内存开销,请保留一个排序列表并使用 bisect
搜索它。模块。
from bisect import bisect_left
def bi_contains(lst, item):
""" efficient `item in lst` for sorted lists """
# if item is larger than the last its not in the list, but the bisect would
# find `len(lst)` as the index to insert, so check that first. Else, if the
# item is in the list then it has to be at index bisect_left(lst, item)
return (item <= lst[-1]) and (lst[bisect_left(lst, item)] == item)
关于python - 在巨大列表中查找/搜索的最有效方法(python),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2701173/