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：如何有效地檢查項目是否在列表中？

回答

相關問題