通过Python中非常大的列表计算速度/性能

Question

我正在用Python 3编写一个程序,它的一部分功能是找出列表中出现最多的单词并返回该单词的出现次数.我有适用的代码,但部分要求是它需要一个200,000多个单词的列表并在几秒钟内完成此活动,并且我的代码需要很长时间才能运行.我想知道你对这种方法的速度改进有什么建议.

def max_word_frequency(words):
    """A method that takes a list and finds the word with the most
    occurrences and returns the number of occurences of that word
    as an integer.
    """
    max_count = 0
    for word in set(words):
        count = words.count(word)
        if count > max_count:
            max_count = count

    return max_count

我已经考虑过使用字典,因为与列表相比它们可以清洗和超级快速,但我还不知道如何实现它.

谢谢大家的时间!
- 芬恩

Answer 1

首先,您的算法循环遍历m整个200 000个单词列表,其中m是此列表中不同单词的数量.这对于计算单词的迭代并选择最大值来说真的不是一个好主意.我可以向你展示一个更有效的算法(它只能在列表上迭代一次),但Python已经有了工具来做你想要的.

要使用几行代码解决您的问题,您可以使用标准库中提供的Python算法,该算法已在C中实现,并且可能比您的循环更有效.该方法Counter及其most_common方法可能对您有所帮助:

>>> from collections import Counter
>>> counts = Counter(['abc', 'def', 'abc', 'foo', 'bar', 'foo', 'foo'])
>>> counts
Counter({'foo': 3, 'abc': 2, 'bar': 1, 'def': 1})
>>> Counter(['abc', 'def', 'abc', 'foo', 'bar', 'foo', 'foo']).most_common(1)
[('foo', 3)]

你只需要返回元组的第二个元素(这里只有一个元组,因为我们通过1参数询问most_common)

绩效比较

为了比较,我拿了一个LaTeX文件的样本(~12Ko),用空格分割单词(给出x1835个单词)并运行你的函数和下面的timete.你可以看到真正的收获.

>>> len(x)
1835
>>> def max_word_2(words):
...     counts = Counter(words)
...     return counts.most_common(1)[0][1]
>>> timeit.timeit("max_word_2(x)", setup="from __main__ import x, max_word_2", number=1000)
1.1040630340576172
>>> timeit.timeit("max_word_frequency(x)", setup="from __main__ import x, max_word_frequency", number=1000)
35.623037815093994

只是这个改变可能足以加快你的过程:)