¿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 ya sea usando una matriz asociativa o por la clasificación de la matriz de entrada usando un algoritmo de ordenación "estándar" como tipo rápido. 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 sus datos muchos lazos

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

Más información sobre sus datos.

• ¿Cuántos artículos hay?
• ¿Cuál es la relación esperada de artículos únicos a artículos totales?
• ¿Cuál es la distribución de los valores reales de sus 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, trabaja en términos de no números, sino de pares (número, frecuencia) (puede 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 unes dos listas que comienzan con el mismo valor, colocas el valor en el lista de salida con su suma de ocurrencias. En su 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 ser mejorado mediante el uso de algunos trucos inteligentes que hacer una reducción inicial de la matriz (obtener una matriz de valor: pares de ocurrencia de que es mucho más pequeño que el original, pero la suma de 'ocurrencia' para cada 'valor' es igual al 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.

Answer 2

Con una matriz de enteros como en el ejemplo, la forma más eficiente sería tener una matriz de int sy indexarla utilizando sus valores (como parece estar haciendo ya).

Si no puede hacer eso, no puedo pensar en una mejor alternativa 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 es asintóticamente más lento (O (n * log (n))) que el uso de una solución basada HashMap (O (n)).)

Answer 3

Hashing es generalmente más escalable, como otro respuesta indica. Sin embargo, para muchas distribuciones posibles (y muchos casos de la vida real, donde los subarreglos simplemente se clasifican a menudo, dependiendo de cómo se armó el conjunto general), timsort es a menudo "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 buena manera de abordar estos problemas, excepto para comparar una selección de casos representativos de la carga de trabajo de la vida real que espera experimentar (con el riesgo obvio de que pueda elegir una muestra que realmente le haya sucedido) ser 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).