Python collections.Counter: most_common complexity

Question

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

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.

score 81 · Accepted Answer · edited May 28 '19 at 01:47

81

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.

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)

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

O(n)

edited May 28 '19 at 01:47

Boris Verkhovskiy

14,854
11
100
103

answered Mar 24 '15 at 19:11

JuniorCompressor

19,631
4
30
57

Very elegant. Benchmarking confirms this: # 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 Aug 03 '19 at 14:29
1

One thing to add that's not obvious is we only need a heap of size k here! – Union find Jan 13 '21 at 17:55
but if just return 1 elm, i found that most_common is faster than o(n), any advice? i compare it by loop a list and find the running max occ by myself vs directly use most common – user192344 Jul 26 '23 at 04:45

score 16 · Answer 2 · edited May 26 '19 at 17:48

16

The source shows exactly what happens:

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 is defined in heapq.py

edited May 26 '19 at 17:48

Boris Verkhovskiy

14,854
11
100
103

answered Mar 24 '15 at 19:07

Padraic Cunningham

176,452
29
245
321

1

@RomainG, no worries, either `n log n` if n is not specified or use heapq.nlargest which is `O(n * log(k))` – Padraic Cunningham Mar 24 '15 at 19:15

Python collections.Counter: most_common complexity

2 Answers2

Linked

Related