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

我有一个字符串列表（像是），并且，当我解析文本时，我需要检查一个单词是否属于我当前列表的单词组。Python：如何有效地检查项目是否在列表中？

但是，根据Python文档，我的输入非常大（大约600万行），并检查元素是否属于列表是O（n）操作。

我的代码是这样的：

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

，因为它需要的，我想改善它走的大部分时间那部分太多时间（天实际上）。我看看Python集合，更确切地说，在deque。但是，只能给O（1）操作时间访问列表的头部和尾部，而不是在中间。

有人有一个关于如何以更好的方式做到这一点的想法？

来源

2012-06-07 Jiehong

是否有任何理由不能使用一组单词来代替？可能有6亿行，但使用的英语单词少得多（如果不清除它，甚至包括前导和尾随标点符号）。测试集合中的成员应该非常快。 – DSM

@DSM：O（1）实际上，假设散列冲突相对较少:) –

您无法检查项目是否在列表中有效。这不是列表的目的。你需要选择你的数据类型（特别是集合），以适合你将要使用的数据类型，因为没有任何数据类型对每件事都很好。 – Ben

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

下面是一些相对定时为你考虑一组VS列表：

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个字与一组25万个字是17,085 X更快比匹配相同的250,000单词列表中相同的10000个单词列表。使用源代码列表和成员资格测试集合是28,392 X更快比单独未排序列表更快。

对于成员资格测试，列表是O（n），集合和字典是O（1）用于查找。

结论：为600万行文本使用更好的数据结构！

来源

2012-06-08 00:18:14

或[后缀树]（https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/） – dawg

这听起来不错。我的第一个代码需要大约500天的微积分，大约50天需要巧妙的重新分解。现在，它只需要1小时左右！即使我的集合是20万长，这是令人印象深刻的。 – Jiehong

@ user1443418：关键的延迟因素是Python操作符in对列表。如果你将这两个数据结构混合在一起，并使用一个列表来访问数据（即，在test_list中使用'for-word'），并使用set来存储成员资格（即'如果word在all_word_set'中），它甚至更快。成员测试的速度更快;列表更快地以线性方式创建访问。 '知道你的工具Luke.' –

它使用list comprehension

words_in_line = [word for word in line if word in my_list]

这将是比你发布的代码更高效，但多少对您的海量数据集是很难知道。

来源

2012-06-08 00:02:35 Levon

不，这不是我们在这种情况下寻找的答案。这仍然做600M O（n）操作（'如果word在my_list'中），它不会影响真正的问题。 –

你可以在这里做两个改进。

用哈希表返回你的单词列表。当你检查你的单词列表中是否存在单词时，这将为你提供O（1）表现。有很多方法可以做到这一点;在这种情况下最适合的是将您的列表转换为一个集合。
为您的匹配词集合使用更合适的结构。
- 如果您需要同时在内存中存储所有匹配项，请使用dequeue，因为它的附加性能优于列表。
- 如果你不需要一次在内存中的所有匹配，请考虑使用一个生成器。生成器用于根据您指定的逻辑遍历匹配值，但它一次只将结果列表的一部分存储在内存中。如果您遇到I/O瓶颈，它可能会提高性能。

下面是根据我的建议的示例实现（选择了一台发电机，因为我无法想象，你需要所有这些单词在内存中一次）。

from itertools import chain 
d = set(['a','b','c']) # Load our dictionary 
f = open('c:\\input.txt','r') 
# Build a generator to get the words in the file 
all_words_generator = chain.from_iterable(line.split() for line in f) 
# Build a generator to filter out the non-dictionary words 
matching_words_generator = (word for word in all_words_generator if word in d) 
for matched_word in matching_words_generator: 
    # Do something with matched_word 
    print matched_word 
# We're reading the file during the above loop, so don't close it too early 
f.close()

input.txt中

a b dog cat 
c dog poop 
maybe b cat 
dog

输出

a 
b 
c 
b

来源

2012-06-08 00:47:15 cheeken

我不是你为什么首先选择了一个列表清晰，但这里有一些替代品：

使用一组（）可能是一个好主意。虽然无序，但速度非常快，但有时这正是需要的。

如果你需要的东西有序，有任意查询，以及，你可以使用某种类型的树： http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

如果有少数这里误报的集员测试或有可以接受的，你可能会检查到布隆过滤器： http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/

根据你在做什么，一个特里可能也是非常好的。

来源

2012-06-08 00:58:01 user1277476

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

回答

相关问题