比较 python 中的两个大型列表

Question

我有一个包含大约400个单词的列表。另一个列表列表，其中每个列表包含大约 150,000 个单词。这个列表有20个这样的列表。

现在我想看看这400个单词中有多少出现在这150,000个单词列表中。我还想知道这400个单词中的一个单词，在150k单词列表中出现多少次，这些单词中哪些出现最多，出现多少次等。

我能想到的唯一解决方案是多项式时间解决方案。这是一个非常糟糕的解决方案，并且会非常慢：

for one_list in list_of_150kwords:
    for key in 400_words:
        for word in one_list:
            if key == word:
                # count this word
                # do other stuff

这是一个非常丑陋和糟糕的解决方案，但我想不出更好的解决方案。我尝试了同样的方法，将这些列表转换为 NumPy 数组：

list_of_150kwords = numpy.array(list_of_150kwords)
...

但我仍然觉得它很慢。还有其他解决方案吗？还是任何图书馆？

Answer 1

这

听起来像是使用set的好机会：

set_of_150kwords = set(list_of_150kwords)
one_set = set(one_list)
len(one_set & set_of_150kwords) # set intersection is &
=> number of elements common to both sets

根据集合论，两个集合

的交集给出了出现在两个集合中的元素，那么一个简单的长度问题。对于第二部分（这些词中的哪一个出现最多，出现多少次等）创建一个带有list_of_150kwords的Counter，这将告诉您每个单词在列表中出现的次数。交集集将告诉您哪些是常用词，从而解决您的两个要求。

Answer 2

from collections import Counter
search_data = [
    ["list", "of", "150k", "words"],
    ["another", "list", "of", "150k", "words"],
    ["yet", "another", "list", "of", "150k", "words"]
    # ... 17 more of these
]
search_words = ["four", "hundred", "words", "to", "search", "for"]
def word_finder(words_to_find):
    lookfor = set(word.lower() for word in words_to_find)
    def get_word_count(text):
        return Counter(word for word in (wd.lower() for wd in text) if word in lookfor)
    return get_word_count
def get_words_in_common(counters):
    # Maybe use c.viewkeys() instead of set(c)? Which is faster?
    return reduce(operator.and_, (set(c) for c in counters))
def main():
    wordcount = word_finder(search_words)
    counters = [wordcount(wordlst) for wordlst in search_data]
    common_to_all = get_words_in_common(counters)
    print(common_to_all)
if __name__=="__main__":
    main()

Answer 3

这是Trie有用的地方的规范示例。您需要为每个 150K 列表创建一个 Trie。然后，您可以在O（W）时间内检查列表中是否存在给定的单词。其中 W 是单词的最大长度。

然后你可以循环浏览400字的列表，检查每部作品是否在150K字的列表中。

鉴于 L 即 150K 列表的数量远小于 150K，W 远

小于 150K，没有集合连接会像 Trie 比较那样快。

最终运行复杂度：

N = 400 //Size of small list
W = 10 // Max word Length
M = 150K // Max size of the 150K lists
P = 4 // Number of 150K lists
P * M // To construct Trie
N * P * W // To find each word in the 150k lists
MP + NPW // Total complexit

Answer 4

经典地图减少问题....http://sist.sysu.edu.cn/~wuweig/DSCC/Inverted%20Indexing%20by%20MapReduce.pdf