python - collections.Counter 如何实现快速排序时间？

Question

最近我一直在研究 Python 的 collections.Counter数据结构。此对象的规范用途是计算文本文件中单词的出现次数:

from collections import Counter

with open(r'filename') as f:
    #create a list of all words in the file using a list comprehension
    words = [word for line in f for word in line.split()]

c = Counter(words)

最酷的部分是如何使用这个结构来找出最常见的词:

for word, count in c.most_common():
    print word, count

我不明白的部分是most_common() runs in O(n) time [编辑:这是不正确的。根据 Martijn 的回答，它实际上在 O(n log k)] 中运行。显然，这意味着它不能在幕后用字典进行比较排序，因为最快的比较排序是 O(nlogn)。

那么collections.Counter是如何实现快速排序的呢？

Answer 1

它不会在 O(n) 时间内运行。当您请求字典中的所有 值时，会使用常规排序，即 O(NlogN) 算法。

当请求前 K 个结果时，使用 heapq.nlargest() 调用，这是一种在 O(NlogK) 时间内更有效的方法:

def most_common(self, n=None):
    '''List the n most common elements and their counts from the most
    common to the least.  If n is None, then list all element counts.

    >>> Counter('abcdeabcdabcaba').most_common(3)
    [('a', 5), ('b', 4), ('c', 3)]

    '''
    # Emulate Bag.sortedByCount from Smalltalk
    if n is None:
        return sorted(self.iteritems(), key=_itemgetter(1), reverse=True)
    return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1))

答案谈到了在线性时间内完成的计数；构造 Counter 实例，基本上是对输入可迭代对象的循环:

for elem in iterable:
    self[elem] = self_get(elem, 0) + 1