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屋!