it-swarm-es.com

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

Espero que esta pregunta no se considere demasiado básica para este foro, pero ya veremos. Me pregunto cómo refactorizar algunos códigos para un mejor rendimiento que se está ejecutando un montón de veces.

Supongamos que estoy creando una lista de frecuencias de palabras, usando un mapa (probablemente un HashMap), donde cada tecla es una cadena con la palabra que se cuenta y el valor es un número entero que se incrementa cada vez que se encuentra un token de la palabra.

En Perl, aumentar ese 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);

Que, por supuesto, se basa en la característica de autoboxing en las nuevas versiones de Java. Me pregunto si puede sugerir una manera más eficiente de incrementar ese valor. ¿Hay incluso buenas razones de rendimiento para evitar el marco de Colecciones y utilizar otra cosa en su lugar?

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

323
gregory

Algunos resultados de la prueba

He recibido muchas buenas respuestas a esta pregunta, gracias a todos, así que decidí realizar algunas pruebas y descubrir cuál es el método 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 conteo de frecuencia de todos los tokens de Word en el archivo. Dado que esto tomó un promedio de solo 3 segundos, hice que realizara el conteo de frecuencia (no la E/S) 10 veces.
  2. cronometró el bucle de 10 iteraciones pero no la operación de E/S y registró el tiempo total tomado (en segundos de reloj) usando esencialmente el método Ian Darwin en el Libro de cocina de Java .
  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, así que le 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)
  • Trove: 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 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 subprocesamiento es un problema, AtomicLong podría ser más atractivo que los otros (no estoy muy seguro). También ejecuté TestForNull con variables final, pero la diferencia fue insignificante.

Tenga en cuenta que no he perfilado el uso de memoria en los diferentes escenarios. Me encantaría saber de cualquier persona 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 clases de terceros. Entonces, a menos que descubra problemas con él, así es como es más probable que vaya.

El código

Aquí está el código crucial 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();

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

Bien, puede ser una pregunta antigua, pero hay una forma más corta con Java 8:

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

Qué hace: si clave no existe, ponga 1 como valor, de lo contrario suma 1 al valor vinculado a clave Más información aquí

167
LE GALL Benoît

Una pequeña investigación en 2016: https://github.com/leventov/Java-Word-count , código fuente de referencia

Los 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: 

42
leventov

Google Guayaba es tu amigo ...

... al menos en algunos casos. Tienen este Niza AtomicLongMap . Especialmente agradable porque está tratando con long as 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); 
32
H6.

@Hank Gay

Como seguimiento a mi propio comentario (bastante inútil): Trove parece ser el camino a seguir. Si, por alguna razón, quisiera mantener el JDK estándar, ConcurrentMap y AtomicLong puede hacer que el código a tiny bit sea 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, todo lo que este enfoque tiene que recomendar es una mayor simpatía con los hilos.

31
Hank Gay

Siempre es una buena idea mirar el Biblioteca de Google Collections 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 tipo mapa para iterar sobre claves/entradas, etc. Internamente, la implementación actualmente utiliza un HashMap<E, AtomicInteger>, por lo que no incurrirá en costos de boxeo.

25
Chris Nokleberg

Debe tener en cuenta el hecho de que su intento original

int count = map.containsKey (Word)? map.get (Word): 0;

contiene dos operaciones potencialmente caras en un mapa, a saber containsKey y get. El primero realiza una operación potencialmente muy similar al segundo, por lo que está haciendo el mismo trabajo dos veces !

Si observa la API para el Mapa, las operaciones get generalmente devuelven null cuando el mapa no contiene el elemento solicitado.

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

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

peligroso, ya que podría producir NullPointerExceptions. Debería verificar primero un null.

Tambien nota, y esto es muy importante, que HashMaps can contiene nulls por definición. Así que no todos los null devueltos dicen "no hay tal elemento". En este sentido, containsKey se comporta de manera diferente de get al decirle si existe tal elemento. Consulte la API para más detalles.

Sin embargo, para su caso, es posible que no desee distinguir entre un null almacenado y "noSuchElement". Si no desea permitir nulls, puede preferir un Hashtable. El uso de una biblioteca de envoltura 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 me olvidé de poner eso al principio, ¡gracias a la función de edición!), La mejor manera de hacerlo de forma nativa es viar a get en una variable final, verifique null y put con 1 . La variable debe ser final porque de todos modos es inmutable. Es posible que el compilador no necesite esta sugerencia, pero es más claro de esa manera.

 final HashMap map = generateRandomHashMap (); 
 final Object Key = fetchSomeKey (); 
 final Integer i = map.get (key); 
 if (i ! = nulo) {
 map.put (i + 1); 
} else {
 // haga algo 
} 

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

21
Aleksandar Dimitrov
Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0);
map.put(key, count + 1);

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

Beneficio:

  • No creando otra clase para int mutable.
  • Código corto
  • Fácil de entender
  • Ninguna excepción de puntero nulo

