Python集合计数器:most_common复杂度 [英] Python collections.Counter: most_common complexity

问题描述

Python中collections.Counter对象提供的函数most_common的复杂性是什么?

What is the complexity of the function most_common provided by the collections.Counter object in Python?

更具体地说，是Counter在计数时保留某种排序的列表，当n是添加到计数器的(唯一)项目数时，允许它执行most_common操作比O(n)更快. ?为了给您提供信息，我正在处理大量文本数据，试图找到第n个最常见的标记.

More specifically, is Counter keeping some kind of sorted list while it's counting, allowing it to perform the most_common operation faster than O(n) when n is the number of (unique) items added to the counter? For you information, I am processing some large amount of text data trying to find the n-th most frequent tokens.

我检查了官方文档和

I checked the official documentation and the TimeComplexity article on the CPython wiki but I couldn't find the answer.

推荐答案

来自

From the source code of collections.py, we see that if we don't specify a number of returned elements, most_common returns a sorted list of the counts. This is an O(n log n) algorithm.

如果我们使用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，我们可以得出以下结论:

If we use most_common to return k > 1 elements, then we use heapq.nlargest. This is an O(k) + O((n - k) log k) + O(k log k) algorithm, which is very good for a small constant k, since it's essentialy linear. The O(k) part comes from heapifying the initial k counts, the second part from n - k calls to heappushpop method and the third part from sorting the final heap of k elements. Since k <= n we can conclude that the complexity is:

O(n log k)

O(n log k)

如果为k = 1，则很容易表明复杂度为:

If k = 1 then it's easy to show that the complexity is:

O(n)

O(n)

这篇关于Python集合计数器:most_common复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！