De una manera más eficiente para incrementar un valor de Mapa en Java
https://stackoverflow.com/questions/81346
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Espero que esta pregunta no está considerada demasiado básicos para este foro, pero vamos a ver.Me pregunto cómo refactorizar el código para un mejor rendimiento que es llevar un montón de veces.
Dicen que estoy creando una lista de frecuencias de palabras, el uso de un Mapa (probablemente un HashMap), donde cada tecla es una Cadena de texto con la palabra que está siendo contado y el valor es un Entero que se incrementa cada vez que un símbolo de la palabra.
En Perl, el incremento de dicho valor sería extremadamente fácil:
$map{$word}++;
Pero en Java, es mucho más complicado.Aquí la forma en que actualmente estoy haciendo:
int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);
Que por supuesto se basa en el autoboxing característica en las nuevas versiones de Java.Me pregunto si usted puede pensar en una forma más eficiente de incrementar dicho valor.Hay incluso un buen rendimiento razones para evitar el framework de Colecciones y el uso de un algo a cambio?
Actualización:He hecho una prueba de varias de las respuestas.Ver a continuación.
Solución
Algunos de los resultados de la prueba
He recibido un montón de buenas respuestas a esta pregunta, gracias a la gente--así que me decidí a correr algunas pruebas y averiguar qué método es en realidad más rápido.Los cinco métodos que he probado son estos:
- el "ContainsKey" el método que he presentado en la pregunta
- el "TestForNull" método sugerido por Aleksandar Dimitrov
- el "AtomicLong" método sugerido por Hank Gay
- el "Tesoro" método sugerido por jrudolph
- el "MutableInt" método sugerido por phax.myopenid.com
Método
Esto es lo que hice...
- creado cinco clases que eran idénticos excepto por las diferencias que se muestra a continuación.Cada grupo tenía que realizar una operación típica de el escenario que se me presenta:la apertura de un archivo de 10 mb y la lectura, a continuación, realizar un recuento de frecuencia de la palabra fichas en el archivo.Desde este tuvo un promedio de sólo 3 segundos, tuve que realizar el recuento de frecuencia (no la e/S) 10 veces.
- temporizar el bucle de 10 iteraciones, pero no la operación de e/S y registra el tiempo total empleado (en el reloj de segundos) que básicamente Ian Darwin método en Java libro de cocina.
- realiza todas las cinco pruebas en serie, y luego hizo este otro tres veces.
- promedio de los cuatro resultados de cada método.
Resultados
Voy a presentar los resultados de la primera y el código de abajo para aquellos que estén interesados.
El ContainsKey el método fue, como se esperaba, el más lento, así que me voy a dar la velocidad de cada método en comparación con la velocidad de ese método.
- ContainsKey: 30.654 segundos (línea de base)
- AtomicLong: 29.780 segundos (1.03 veces más rápido)
- TestForNull: 28.804 segundos (1.06 veces más rápido)
- Tesoro: 26.313 segundos (1.16 veces más rápido)
- MutableInt: 25.747 segundos (1.19 veces más rápido)
Conclusiones
Parecería que sólo el MutableInt método y el Tesoro método son significativamente más rápido, en el que solo ellos pueden dar un aumento de rendimiento de más del 10%.Sin embargo, si el roscado es un problema, AtomicLong puede ser más atractivo que los demás (no estoy muy seguro).También corrí con TestForNull final variables, pero la diferencia era insignificante.
Tenga en cuenta que no he perfilado el uso de la memoria en los diferentes escenarios.Yo estaría feliz de saber de alguien que tiene una buena visión de cómo los MutableInt y el Tesoro de los métodos sería probable que afectan el uso de la memoria.
Personalmente, creo que la MutableInt método el más atractivo, ya que no requieren la carga de terceros clases.Así que a menos que descubro que tengo problemas con él, que es la forma en que me siento más probabilidades de ir.
El código
Aquí es crucial el código de cada método.
ContainsKey
import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(word) ? freq.get(word) : 0;
freq.put(word, count + 1);
TestForNull
import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
Integer count = freq.get(word);
if (count == null) {
freq.put(word, 1);
}
else {
freq.put(word, count + 1);
}
AtomicLong
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicLong;
...
final ConcurrentMap<String, AtomicLong> map =
new ConcurrentHashMap<String, AtomicLong>();
...
map.putIfAbsent(word, new AtomicLong(0));
map.get(word).incrementAndGet();
Tesoro
import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1);
MutableInt
import java.util.HashMap;
import java.util.Map;
...
class MutableInt {
int value = 1; // note that we start at 1 since we're counting
public void increment () { ++value; }
public int get () { return value; }
}
...
Map<String, MutableInt> freq = new HashMap<String, MutableInt>();
...
MutableInt count = freq.get(word);
if (count == null) {
freq.put(word, new MutableInt());
}
else {
count.increment();
}
Otros consejos
OK, puede ser una vieja pregunta, pero hay un camino más corto con Java 8 :
Map.merge(key, 1, Integer::sum)
Lo que hace :si clave no existe, puesto 1 como valor, de lo contrario suma 1 el valor vinculado a clave.Más información aquí
Un poco de investigación en 2016: https://github.com/leventov/java-word-count, referencia código fuente
Mejores resultados por el método (menor es mejor):
time, ms
kolobokeCompile 18.8
koloboke 19.8
trove 20.8
fastutil 22.7
mutableInt 24.3
atomicInteger 25.3
eclipse 26.9
hashMap 28.0
hppc 33.6
hppcRt 36.5
Tiempo espacio
esultados:
Google La guayaba es tu amigo...
...al menos en algunos casos.Que tener esta buena AtomicLongMap.Especialmente agradable porque usted está tratando con largo como valor en su mapa.
E. g.
AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(word);
También es posible agregar más de 1 para el valor:
map.getAndAdd(word, 112L);
@Hank Gay
Como seguimiento a mi propia (y bastante inútil) comentario:Tesoro se ve como el camino a seguir.Si, por cualquier razón, quería seguir con el estándar JDK, ConcurrentMap y AtomicLong puede hacer que el código de una pequeño poco más agradable, aunque YMMV.
final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
map.putIfAbsent("foo", new AtomicLong(0));
map.get("foo").incrementAndGet();
dejará 1 como el valor en el mapa para foo.De manera realista, el aumento de la amistad para el roscado es todo lo que este enfoque ha de recomendar.
Siempre es una buena idea mirar en la Google Colecciones De La Biblioteca para este tipo de cosas.En este caso un Conjunto múltiple va a hacer el truco:
Multiset bag = Multisets.newHashMultiset();
String word = "foo";
bag.add(word);
bag.add(word);
System.out.println(bag.count(word)); // Prints 2
Hay Mapa-como métodos para iterar sobre las teclas/entradas, etc.Internamente, la aplicación utiliza en la actualidad un HashMap<E, AtomicInteger>, por lo que no se incurrirá en costos de boxeo.
Usted debe ser consciente del hecho de que su tentativa original
int count = map.containsKey(word) ? map.get(word) : 0;
contiene dos potencialmente costosas operaciones en un mapa, es decir, containsKey y get.El primero realiza una operación potencialmente bastante similar a la de los últimos, así que estamos haciendo el mismo trabajo dos veces!
Si usted mira la API de Mapas, get las operaciones suelen devolver null cuando el mapa no contiene el elemento solicitado.
Tenga en cuenta que esto hará que una solución como
map.put( key, map.get(key) + 1 );
peligroso, ya que podría producir NullPointerExceptions.Usted debe comprobar para un null en primer lugar.
También se nota, y esto es muy importante, que HashMaps puede contienen nulls por definición.Así que no todos los devuelven null dice que "no hay ningún elemento en común".En este sentido, containsKey se comporta de manera diferente de get en realidad diciendo si hay un elemento.Se refieren a la API para obtener más detalles.
Para su caso, sin embargo, usted podría no querer distinguir entre un almacenados null y "noSuchElement".Si usted no quiere permitir nulls es posible que prefiera un Hashtable.El uso de un contenedor de la biblioteca como ya fue propuesto en otras respuestas podría ser una mejor solución para el tratamiento manual, dependiendo de la complejidad de su aplicación.
Para completar la respuesta (y se me olvidó poner que en primer lugar, gracias a la función de edición!), la mejor manera de hacerlo de forma nativa, es get en un final variable, comprobar null y put de nuevo con un 1.La variable debe ser final porque es inmutable de todos modos.El compilador puede que no necesite esta sugerencia, pero su más clara de esa manera.
final HashMap map = generateRandomHashMap();
final Object key = fetchSomeKey();
final Integer i = map.get(key);
if (i != null) {
map.put(i + 1);
} else {
// do something
}
Si no quieres depender de autoboxing, usted debe decir algo como map.put(new Integer(1 + i.getValue())); en su lugar.
Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0);
map.put(key, count + 1);
Y esa es la manera de incrementar un valor con un simple código.
Beneficio:
- No crear otra clase para mutable int
- Código corto
- Fácil de entender
- No hay excepción de puntero nulo
Otra manera es utilizar el método merge, pero esto es demasiado para incrementar un valor.
map.merge(key, 1, (a,b) -> a+b);
Sugerencia:usted debe preocuparse acerca de la legibilidad del código, más de poco rendimiento que se obtiene en la mayoría de las veces.
Otra forma de sería la creación de un mutable entero:
class MutableInt {
int value = 0;
public void inc () { ++value; }
public int get () { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt> ();
MutableInt value = map.get (key);
if (value == null) {
value = new MutableInt ();
map.put (key, value);
} else {
value.inc ();
}
por supuesto, esto implica la creación de un objeto adicional, pero la sobrecarga en comparación a la creación de un Entero (incluso con el Entero.valueOf) no debe ser mucho.
Usted puede hacer uso de computeIfAbsent método en Map interfaz proporcionada en Java 8.
final Map<String,AtomicLong> map = new ConcurrentHashMap<>();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("B", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); //[A=2, B=1]
El método computeIfAbsent comprueba si la clave especificada ya está asociado con un valor o no?Si no hay ningún valor asociado, a continuación, intenta calcular su valor utilizando la función de asignación.En cualquier caso, se devuelve el actual (existente o calculada) valor asociado con la clave especificada, o null si el valor calculado es nulo.
En una nota de lado, si usted tiene una situación en la que varios subprocesos actualización común de la cantidad que usted puede tener una mirada en LongAdder clase.Bajo de alta contención, el rendimiento esperado de esta clase es significativamente mayor que AtomicLong, a expensas de un mayor consumo de espacio.
Memoria de rotación puede ser un problema aquí, ya que cada boxeo de un entero mayor que o igual a 128 provoca una asignación de objeto (ver Entero.valueOf(int)).Aunque el recolector de basura de manera muy eficiente trata con objetos de corta duración, el rendimiento se sufren en algún grado.
Si usted sabe que el número de incrementos de hecho en gran medida supera el número de teclas (=palabras en este caso), considere la posibilidad de usar un int titular en su lugar.Phax ya presentó el código de este.Aquí está de nuevo, con dos cambios (titular de la clase de hechos estáticos, y el valor inicial se establece en 1):
static class MutableInt {
int value = 1;
void inc() { ++value; }
int get() { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt>();
MutableInt value = map.get(key);
if (value == null) {
value = new MutableInt();
map.put(key, value);
} else {
value.inc();
}
Si usted necesita un rendimiento extremo, buscar un Mapa de la aplicación que está directamente orientada hacia primitivo de los tipos de valor.jrudolph mencionado GNU Tesoro.
Por cierto, un buen término de búsqueda para que este tema es "histograma".
En lugar de llamar a containsKey() es más rápido sólo para llamar mapa.obtener y comprobar si el valor devuelto es null o no.
Integer count = map.get(word);
if(count == null){
count = 0;
}
map.put(word, count + 1);
¿Estás seguro de que este es un cuello de botella?Se han hecho análisis de rendimiento?
Trate de usar el NetBeans profiler (su libre y construido en la NOTA 6.1) para buscar en puntos de acceso.
Por último, una JVM de actualización (digamos, de 1.5->1.6) es a menudo un hoteles de rendimiento de refuerzo.Incluso una actualización en el número de compilación puede proporcionar un buen rendimiento aumenta.Si se ejecuta en Windows y esta es una clase de servidor de aplicaciones, el uso de servidor en la línea de comandos para utilizar el Servidor de Hotspot de la JVM.En Linux y Solaris máquinas, este es autodetecta.
Hay un par de métodos:
El uso de una Bolsa de alorithm como los conjuntos de contenidos en Google Colecciones.
Crear mutable contenedor que se puede utilizar en el Mapa:
class My{
String word;
int count;
}
Y el uso put("palabra", lo nuevo de Mi("Palabra") );Entonces usted puede comprobar si existe y se incrementan cuando la adición.
Evitar rodar su propia solución usando las listas, porque si te innerloop búsqueda y clasificación, su rendimiento va a apestar.La primera HashMap solución es en realidad bastante rápido, pero una correcta como la que se encuentra en Google Colecciones es probablemente mejor.
Conteo de palabras usando Google Colecciones, se ve algo como esto:
HashMultiset s = new HashMultiset();
s.add("word");
s.add("word");
System.out.println(""+s.count("word") );
El uso de la HashMultiset es bastante elegante, porque una bolsa de algoritmo es justo lo que necesita para contar palabras.
Creo que la solución sería la forma estándar, pero - como se señaló a sí mismo - que no es probablemente la manera más rápida posible.
Usted puede mirar GNU Tesoro.Que es una biblioteca que contiene todo tipo de rápido primitivas Colecciones.Su ejemplo sería el uso de un TObjectIntHashMap que tiene un método adjustOrPutValue que hace exactamente lo que usted desea.
Una variación en la MutableInt enfoque que podría ser incluso más rápido, si un poco de un hack, es el uso de un único elemento de la matriz int:
Map<String,int[]> map = new HashMap<String,int[]>();
...
int[] value = map.get(key);
if (value == null)
map.put(key, new int[]{1} );
else
++value[0];
Sería interesante si pudieras volver a ejecutar las pruebas de rendimiento con esta variación.Podría ser el más rápido.
Editar:El modelo anterior funcionó bien para mí, pero con el tiempo he cambiado a utilizar Tesoro colecciones para reducir el tamaño de la memoria en algunos muy grandes mapas que estaba creando, y como bonus, también fue más rápido.
Una muy buena característica es que el TObjectIntHashMap la clase tiene una sola adjustOrPutValue llamada que, dependiendo de si ya existe un valor en esa clave, o bien poner un valor inicial o incremento el valor existente.Esto es perfecto para el incremento de las:
TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);
Google Colecciones HashMultiset :
- muy elegante para usar
- pero consume CPU y la memoria
Mejor sería disponer de un método como : Entry<K,V> getOrPut(K);
(elegante y de bajo costo)
Un método de calcular el hash y el índice sólo una vez, y luego podemos hacer lo que queremos con la entrada (sustituir o actualizar el valor).
Más elegante:
- tomar un HashSet<Entry>
- extender para que get(K) poner una nueva Entrada si es necesario
De entrada podría ser su propio objeto.
--> (new MyHashSet()).get(k).increment();
"poner la" necesidad "de conseguir" (para asegurar que no se clave duplicada).
Así que directamente hacer un "put",
y si hay un valor anterior, después de hacer una adición:
Map map = new HashMap ();
MutableInt newValue = new MutableInt (1); // default = inc
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
newValue.add(oldValue); // old + inc
}
Si el recuento empieza en 0, a continuación, añadir 1:(o cualesquiera otros valores...)
Map map = new HashMap ();
MutableInt newValue = new MutableInt (0); // default
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
newValue.setValue(oldValue + 1); // old + inc
}
Aviso : Este código no es seguro para subprocesos.El uso de éste para construir, a continuación, utilizar el mapa, no simultáneamente actualización.
Optimización : En un bucle, mantener el valor anterior para convertirse en el nuevo valor de la siguiente bucle.
Map map = new HashMap ();
final int defaut = 0;
final int inc = 1;
MutableInt oldValue = new MutableInt (default);
while(true) {
MutableInt newValue = oldValue;
oldValue = map.put (key, newValue); // insert or...
if (oldValue != null) {
newValue.setValue(oldValue + inc); // ...update
oldValue.setValue(default); // reuse
} else
oldValue = new MutableInt (default); // renew
}
}
Las distintas primitivas contenedores, por ejemplo, Integer son inmutables, así que realmente no hay una manera más concisa para hacer lo que estás preguntando a menos que usted puede hacerlo con algo como AtomicLong.Me puede dar un ir en un minuto y actualización.BTW, Hashtable es una parte de la El Framework De Colecciones.
Yo uso la de Apache Colecciones Perezoso Mapa (para inicializar los valores a 0) y el uso MutableIntegers de Apache Lang como valores en ese mapa.
El costo más grande es tener que ver dos veces el mapa en su método.En el mío que tiene que hacer sólo una vez.Acaba de obtener el valor de (será inicializado en caso de ausencia) y lo incrementa.
El Funcional Java biblioteca TreeMap discbased tiene un update método en el último tronco de la cabeza:
public TreeMap<K, V> update(final K k, final F<V, V> f)
Ejemplo de uso:
import static fj.data.TreeMap.empty;
import static fj.function.Integers.add;
import static fj.pre.Ord.stringOrd;
import fj.data.TreeMap;
public class TreeMap_Update
{public static void main(String[] a)
{TreeMap<String, Integer> map = empty(stringOrd);
map = map.set("foo", 1);
map = map.update("foo", add.f(1));
System.out.println(map.get("foo").some());}}
Este programa imprime "2".
@Vilmantas Baranauskas:Con respecto a esta respuesta, me gustaría comentar que si yo tenía la rep puntos, pero yo no.Yo quería señalar que el Contador de la clase definida NO es thread-safe, ya que no es suficiente sólo sincronizar inc() sin sincronizar el valor de().Otros hilos de llamada valor() no están garantizados para ver el el valor, a menos de un pasa-antes de que se ha establecido relación con la actualización.
No sé qué tan eficiente es, pero el código de abajo, funciona igual de bien.Es necesario definir un BiFunction al principio.Además, usted puede hacer más que simplemente incremento con este método.
public static Map<String, Integer> strInt = new HashMap<String, Integer>();
public static void main(String[] args) {
BiFunction<Integer, Integer, Integer> bi = (x,y) -> {
if(x == null)
return y;
return x+y;
};
strInt.put("abc", 0);
strInt.merge("abc", 1, bi);
strInt.merge("abc", 1, bi);
strInt.merge("abc", 1, bi);
strInt.merge("abcd", 1, bi);
System.out.println(strInt.get("abc"));
System.out.println(strInt.get("abcd"));
}
la salida es
3
1
Si estás usando Eclipse Colecciones, puede utilizar una HashBag.Va a ser el enfoque más eficiente en términos de uso de memoria y que también funcionará bien en términos de velocidad de ejecución.
HashBag está respaldado por un MutableObjectIntMap que almacena primitivo enteros en lugar de Counter objetos.Esto reduce la sobrecarga de la memoria y mejora la velocidad de ejecución.
HashBag proporciona la API de que había necesidad, ya que es un Collection que también permite consultar el número de ocurrencias de un elemento.
He aquí un ejemplo de la Eclipse Colecciones De Kata.
MutableBag<String> bag =
HashBag.newBagWith("one", "two", "two", "three", "three", "three");
Assert.assertEquals(3, bag.occurrencesOf("three"));
bag.add("one");
Assert.assertEquals(2, bag.occurrencesOf("one"));
bag.addOccurrences("one", 4);
Assert.assertEquals(6, bag.occurrencesOf("one"));
Nota: Soy un confirmador de Eclipse Colecciones.
Muy simple, sólo tiene que utilizar la función incorporada en Map.java como seguido
map.put(key, map.getOrDefault(key, 0) + 1);
Dado que una gran cantidad de personas de la búsqueda Java temas para Groovy respuestas, aquí es cómo usted puede hacerlo en Groovy:
dev map = new HashMap<String, Integer>()
map.put("key1", 3)
map.merge("key1", 1) {a, b -> a + b}
map.merge("key2", 1) {a, b -> a + b}
Espero que yo estoy entendiendo tu pregunta correctamente, voy a Java desde Python, así que puedo empatizar con su lucha.
si usted tiene
map.put(key, 1)
te gustaría hacer
map.put(key, map.get(key) + 1)
Espero que esto ayude!
