[PYTHON] 파이썬 컬렉션. 카운터 : most_common complexity

파이썬 컬렉션. 카운터 : most_common complexity

파이썬 2.7에서 collections.Counter 객체에 의해 제공되는 함수 most_common의 복잡성이 무엇인지 궁금합니다.

좀 더 구체적으로, 카운터가 일종의 정렬 된 목록을 유지하면서 업데이트되는 동안 n이 카운터에 추가 된 고유 항목 수인 경우 O (n)보다 most_common 연산을 더 빠르게 수행 할 수 있습니까? 정보를 얻기 위해, n 번째 가장 빈번한 토큰을 찾기 위해 많은 양의 텍스트 데이터를 처리 중입니다.

CPython 위키 (https://wiki.python.org/moin/TimeComplexity) 공식 문서 (https://docs.python.org/2/library/collections.html#collections.Counter)를 확인했지만 대답을 찾지 못했습니다. 미리 감사드립니다.

로맹.

해결법

1. ==============================

   1.collections.py의 소스 코드에서 우리는 반환 된 요소의 수를 지정하지 않으면 most_common이 개수의 정렬 된 목록을 반환한다는 것을 알 수 있습니다. 이것은 O (n log n) 알고리즘입니다.

   collections.py의 소스 코드에서 우리는 반환 된 요소의 수를 지정하지 않으면 most_common이 개수의 정렬 된 목록을 반환한다는 것을 알 수 있습니다. 이것은 O (n log n) 알고리즘입니다.

   most_common을 사용하여 k> 1 요소를 반환하면 heapq의 nlargest 메서드를 사용합니다. 이것은 O (k) + O ((n - k) log k) + O (k log k) 알고리즘으로 작은 상수 k에 매우 유용합니다. O (k) 부분은 초기 k 카운트를 heapifying하고, 두 번째 부분은 heappushpop 메소드로 호출하며, 세 번째 부분은 k 요소의 최종 힙을 정렬합니다. k <= n이기 때문에 복잡성은 다음과 같다고 결론 지을 수있다.

   k = 1이면 복잡성을 쉽게 나타낼 수 있습니다.

2. ==============================

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

from https://stackoverflow.com/questions/29240807/python-collections-counter-most-common-complexity by cc-by-sa and MIT license