Какая временная сложность counter и sorted?

Question

#1
from collections import Counter

company = {'A': 3.75, 'B': 44.2, 'C': 12.4, 'D': 44.5, 'E': 10.1}
count = Counter(company)

print(count.most_common(3))


#2
company = {'A': 3.75, 'B': 44.2, 'C': 12.4, 'D': 44.5, 'E': 10.1}
income = sorted(list(company.items()), key=lambda tup: tup[1], reverse=True)[:3]
print(income)

Answer 1

Можно посмотреть исходники модуля Collections для начала:

    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), ('b', 2), ('r', 2)]
        '''
        # Emulate Bag.sortedByCount from Smalltalk
        if n is None:
            return sorted(self.items(), key=_itemgetter(1), reverse=True)

        # Lazy import to speedup Python startup time
        import heapq
        return heapq.nlargest(n, self.items(), key=_itemgetter(1))

Как можно видеть, если вызвать most_common без параметра, то разницы с sorted вообще не будет - будет вызван в итоге он же. А вот при вызове с параметром будет вызвана другая сортировка heapq.nlargest, насколько я помню она более эффективная, чем та, которая используется в sorted, если нужно взять небольшое число самых больших или самых маленьких элементов.

Про сложность heapq.nlargest и сравнение с sorted можете попробовать почитать здесь и здесь.

БЛОГ НА HUSL

Какая временная сложность counter и sorted?

Ответы (1 шт):