在巨大的列表中查找/搜索的最有效方法(python)

Question

- 我刚刚解析了一个大文件,我创建了一个包含42.000个字符串/单词的列表.我想查询[反对此列表]以检查给定的单词/字符串是否属于它.所以我的问题是:

这种查找最有效的方法是什么？

第一种方法是对列表(list.sort())进行排序,然后使用

>> if word in list: print 'word'

这真是微不足道,我相信有更好的方法来做到这一点.我的目标是应用快速查找,查找给定字符串是否在此列表中.如果您对其他数据结构有任何想法,欢迎使用.然而,我想避免现在更复杂的数据结构,如Tries等.我有兴趣听到有关快速查找或任何其他python库方法的想法(或技巧)可能比简单更快地进行搜索in.

而且我想知道搜索项的索引

Answer 1

不要创建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)