Python collection.Counter: Most_common сложности

Question

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

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

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

Ромны.

Answer 1

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

Если мы используем most_common возвращать k > 1 элементы, то мы используем самый большой метод heapq, Это 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 тогда легко показать, что сложность такова:

На)

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