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

Question

我有一个字符串列表(像这样的单词),当我解析文本时,我需要检查一个单词是否属于我当前列表中的单词组.

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

我的代码是这样的:

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

由于花费了太多时间(实际上是几天),我想改进大部分时间都要花费的那部分.我看看Python集合,更准确地说,看看deque.但是,只允许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个单词的列表快17085 X. 使用源列表和成员资格测试集合比单独的未排序列表快28,392 X.

对于成员资格测试,列表是O(n),并且set和dicts是O(1)用于查找.

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