Otra forma es usar el método de combinación, pero esto es demasiado para simplemente incrementar un valor.

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

Sugerencia: debe preocuparse por la legibilidad del código más que la poca ganancia de rendimiento en la mayoría del tiempo.

20
off99555

Otra forma sería creando un 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 Integer (incluso con Integer.valueOf) no debería ser tanto.

18
Philip Helger

Puede utilizar el método computeIfAbsent en la interfaz Map 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á 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 LongAdder clase. Bajo una alta contención, el rendimiento esperado de esta clase es significativamente mayor que AtomicLong , a expensas de un mayor consumo de espacio.

10
i_am_zero

La rotación de memoria puede ser un problema aquí, ya que cada recuadro de un int mayor o igual a 128 causa una asignación de objeto (consulte Integer.valueOf (int)). Aunque el recolector de basura se ocupa de manera muy eficiente con objetos de corta duración, el rendimiento sufrirá en cierta medida.

Si sabe que el número de incrementos realizados superará en gran medida el número de claves (= palabras en este caso), considere usar un titular int en su lugar. Phax ya presentó el código para esto. Aquí está de nuevo, con dos cambios (la clase del 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".

7
volley

En lugar de llamar a contieneKey (), 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);
5
Glever

Hay un par de enfoques:

  1. Use un algoritmo 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 puedes verificar si existe e incrementar al agregar.

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

Contando palabras usando Google Collections, se ve algo así:



    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 necesitas para contar palabras.

3
tovare

Google Collections HashMultiset:
- 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)

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

Mas elegante:
- toma un HashSet<Entry>
- extiéndalo para que get(K) ponga una nueva entrada si es necesario
- La entrada podría ser tu propio objeto.
-> (new MyHashSet()).get(k).increment();

3
the felis leo

Una variación en el enfoque de MutableInt que podría ser incluso más rápida, si se trata de 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. Podría ser el más rápido.


Edición: el patrón anterior funcionó bien para mí, pero finalmente 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 clase TObjectIntHashMap tiene una única adjustOrPutValue llamada 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);
3

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.

Puede 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 adjustOrPutValue que hace exactamente lo que quiere.

3
jrudolph

¿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 NetBeans (es gratuito y está integrado en NB 6.1) para ver los hotspots.

Finalmente, una actualización JVM (por ejemplo, desde 1.5-> 1.6) es a menudo un refuerzo de rendimiento barato. 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 del Hotspot del servidor. En las máquinas Linux y Solaris, esto se detecta automáticamente.

3
John Wright

"poner" necesita "obtener" (para asegurar que no haya una clave duplicada).
Así que directamente haz un "put",
y si hubiera un valor anterior, entonces haga 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 conteo 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 antiguo 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
  }
}
2
the felis leo

Si está utilizando Eclipse Collections , puede usar una HashBag. Será el enfoque más eficiente en términos de uso de memoria y también tendrá un buen desempeño en términos de velocidad de ejecución.

HashBag está respaldado por una MutableObjectIntMap que almacena entradas primitivas en lugar de Counter objetos. Esto reduce la sobrecarga de memoria y mejora la velocidad de ejecución.

HashBag proporciona la API que necesitaría, ya que es una Collection que también le permite consultar el número de ocurrencias de un elemento.

Aquí hay un ejemplo de Eclipse Collections 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 remitente para las colecciones de Eclipse.

1
Craig P. Motlin

Usaría el Mapa Lazy de Apache Collections (para inicializar los valores a 0) y utilizaría los MutableIntegers de Apache Lang como valores en ese mapa.

El mayor costo es tener que talar el mapa dos veces en tu método. En la mía hay que hacerlo una sola vez. Solo obtenga el valor (se inicializará si está ausente) e incrementarlo.

1
jb.

La estructura de datos TreeMap de Functional Java library tiene un método update en la última cabeza de enlace:

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".

1
Apocalisp

No sé cuán eficiente es, pero el código a continuación también funciona. Debe definir una BiFunction al principio. Además, puedes 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
1
MGoksu

Los diversos envoltorios primitivos, por ejemplo, Integer son inmutables, por lo que realmente no hay una forma más concisa de hacer lo que pides a menos que puedas hacerlo con algo como AtomicLong . Puedo darle una oportunidad en un minuto y actualizar. Por cierto, Hashtable is a parte de Collections Framework .

1
Hank Gay

@Vilmantas Baranauskas: Respecto a esta respuesta, comentaría si tuviera los puntos de repetición, pero no los tengo. Quería señalar que la clase de contador definida allí NO es segura para subprocesos ya que no es suficiente para sincronizar simplemente inc () sin sincronizar valor (). No se garantiza que los otros subprocesos que llaman a value () vean el valor a menos que se haya establecido una relación de suceso antes de la actualización.

1
Alex Miller

Bastante simple, solo use la función incorporada en Map.Java como sigue

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