Python collections.Counter: most_common complex

Question

Мне интересно, в чем сложность функции most_common, предоставляемой объектом collections.Counter в python 2.7.

Более конкретно, это Counter сохраняя некоторый вид отсортированного списка, пока она обновляется, что позволяет выполнять операцию most_common быстрее, чем при O(n)n этого количества (уникальных) элементов добавляются к счетчику? Для вас информация, я обрабатываю большое количество текстовых данных, пытаясь найти n-ый самый часто используемый токен.

Я проверил официальную документацию (https://docs.python.org/2/library/collections.html#collections.Counter), вики CPython (https://wiki.python.org/moin/TimeComplexity), но я не смог найти ответ. Заранее спасибо!

Romain.

Answer 1

Из исходного кода collections.py, мы видим, что если мы не будем указывать число возвращаемых элементов, most_common возвращает отсортированный список подсчетов. Это алгоритм O(n log n).

Если мы используем most_common вернуть k > 1 элементы, то мы используем nlargest метод heapq. Это алгоритм O(k) + O((n - k) log k) + O(k log k), который очень хорош для небольшой константы k, так как это очень линейно. Часть O(k) исходит из heapifying начальной цифры k, вторая часть от n - k вызывает метод heappushpop, а третья часть - от сортировки конечной кучи k элементов. Поскольку k <= n мы можем сделать вывод, что сложность:

O (N журнал 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))