dict - Colecciones de Python. Contador: complejidad más_común

python 3.6 collections

Question

Me pregunto cuál es la complejidad de la función most_common proporcionada por las collections.Counter most_common el objeto en Python 2.7.

Más específicamente, ¿el Counter mantiene algún tipo de lista ordenada mientras se está actualizando, lo que permite realizar la operación most_common más rápido que O(n) cuando n es el número de elementos (únicos) agregados al contador? Para su información, estoy procesando una gran cantidad de datos de texto tratando de encontrar los tokens más frecuentes.

Revisé la documentación oficial ( https://docs.python.org/2/library/collections.html#collections.Counter ), la wiki de CPython ( https://wiki.python.org/moin/TimeComplexity ) pero pude No encuentra la respuesta. ¡Gracias de antemano!

Romain

Answer 1

Desde el código fuente de collections.py , vemos que si no especificamos un número de elementos devueltos, most_common devuelve una lista ordenada de los conteos. Este es un algoritmo O(n log n) .

Si usamos most_common para devolver k > 1 elementos, entonces usamos el método heapq de heapq . Este es un algoritmo O(k) + O((n - k) log k) + O(k log k) , que es muy bueno para una pequeña constante k , ya que es esencialmente lineal. La parte O(k) proviene de la heapificación de los recuentos de k iniciales, la segunda parte de n - k llama al método heappushpop y la tercera parte de la clasificación del montón final de k elementos. Como k <= n podemos concluir que la complejidad es:

O (n log k)

Si k = 1 entonces es fácil mostrar que la complejidad es:

En)

Answer 2

La fuente muestra exactamente lo que sucede:

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