recorrer ordenado metodos implementar example entre ejemplos diferencia como java optimization collections

ordenado - recorrer un map java



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

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, y luego realizar un conteo de frecuencia de todas las palabras en el archivo. Como 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 de 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 las variables final , pero la diferencia fue insignificante.

Tenga en cuenta que no he perfilado el uso de la 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 ninguna clase 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(); }

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.

Digamos que estoy creando una lista de frecuencia 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 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.

Google Guava es tu amigo ...

... al menos en algunos casos. Ellos tienen este bonito AtomicLongMap . Especialmente agradable porque se trata de valores largos en su mapa.

P.ej

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

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

map.getAndAdd(word, new Long(112));

"poner" necesita "obtener" (para asegurar que no haya una clave duplicada).
Así que directamente hacer 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 y 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 } }

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

Intente usar el perfilador 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.

@Hank Gay

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

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

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 la clave no existe, ponga 1 como valor, de lo contrario sume 1 al valor vinculado a clave . Mas informacion here

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 a 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 usted quiere.

Dado que mucha gente busca temas de Java para las respuestas de Groovy, aquí se explica cómo 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}

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 clave y get . El primero realiza una operación potencialmente muy similar al segundo, ¡así que estás haciendo el mismo trabajo dos veces !

Si observa la API para el mapa, las operaciones de get generalmente devuelven un null cuando 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 podría dar lugar a NullPointerException s. Debería comprobar primero si hay un null .

También tenga en cuenta , y esto es muy importante, que HashMap s puede contener nulls por definición. Así que no todos los null devueltos dicen "no hay tal elemento". En este sentido , containsKey comporta de manera diferente a la get realmente le dice si existe tal elemento. Consulte la API para más detalles.

Para su caso, sin embargo, es posible que no desee distinguir entre un null almacenado y "noSuchElement". Si no desea permitir null s, es posible que prefiera 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 get a una variable final , verificar si hay null y put colocarla con un 1 . La variable debería ser final porque de todas formas 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 != null) { map.put(i + 1); } else { // do something }

Si no quieres confiar en el autoboxing, debes decir algo como map.put(new Integer(1 + i.getValue())); en lugar.

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

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

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 HashMap es en realidad bastante rápida, pero es probable que sea mejor una adecuada como la que se encuentra en Google Collections.

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.

La TreeMap datos TreeMap la biblioteca Java funcional tiene un método de update en el último encabezado de TreeMap :

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

La rotación de memoria puede ser un problema aquí, ya que cada recuadro de un int mayor o igual a 128 provoca 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".

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

No sé qué tan eficiente es, pero el código a continuación también funciona. Debe definir un 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

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.

Puede hacer uso del método computeIfAbsent en la interfaz de 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 un valor asociado, intenta calcular su valor utilizando la función de mapeo dada. En cualquier caso, devuelve el valor actual (existente o computado) asociado con la clave especificada, o nulo si el valor computado 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 LongAdder LongAdder. LongAdder una alta disputa, el rendimiento esperado de esta clase es significativamente mayor que AtomicLong , a expensas de un mayor consumo de espacio.

Si está utilizando Eclipse Collections , puede usar un 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 un objeto MutableObjectIntMap que almacena MutableObjectIntMap primitivas en lugar de objetos Counter . 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 apariciones de un elemento.

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

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 tipo Map 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.

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:

Una variación en el enfoque de MutableInt que podría ser incluso más rápida, si se trata de un truco, es utilizar 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 TObjectIntHashMap es que la clase TObjectIntHashMap tiene una única llamada a adjustOrPutValue 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);

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.

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.