在Python中，针对大型列表进行查找/搜索的最有效方法是什么？

Question

-- 我刚刚解析了一个大文件，并创建了一个包含42,000个字符串/单词的列表。我想查询以检查给定的单词/字符串是否属于它。那么我的问题是：

对于这样的查找，最有效的方法是什么？

一种首要的方法是对列表进行排序（list.sort()），然后只需使用

>> if word in list: print 'word'

这个问题非常琐碎，我相信有更好的方法来解决。我的目标是应用一种快速查找方法，找出给定的字符串是否在这个列表中。如果您有其他数据结构的想法，欢迎分享。但是，我暂时想避免更复杂的数据结构，比如 Trie 等。我感兴趣的是听到关于快速查找或任何其他 Python 库方法的想法（或技巧），这些方法可能比简单的 in 更快地完成搜索。

同时，我还想知道搜索项的索引。

- user229269

---

如果您预计以后会进行复杂的查找 - 我指的是不是琐碎的 - 我建议您将其存储在 sqlite3 中。 - Jeffrey Jose

Answer 1

不要创建一个list，而是创建一个set。它可以在常数时间内进行查找。

如果你不想使用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)

- Jochen Ritzel

---

非常感谢THC4k提供的详细回复。实际上我本来想自己应用二分查找，但是看到bisect模块似乎已经包含了相似的功能，所以你节省了我的时间 :）。再次感谢你的帮助。 - user229269

@user229269，你理解错误了帖子的重点！你可能根本不需要一个list，而是需要一个set。 - Mike Graham

@Mike Graham，我知道你的意思，但是我担心如果我使用集合(set)，可能会遇到内存问题，因为我的列表实际上是一个快速增长的单词列表，最终可能会达到100,000个字符串甚至更多。 - user229269

@user229269，一百万个条目并不算很多。对于这么多的条目，使用set而不是list只会增加不到2MB的内存使用量，在现代硬件上这并不算太多。如果你的数据增长到了无法使用set导致内存问题的程度，那么你可能需要考虑使用完全不同的技术，比如将数据存储在数据库中。 - Mike Graham

是的，实际上你 (@Mike Graham) 是正确的 :) -- 我已经使用了集合。非常感谢你让我重新考虑它。 - user229269

很棒的方法！谢谢，将超过1M个实体的查找时间从大约3小时减少到了几秒钟！ :) - inverted_index

Answer 2

在集合与列表之间的一个问题尚未被考虑：在"解析大文件"时，人们希望需要处理重复的单词/字符串。你完全没有提到这一点。

显然，将新单词添加到集合中会即时移除重复项，而不会增加任何CPU时间或思考时间的成本。如果您尝试使用列表来实现，最终会导致O(N ** 2)的结果。如果将所有内容附加到列表中，并在最后删除重复项，则最聪明的方法是...鼓声...使用集合，而列表的（小）内存优势很可能会被重复项淹没。

- John Machin

Answer 3

使用这个程序看起来字典是最快的，集合是第二快的，带有bi_contains的列表是第三快的。

from datetime import datetime

def ReadWordList():
    """ Loop through each line in english.txt and add it to the list in uppercase.

    Returns:
    Returns array with all the words in english.txt.

    """
    l_words = []
    with open(r'c:\english.txt', 'r') as f_in:
        for line in f_in:
            line = line.strip().upper()
            l_words.append(line)

    return l_words

# Loop through each line in english.txt and add it to the l_words list in uppercase.
l_words = ReadWordList()
l_words = {key: None for key in l_words}
#l_words = set(l_words)
#l_words = tuple(l_words)

t1 = datetime.now()

for i in range(10000):
    #w = 'ZEBRA' in l_words
    w = bi_contains(l_words, 'ZEBRA')

t2 = datetime.now()
print('After: ' + str(t2 - t1))

# list = 41.025293 seconds
# dict = 0.001488 seconds
# set = 0.001499 seconds
# tuple = 38.975805 seconds
# list with bi_contains = 0.014000 seconds

- Superdooperhero

---

对字典的速度感到惊讶。下一个问题是生成“l_words”对象需要多长时间。+1！ - Cometsong