performance - tiene - contar veces que se repite un elemento en una lista python

La manera más eficiente de contar las ocurrencias?

Question

Estoy buscando calcular la entropía y la información mutua una gran cantidad de veces en el código de rendimiento crítico. Como paso intermedio, necesito contar el número de ocurrencias de cada valor. Por ejemplo:

uint[] myArray = [1,1,2,1,4,5,2];
uint[] occurrences = countOccurrences(myArray);
// Occurrences == [3, 2, 1, 1] or some permutation of that.
// 3 occurrences of 1, 2 occurrences of 2, one each of 4 and 5.

Por supuesto, las formas obvias de hacer esto son usar una matriz asociativa o ordenar la matriz de entrada usando un algoritmo de clasificación "estándar" como ordenar rápidamente. Para enteros pequeños, como bytes, el código está actualmente especializado para usar una matriz antigua simple.

¿Hay algún algoritmo inteligente para hacer esto de manera más eficiente que una tabla hash o un algoritmo de clasificación "estándar", como una implementación de matriz asociativa que favorece las actualizaciones sobre inserciones o un algoritmo de clasificación que brilla cuando los datos tienen muchos vínculos ?

Nota: Los enteros no dispersos son solo un ejemplo de un posible tipo de datos. Estoy buscando implementar una solución razonablemente genérica aquí, aunque como los enteros y las estructuras que contienen solo enteros son casos comunes, estaría interesado en soluciones específicas para estos si son extremadamente eficientes.

Answer 1

Con una matriz de enteros como en el ejemplo, la forma más eficiente sería tener una matriz de int e indexarla usando sus valores (como parece que ya lo está haciendo).

Si no puedes hacer eso, no puedo pensar en una alternativa mejor que un hashmap. Solo necesitas tener un algoritmo hash rápido. No puede obtener un rendimiento superior a O (n) si desea utilizar todos sus datos. ¿Es una opción usar solo una parte de los datos que tiene?

(Tenga en cuenta que la clasificación y el recuento son asintóticamente más lentos (O (n * log (n))) que utilizando una solución basada en hashmap (O (n)).)

Answer 2

Hashing es generalmente más escalable, como indica otra respuesta. Sin embargo, para muchas distribuciones posibles (y muchos casos de la vida real, donde por lo general se clasifican subarreglos , dependiendo de cómo se armó el conjunto general), timsort suele ser "sobrenaturalmente bueno" (más cercano a O (N) que a O (N log N)) - Escuché que probablemente se convertirá en el algoritmo de clasificación estándar / predeterminado en Java en algunos datos futuros razonablemente próximos (desde hace años es el algoritmo de clasificación estándar en Python).

No hay una manera realmente buena de abordar estos problemas, excepto para comparar una selección de casos que sean representativos de la carga de trabajo de la vida real que usted espera experimentar (con el riesgo obvio de que pueda elegir una muestra que realmente sea parcial / no -representativo: no es un riesgo pequeño si intenta crear una biblioteca que será utilizada por muchos usuarios externos fuera de su control).

Answer 3

Por favor, cuenta más sobre tus datos.

• ¿Cuántos artículos hay?
• ¿Cuál es la proporción esperada de artículos únicos a artículos totales?
• ¿Cuál es la distribución de los valores reales de tus enteros? ¿Son generalmente lo suficientemente pequeños como para usar una matriz de conteo simple? ¿O están agrupados en grupos razonablemente estrechos? Etc.

En cualquier caso, sugiero la siguiente idea: un mergesort modificado para contar duplicados.

Es decir, trabajas en términos de no números, sino de pares (número, frecuencia) (puedes usar alguna representación inteligente de memoria eficiente para eso, por ejemplo, dos matrices en lugar de una matriz de pares, etc.).

Empiezas con [(x1,1), (x2,1), ...] y haces un mergesort como de costumbre, pero cuando fusionas dos listas que comienzan con el mismo valor, colocas el valor en la lista de salida con su suma de ocurrencias. En tu ejemplo:

[1:1,1:1,2:1,1:1,4:1,5:1,2:1]
Split into [1:1, 1:1, 2:1] and [1:1, 4:1, 5:1, 2:1]
Recursively process them; you get [1:2, 2:1] and [1:1, 2:1, 4:1, 5:1]
Merge them: (first / second / output)
[1:2, 2:1] / [1:1, 2:1, 4:1, 5:1] / [] - we add up 1:2 and 1:1 and get 1:3
[2:1] / [2:1, 4:1, 5:1] / [1:3] - we add up 2:1 and 2:1 and get 2:2
[] / [4:1, 5:1] / [1:3, 2:2]
[1:3, 2:2, 4:1, 5:1]

Esto podría mejorarse enormemente mediante el uso de algunos trucos inteligentes para hacer una reducción inicial de la matriz (obtener una matriz de valores: pares de ocurrencias mucho más pequeños que la original, pero la suma de ''ocurrencia'' para cada ''valor'' es igual a el número de ocurrencias de ''valor'' en la matriz original). Por ejemplo, divida la matriz en bloques continuos donde los valores difieren en no más de 256 o 65536 y use una matriz pequeña para contar las ocurrencias dentro de cada bloque. En realidad, este truco también se puede aplicar a fases posteriores de fusión.