Cómo implementar eficientemente un mapa de contador

Esta es una discusión sobre stackoverflow hace muchos años, y la respuesta implica una variedad de métodos de conteo. Para un mapa con una estructura clave-valor, a menudo nos referimos a la clave como un objeto al programar y al valor como un número entero o largo para ser responsable de contar, contando así la frecuencia de múltiples claves.

Ante un requisito tan básico, pueden existir muchas implementaciones. Por ejemplo, el más básico se implementa directamente usando el mapa de jdk: el valor es un número entero o largo. Su tipo de código básico es el siguiente:

1: final Maplt; String, Integergt; freq = new HashMaplt;

2: int count = freq. contieneKey(palabra) ? freq.get(palabra): 0;

3: freq.put(palabra, recuento 1); y obtenga el valor si es , de lo contrario es 0, y luego ingrese un valor más 1. Siempre es necesario juzgar el contenido y realizar tres llamadas a los métodos get y put.

Por supuesto, podemos eliminar aún más el juicio de contención. El código es el siguiente:

1: final Maplt; String, Integergt; );

2: Número entero = freq.get(palabra

3: if (count == null) {

4: freq.put; (palabra, 1) ;

5: } else {

6: freq.put(palabra, recuento 1);

7: }

Situación general, cuando llegamos a este punto, la mayoría de la gente está satisfecha con su lógica y la ejecución simple es aceptable. Intente pensar en ello, ¿no? Obtener más poner, resuelto.

Por supuesto, esta implementación no es lo suficientemente eficiente, por lo que comenzamos a intentar implementar o encontrar métodos más eficientes para ver si se necesita la biblioteca de colección de código abierto:

Hay Trove , hagamos referencia a él:

1: final TObjectIntHashMaplt; Stringgt; freq = new TObjectIntHashMaplt (); ;

Esto es muy elegante. ¿Cómo es la actuación? No lo sé, debes mirar el código fuente para comprender los detalles. ¿Qué tal echarle un vistazo a la famosa guayaba?

1: AtomicLongMaplt; Stringgt; map = AtomicLongMap.create();

2: map.getAndIncrement(word);

La implementación sigue siendo elegante. pero, pero mire el nombre y luego mire el código fuente, está bien, es seguro para subprocesos y admite la concurrencia. Esto no es fácil en nuestro escenario. Si no es necesario, nuestra intuición nos dice que debe ser "lento".

Buscar de nuevo:

1: Multisetlt; stringgt; bag = HashMultiset.create();

2: bag.add(word) Es apropiado. La implementación de bag es obviamente mucho mejor y, desde una comprensión semántica, dicha interfaz es más fácil de entender.

Entonces, ¿cuál es el rendimiento de estos métodos? Hice una comparación simple, usando 26 letras en inglés como clave, y recorrí uniformemente varias veces para comparar la eficiencia de cada método (eficiencia de tiempo puro), y el tiempo no cuenta los gastos generales de construcción. Además, se implementa una versión segura para subprocesos de concurrentMap. De hecho, AtomicLongMap en la guayaba de Google también envuelve el concurrentMap de juc. Contiene el método MutableInt definitivo, búsquelo, tiene el mejor rendimiento.