Python collections.Counter:most_common复杂性

Question

我想知道python 2.7中对象most_common提供的函数的复杂性是多少collections.Counter.

更具体地说,是Counter保持某种排序列表,当它被更新,允许执行的most_common速度比运行O(n)时n添加计数器的(唯一的)项目的数量？为了您的信息,我正在处理一些大量的文本数据,试图找到第n个最常见的令牌.

我检查了官方文档(https://docs.python.org/2/library/collections.html#collections.Counter),CPython wiki(https://wiki.python.org/moin/TimeComplexity)但我可以找不到答案.先感谢您!

罗曼.

Answer 1

从collections.py的源代码中,我们看到如果我们没有指定多个返回的元素,则most_common返回计数的排序列表.这是一种O(n log n)算法.

如果我们使用most_common返回k > 1元素,那么我们使用nlargest方法heapq.nlargest.这是一种O(k) + O((n - k) log k) + O(k log k)算法,对于小常数非常有用k,因为它本质上是线性的.该O(k)部分来自堆积初始k计数,第二部分来自n - k对heappushpop方法的调用,第三部分来自对最终k元素堆的排序.因为k <= n我们可以得出结论,复杂性是:

O(n log k)

如果k = 1那时很容易证明复杂性是:

上)

Answer 2

来源显示了究竟发生了什么:

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('abracadabra').most_common(3)
    [('a', 5), ('r', 2), ('b', 2)]

    '''
    # 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))