Python collections.Counter：most_common的复杂度

Question

collections.Counter在Python中提供的most_common函数的复杂度是怎样的？

更具体地说，当计数时，Counter是否会保持某种排序列表，使得它可以在n为添加到计数器中的(唯一)项目数量时，比O(n)更快地执行most_common操作？为了您的信息，我正在处理大量文本数据，试图找到第n个最常见的令牌。

我查看了官方文档和CPython维基上的Time Complexity文章，但我没有找到答案。

- Romain G

Answer 1

从 collections.py 的源代码中可以看到，如果我们没有特别指定返回元素的数量，`most_common` 会返回一个按计数排序后的列表。这是一个 O(n log n) 算法。

如果我们使用 `most_common` 来返回 `k > 1` 个元素，我们就要使用 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`，那么很容易证明复杂度为：

O(n)

- JuniorCompressor

---

非常优雅。基准测试证实了这一点： # L = rand_list(10000000) # timeit(lambda: sorted(L)[0:6], number=50) # 44.241248495000036 # timeit(lambda: heapq.nsmallest(6, L), number=50) # 14.27249390999998 - Leo Ufimtsev

需要补充的一点是，这里我们只需要一个大小为k的堆！ - Union find

但是如果只返回一个元素，我发现使用most_common比O(n)更快，有什么建议吗？我通过循环列表并自己找到运行时最常出现的元素与直接使用most_common进行比较。 - user192344

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

heapq.nlargest 定义在 heapq.py 中。

- Padraic Cunningham

---

@RomainG，不用担心，如果没有指定n，则为n log n，或者使用heapq.nlargest，它是O(n * log(k))。 - Padraic Cunningham