Contador eficiente en Java – Programación.Click

A menudo, es posible que necesite un contador para comprender la frecuencia de algo (por ejemplo, palabras) de una base de datos o un archivo de texto. Un contador se puede implementar fácilmente usando un HashMap en Java. Este artículo compara diferentes enfoques para implementar un contador. Finalmente, se concluirá uno eficiente.

ACTUALIZACIÓN: Eche un vistazo al contador de Java 8, escribir un contador son solo 2 líneas simples ahora.

1. El Ingenuo Encimera

Ingenuamente, se puede implementar de la siguiente manera:

String s = "one two three two three three";
String[] sArr = s.split(" ");
 
//naive approach	 
HashMap<String, Integer> counter = new HashMap<String, Integer>();
 
for (String a : sArr) {
	if (counter.containsKey(a)) {
		int oldValue = counter.get(a);
		counter.put(a, oldValue + 1);
	} else {
		counter.put(a, 1);
	}
}

En cada bucle, verifica si la clave existe o no. Si es así, incremente el valor anterior en 1, si no, establézcalo en 1. Este enfoque es simple y directo, pero no es el enfoque más eficiente. Este método se considera menos eficaz por las siguientes razones:

containsKey (), get () se llaman dos veces cuando ya existe una clave. Eso significa buscar en el mapa dos veces.
Dado que Integer es inmutable, cada bucle creará uno nuevo para incrementar el valor anterior

2. El Mejor Encimera

Naturalmente, queremos un entero mutable para evitar la creación de muchos objetos Integer. Una clase de entero mutable se puede definir de la siguiente manera:

class MutableInteger {
 
	private int val;
 
	public MutableInteger(int val) {
		this.val = val;
	}
 
	public int get() {
		return val;
	}
 
	public void set(int val) {
		this.val = val;
	}
 
	//used to print value convinently
	public String toString(){
		return Integer.toString(val);
	}
}

LeetCode - Ceros finales factoriales (Java)

Y el contador se mejora y cambia a lo siguiente:

HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();	
 
for (String a : sArr) {
	if (newCounter.containsKey(a)) {
		MutableInteger oldValue = newCounter.get(a);
		oldValue.set(oldValue.get() + 1);
	} else {
		newCounter.put(a, new MutableInteger(1));
	}
}

Esto parece mejor porque ya no requiere la creación de muchos objetos Integer. Sin embargo, la búsqueda sigue siendo dos veces en cada bucle si existe una clave.

3. El Eficiente Encimera

El método HashMap.put (clave, valor) devuelve el valor actual de la clave. ¡Esto es útil, porque podemos usar la referencia del valor anterior para actualizar el valor sin buscar una vez más!

HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();
 
for (String a : sArr) {
	MutableInteger initValue = new MutableInteger(1);
	MutableInteger oldValue = efficientCounter.put(a, initValue);
 
	if(oldValue != null){
		initValue.set(oldValue.get() + 1);
	}
}

4. Diferencia de rendimiento

Para probar el rendimiento de los tres enfoques diferentes, se utiliza el siguiente código. La prueba de rendimiento se realiza 1 millón de veces. Los resultados brutos son los siguientes:

Naive Approach :  222796000
Better Approach:  117283000
Efficient Approach:  96374000

La diferencia es significativa: 223 frente a 117 frente a 96. Existe una gran diferencia entre Ingenuo y Mejor, lo que indica que crear objetos es caro.

String s = "one two three two three three";
String[] sArr = s.split(" ");
 
long startTime = 0;
long endTime = 0;
long duration = 0;
 
// naive approach
startTime = System.nanoTime();
HashMap<String, Integer> counter = new HashMap<String, Integer>();
 
for (int i = 0; i < 1000000; i++)
	for (String a : sArr) {
		if (counter.containsKey(a)) {
			int oldValue = counter.get(a);
			counter.put(a, oldValue + 1);
		} else {
			counter.put(a, 1);
		}
	}
 
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Naive Approach :  " + duration);
 
// better approach
startTime = System.nanoTime();
HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();
 
for (int i = 0; i < 1000000; i++)
	for (String a : sArr) {
		if (newCounter.containsKey(a)) {
			MutableInteger oldValue = newCounter.get(a);
			oldValue.set(oldValue.get() + 1);
		} else {
			newCounter.put(a, new MutableInteger(1));
		}
	}
 
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Better Approach:  " + duration);
 
// efficient approach
startTime = System.nanoTime();
 
HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();
 
for (int i = 0; i < 1000000; i++)
	for (String a : sArr) {
		MutableInteger initValue = new MutableInteger(1);
		MutableInteger oldValue = efficientCounter.put(a, initValue);
 
		if (oldValue != null) {
			initValue.set(oldValue.get() + 1);
		}
	}
 
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Efficient Approach:  " + duration);

Compile y ejecute Java en la línea de comandos con jarras externas

Cuando usa un contador, probablemente también necesite una función para ordenar el mapa por valor. Puede consultar el método de uso frecuente de HashMap.

5. Soluciones de Keith

Se agregaron un par de pruebas:
1) Refactorizado «mejor enfoque» para simplemente llamar a get en lugar de containsKey. Por lo general, los elementos que desea están en el HashMap, por lo que se reduce de dos búsquedas a una.
2) Se agregó una prueba con AtomicInteger, que Michal mencionó.
3) En comparación con la matriz int singleton, que usa menos memoria según http://amzn.com/0748614079

Ejecuté el programa de prueba 3 veces y tomé el mínimo para eliminar la variación de otros programas. Tenga en cuenta que no puede hacer esto dentro del programa o los resultados se ven demasiado afectados, probablemente debido a gc.

Naive: 201716122
Better Approach: 112259166
Efficient Approach: 93066471
Better Approach (without containsKey): 69578496
Better Approach (without containsKey, with AtomicInteger): 94313287
Better Approach (without containsKey, with int[]): 65877234

Mejor enfoque (sin containsKey):

HashMap<String, MutableInteger> efficientCounter2 = new HashMap<String, MutableInteger>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
	for (String a : sArr) {
		MutableInteger value = efficientCounter2.get(a);
 
		if (value != null) {
			value.set(value.get() + 1);
		} else {
			efficientCounter2.put(a, new MutableInteger(1));
		}
	}
}

Mejor enfoque (sin containsKey, con AtomicInteger):

HashMap<String, AtomicInteger> atomicCounter = new HashMap<String, AtomicInteger>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
	for (String a : sArr) {
		AtomicInteger value = atomicCounter.get(a);
 
		if (value != null) {
			value.incrementAndGet();
		} else {
			atomicCounter.put(a, new AtomicInteger(1));
		}
	}
}

Bucle un iterable en Java

Mejor enfoque (sin containsKey, con int[]):

HashMap<String, int[]> intCounter = new HashMap<String, int[]>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
	for (String a : sArr) {
		int[] valueWrapper = intCounter.get(a);
 
		if (valueWrapper == null) {
			intCounter.put(a, new int[] { 1 });
		} else {
			valueWrapper[0]++;
		}
	}
}

Probablemente, el MultiSet de Guava sea aún más rápido.

6. Conclusión

El ganador es el último que usa matrices int.

Referencias:
1. La forma más eficiente de incrementar un valor de Map en Java.
2. HashMap.put ()

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta