La forma más eficiente de incrementar un valor de Mapa en Java

Espero que esta pregunta no se considere demasiado básica para este foro, pero ya veremos. Me pregunto cómo refactorizar un código para un mejor rendimiento que se ejecuta muchas veces.

Digamos que estoy creando una lista de frecuencia de palabras, usando un Mapa (probablemente un HashMap), donde cada clave es una Cadena con la palabra que se está contando y el valor es un Entero que se incrementa cada vez que se encuentra un token de la palabra.

En Perl, incrementar dicho valor sería trivialmente fácil:

$map{$word}++;

Pero en Java, es mucho más complicado. Aquí la forma en que lo estoy haciendo actualmente:

int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);

Lo que, por supuesto, se basa en la función de autoboxing en las versiones más recientes de Java. Me pregunto si puede sugerir una forma más eficiente de incrementar dicho valor. ¿Hay incluso buenas razones de rendimiento para evitar el marco de Colecciones y usar algo más en su lugar?

Actualización: he hecho una prueba de varias de las respuestas. Vea abajo.

Algunos resultados de la prueba

He recibido muchas buenas respuestas a esta pregunta, gracias amigos, así que decidí realizar algunas pruebas y descubrir qué método es realmente el más rápido. Los cinco métodos que probé son estos:

• El método "ContainsKey" que presenté en la pregunta
• El método "TestForNull" sugerido por Aleksandar Dimitrov
• El método "AtomicLong" sugerido por Hank Gay
• el método "Trove" sugerido por jrudolph
• El método "MutableInt" sugerido por phax.myopenid.com

Método

Esto es lo que hice ...

1. creó cinco clases que eran idénticas, excepto por las diferencias que se muestran a continuación. Cada clase tuvo que realizar una operación típica del escenario que presenté: abrir un archivo de 10 MB y leerlo, luego realizar un recuento de frecuencia de todos los tokens de palabras en el archivo. Como esto tomó un promedio de solo 3 segundos, tuve que realizar el conteo de frecuencia (no la E / S) 10 veces.
2. cronometró el ciclo de 10 iteraciones pero no la operación de E / S y registró el tiempo total empleado (en segundos de reloj) esencialmente usando el método de Ian Darwin en el Java Cookbook .
3. realizó las cinco pruebas en serie, y luego lo hizo otras tres veces.
4. promedió los cuatro resultados para cada método.

Resultados

Presentaré los resultados primero y el código a continuación para aquellos que estén interesados.

El método ContainsKey fue, como se esperaba, el más lento, por lo que daré la velocidad de cada método en comparación con la velocidad de ese método.

• Contiene clave : 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)
• Trove: 26.313 segundos (1.16 veces más rápido)
• MutableInt: 25.747 segundos (1.19 veces más rápido)

Conclusiones

Parece que solo el método MutableInt y el método Trove son significativamente más rápidos, ya que solo dan un aumento de rendimiento de más del 10%. Sin embargo, si el subproceso es un problema, AtomicLong podría ser más atractivo que los demás (no estoy realmente seguro). También ejecuté TestForNull con finalvariables, pero la diferencia fue insignificante.

Tenga en cuenta que no he perfilado el uso de memoria en los diferentes escenarios. Me alegraría saber de cualquiera que tenga una buena idea de cómo los métodos MutableInt y Trove podrían afectar el uso de la memoria.

Personalmente, considero que el método MutableInt es el más atractivo, ya que no requiere cargar ninguna clase de terceros. Entonces, a menos que descubra problemas con él, esa es la forma en que es más probable que vaya.

El código

Aquí está el código crucial de cada método.

Contiene clave

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();

Trove

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();
}

Ahora hay una forma más corta con Java 8 usando Map::merge.

myMap.merge(key, 1, Integer::sum)

Que hace:

• si la clave no existe, ponga 1 como valor
• de lo contrario, sume 1 al valor vinculado a la clave

Más información aquí .

Un poco de investigación en 2016: https://github.com/leventov/java-word-count , código fuente de referencia

Mejores resultados por método (más pequeño 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

Resultados de tiempo \ espacio:

Google Guava es tu amigo ...

... al menos en algunos casos. Tienen este bonito AtomicLongMap . Especialmente agradable porque se trata de tiempo como valor en su mapa.

P.ej

AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(word);

También es posible agregar más de 1 al valor:

map.getAndAdd(word, 112L); 

@Hank Gay

Como seguimiento de mi propio comentario (bastante inútil): Trove parece el camino a seguir. Si, por cualquier razón, que quería seguir con el JDK estándar, ConcurrentMap y AtomicLong puede hacer que el código de una pequeña agradable poco, aunque tu caso es distinto.

    final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.putIfAbsent("foo", new AtomicLong(0));
    map.get("foo").incrementAndGet();

saldrá 1como el valor en el mapa para foo. Siendo realistas, todo lo que este enfoque tiene para recomendar es una mayor amistad con los hilos.

Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0); // ensure count will be one of 0,1,2,3,...
map.put(key, count + 1);

Y así es como incrementas un valor con un código simple.

Beneficio:

• No es necesario agregar una nueva clase o usar otro concepto de int mutable
• No depender de ninguna biblioteca.
• Fácil de entender exactamente lo que está sucediendo (no demasiada abstracción)

Abajo:

• El mapa hash se buscará dos veces para obtener () y poner (). Por lo tanto, no será el código más eficaz.

Teóricamente, una vez que llama a get (), ya sabe dónde poner (), por lo que no debería tener que buscar nuevamente. Pero la búsqueda en el mapa hash generalmente lleva un tiempo mínimo que puede ignorar este problema de rendimiento.

Pero si usted es muy serio sobre el tema, es un perfeccionista, otra forma es usar el método de combinación, esto es (probablemente) más eficiente que el fragmento de código anterior, ya que (teóricamente) buscará en el mapa solo una vez: (aunque Este código no es obvio a primera vista, es corto y eficaz)

map.merge(key, 1, (a,b) -> a+b);

Sugerencia: debe preocuparse por la legibilidad del código más que por un pequeño aumento de rendimiento en la mayoría de las veces. Si le resulta más fácil entender el primer fragmento de código, úselo. Pero si eres capaz de entender bien el segundo, ¡también puedes hacerlo!

Siempre es una buena idea mirar la Biblioteca de colecciones de Google para este tipo de cosas. En este caso, un Multiset hará el truco:

Multiset bag = Multisets.newHashMultiset();
String word = "foo";
bag.add(word);
bag.add(word);
System.out.println(bag.count(word)); // Prints 2

Existen métodos de tipo Mapa para iterar sobre las claves / entradas, etc. Internamente, la implementación actualmente utiliza a HashMap<E, AtomicInteger>, por lo que no incurrirá en costos de boxeo.

Debe tener en cuenta el hecho de que su intento original

int cuenta = map.containsKey (palabra)? map.get (palabra): 0;

contiene dos operaciones potencialmente caras en un mapa, a saber, containsKeyy get. El primero realiza una operación potencialmente bastante similar a la segunda, ¡así que estás haciendo el mismo trabajo dos veces !

Si observa la API de Map, las getoperaciones generalmente regresan nullcuando el mapa no contiene el elemento solicitado.

Tenga en cuenta que esto hará una solución como

map.put (key, map.get (key) + 1);

peligroso, ya que puede producir NullPointerExceptions. Deberías comprobar por nullprimera vez.

También tenga en cuenta , y esto es muy importante, que HashMaps puede contener nullspor definición. Entonces, no todos los devueltos nulldicen "no existe tal elemento". En este sentido, containsKeyse comporta de forma diferente a partir getde realidad que le dice si hay un elemento de este tipo. Consulte la API para más detalles.

Para su caso, sin embargo, es posible que no desee distinguir entre un almacenado nully "noSuchElement". Si no desea permitir nulls, puede preferir a Hashtable. El uso de una biblioteca de contenedor como ya se propuso 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 olvidé ponerla al principio, gracias a la función de edición!), La mejor manera de hacerlo de forma nativa es getingresar una finalvariable, verificar nully putvolver a ingresarla con a 1. La variable debería ser finalporque es inmutable de todos modos. Es posible que el compilador no necesite esta pista, pero es más claro de esa manera.

mapa final de HashMap = generateRandomHashMap ();
clave de objeto final = fetchSomeKey ();
Integer final i = map.get (clave);
if (i! = null) {
    map.put (i + 1);
} más {
    // hacer algo
}

Si no desea confiar en el autoboxing, debería decir algo como en su map.put(new Integer(1 + i.getValue()));lugar.

Otra forma sería crear un número entero mutable:

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 crear un objeto adicional, pero la sobrecarga en comparación con la creación de un número entero (incluso con Integer.valueOf) no debería ser tanto.

Puede utilizar el método computeIfAbsent en la Mapinterfaz 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 computeIfAbsentverifica si la clave especificada ya está asociada con un valor o no? Si no hay ningún valor asociado, intenta calcular su valor utilizando la función de mapeo dada. En cualquier caso, devuelve el valor actual (existente o calculado) asociado con la clave especificada, o nulo si el valor calculado es nulo.

En una nota al margen, si tiene una situación en la que varios subprocesos actualizan una suma común, puede echar un vistazo a la clase LongAdder. Bajo una alta contención, el rendimiento esperado de esta clase es significativamente mayor que AtomicLong, a expensas de un mayor consumo de espacio.

La rotación de memoria puede ser un problema aquí, ya que cada boxeo de un int mayor o igual a 128 causa una asignación de objeto (ver Integer.valueOf (int)). Aunque el recolector de basura se ocupa de manera muy eficiente con objetos de corta duración, el rendimiento se verá afectado hasta cierto punto.

Si sabe que el número de incrementos realizados superará en gran medida el número de teclas (= palabras en este caso), considere usar un soporte int en su lugar. Phax ya presentó el código para esto. Aquí está de nuevo, con dos cambios (la clase de titular se hizo estática y el valor inicial se estableció 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 necesita un rendimiento extremo, busque una implementación de Mapa que se adapte directamente a los tipos de valores primitivos. jrudolph mencionó GNU Trove .

Por cierto, un buen término de búsqueda para este tema es "histograma".

En lugar de llamar a usesKey (), es más rápido llamar a map.get y verificar si el valor devuelto es nulo o no.

    Integer count = map.get(word);
    if(count == null){
        count = 0;
    }
    map.put(word, count + 1);

¿Estás seguro de que esto es un cuello de botella? ¿Has hecho algún análisis de rendimiento?

Intente usar el generador de perfiles de NetBeans (es gratuito y está integrado en NB 6.1) para ver los puntos de acceso.

Finalmente, una actualización de JVM (digamos de 1.5-> 1.6) es a menudo un refuerzo de rendimiento económico. Incluso una actualización en el número de compilación puede proporcionar buenos aumentos de rendimiento. Si está ejecutando en Windows y esta es una aplicación de clase de servidor, use -server en la línea de comandos para usar la JVM de Hotspot del servidor. En máquinas Linux y Solaris, esto se detecta automáticamente.

Hay un par de enfoques:

1. Use un aloritmo de bolsa como los conjuntos contenidos en Google Collections.

2. Cree un contenedor mutable que pueda usar en el Mapa:

    class My{
        String word;
        int count;
    }

Y use put ("word", new My ("Word")); Luego puede verificar si existe e incrementar al agregar.

Evite lanzar su propia solución usando listas, porque si obtiene una búsqueda y clasificación de bucles internos, su rendimiento apestará. La primera solución de HashMap es realmente bastante rápida, pero una propiedad como la que se encuentra en Google Collections es probablemente mejor.

Contar palabras usando Google Collections, se parece a esto:

    HashMultiset s = new HashMultiset();
    s.add("word");
    s.add("word");
    System.out.println(""+s.count("word") );

Usar el HashMultiset es bastante elegante, porque un algoritmo de bolsa es justo lo que necesita al contar palabras.

Creo que su solución sería la forma estándar, pero, como usted mismo señaló, probablemente no sea la forma más rápida posible.

Puedes mirar GNU Trove . Esa es una biblioteca que contiene todo tipo de colecciones primitivas rápidas. Su ejemplo usaría un TObjectIntHashMap que tiene un método ajustarOrPutValue que hace exactamente lo que desea.

Una variación en el enfoque MutableInt que podría ser aún más rápido, si es un truco, es usar una matriz int de un solo elemento:

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 pudiera volver a ejecutar sus pruebas de rendimiento con esta variación. Puede ser el más rápido.

Editar: El patrón anterior funcionó bien para mí, pero eventualmente cambié para usar las colecciones de Trove para reducir el tamaño de la memoria en algunos mapas muy grandes que estaba creando, y como beneficio adicional, también fue más rápido.

Una característica realmente agradable es que la TObjectIntHashMapclase tiene una sola adjustOrPutValuellamada que, dependiendo de si ya hay un valor en esa clave, pondrá un valor inicial o incrementará el valor existente. Esto es perfecto para incrementar:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);

HashMultiset de Google Collections:
bastante elegante de usar
, pero consume CPU y memoria

Lo mejor sería tener un método como: Entry<K,V> getOrPut(K); (elegante y de bajo costo)

Tal método calculará el hash y el índice solo una vez, y luego podríamos hacer lo que queramos con la entrada (ya sea reemplazar o actualizar el valor).

Más elegante:
- tome un HashSet<Entry>
- extiéndalo para que get(K)coloque una nueva entrada si es necesario
- La entrada podría ser su propio objeto.
->(new MyHashSet()).get(k).increment();

Muy simple, solo use la función incorporada de la Map.javasiguiente manera

map.put(key, map.getOrDefault(key, 0) + 1);

"poner" necesita "obtener" (para garantizar que no haya una clave duplicada).
Entonces, haga un "put" directamente,
y si hubo un valor anterior, entonces agregue:

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 comienza en 0, agregue 1: (o cualquier otro valor ...)

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. Úselo para construir, luego use el mapa, no para actualizarlo simultáneamente.

Optimización: en un bucle, mantenga el valor anterior para convertirse en el nuevo valor del 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
  }
}

Los diversos envoltorios primitivos, por ejemplo, Integerson inmutables, por lo que no hay una forma más concisa de hacer lo que está pidiendo, a menos que pueda hacerlo con algo como AtomicLong . Puedo intentarlo en un minuto y actualizar. Por cierto, Hashtable es parte del marco de colecciones .

Usaría Apache Collections Lazy Map (para inicializar valores a 0) y usaría MutableIntegers de Apache Lang como valores en ese mapa.

El mayor costo es tener que buscar el mapa dos veces en su método. En el mío tienes que hacerlo solo una vez. Simplemente obtenga el valor (se inicializará si está ausente) e increméntelo.

La estructura de datos de la biblioteca Java funcionalTreeMap tiene un updatemétodo en la última cabecera del tronco:

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, comentaría si tuviera los puntos de representación, pero no los tengo. Quería señalar que la clase Counter definida allí NO es segura para subprocesos ya que no es suficiente simplemente sincronizar inc () sin sincronizar el valor (). No se garantiza que otros hilos que llamen al valor () vean el valor a menos que se haya establecido una relación anterior con la actualización.

No sé qué tan eficiente es, pero el código a continuación también funciona. Debe definir un BiFunctional principio. Además, puede hacer más que solo incrementar 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 usa Eclipse Collections , puede usar a HashBag. Será el enfoque más eficiente en términos de uso de memoria y también funcionará bien en términos de velocidad de ejecución.

HashBagestá respaldado por un MutableObjectIntMapque almacena entradas primitivas en lugar de Counterobjetos. Esto reduce la sobrecarga de memoria y mejora la velocidad de ejecución.

HashBag proporciona la API que necesitarías ya que es un Collection que también te permite consultar la cantidad de ocurrencias de un elemento.

Aquí hay un ejemplo del Kata de Eclipse Collections .

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 committer para Eclipse Collections.

Sugiero usar Java 8 Map :: compute (). También considera el caso cuando una clave no existe.

Map.compute(num, (k, v) -> (v == null) ? 1 : v + 1);

Dado que mucha gente busca en los temas de Java las respuestas de Groovy, así es como 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}

La manera simple y fácil en Java 8 es la siguiente:

final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.computeIfAbsent("foo", key -> new AtomicLong(0)).incrementAndGet();

Espero entender tu pregunta correctamente, estoy llegando a Java desde Python para poder empatizar con tu lucha.

si usted tiene

map.put(key, 1)

tu harías

map.put(key, map.get(key) + 1)

¡Espero que esto ayude!