-- 我刚刚解析了一个大文件,并创建了一个包含 42.000 个字符串/单词的列表。我想查询[针对此列表]以检查给定的单词/字符串是否属于它。所以我的问题是:
这种查找最有效的方法是什么?
第一种方法是对列表进行排序(list.sort()
)然后只需使用
>> if word in list: print 'word'
这真的很微不足道,我确信有更好的方法来做到这一点。我的目标是应用快速查找来查找给定的字符串是否在此列表中。如果您对其他数据结构有任何想法,欢迎提出。然而,我现在想避免像 Tries 等更复杂的数据结构。我有兴趣听到有关快速查找或任何其他可能比简单搜索更快的 python 库方法的想法(或技巧)in
.
我还想知道搜索项的索引
不要创建一个list
, 创建一个set
。它以恒定的时间进行查找。
如果您不想要集合的内存开销,请保留一个排序列表并使用bisect http://docs.python.org/library/bisect.html module.
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)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)