Python:如何有效地检查一个项目是否在列表中？

Question

我有一个字符串列表(类似单词)，在解析文本时，我需要检查一个单词是否属于我当前列表中的单词组。

但是，我的输入非常大(大约 6 亿行)，根据 Python 文档，检查元素是否属于列表是 O(n) 操作。

我的代码是这样的:

words_in_line = []
for word in line:
    if word in my_list:
        words_in_line.append(word)

因为这需要太多时间(实际上是几天)，所以我想改进占用大部分时间的部分。我查看了 Python 集合，更准确地说，查看了双端队列。但是，只给 O(1) 操作时间访问列表的头部和尾部，而不是在中间。

有人知道如何以更好的方式做到这一点吗？

Answer 1

您可能会考虑 trie或 DAWG或数据库。有几个相同的 Python 实现。

以下是您考虑集合与列表的一些相对时间:

import timeit
import random

with open('/usr/share/dict/words','r') as di:  # UNIX 250k unique word list 
    all_words_set={line.strip() for line in di}

all_words_list=list(all_words_set)    # slightly faster if this list is sorted...      

test_list=[random.choice(all_words_list) for i in range(10000)] 
test_set=set(test_list)

def set_f():
    count = 0
    for word in test_set:
        if word in all_words_set: 
           count+=1
    return count

def list_f():
    count = 0
    for word in test_list:
        if word in all_words_list: 
           count+=1
    return count

def mix_f():
    # use list for source, set for membership testing
    count = 0
    for word in test_list:
        if word in all_words_set: 
           count+=1
    return count    

print "list:", timeit.Timer(list_f).timeit(1),"secs"
print "set:", timeit.Timer(set_f).timeit(1),"secs" 
print "mixed:", timeit.Timer(mix_f).timeit(1),"secs" 

打印:

list: 47.4126560688 secs
set: 0.00277495384216 secs
mixed: 0.00166988372803 secs

即，将一组 10000 个单词与一组 250,000 个单词进行匹配比在一个包含相同 250,000 个单词的列表中匹配一个包含相同 10000 个单词的列表快 17,085 倍。使用源列表和成员测试集比单独使用未排序列表快 28,392 倍。

对于成员资格测试，列表的复杂度为 O(n)，集合和字典的查找复杂度为 O(1)。

结论:为 6 亿行文本使用更好的数据结构!