sábado, 30 de junio de 2012

Java. Maps Iteration/Recorridos sobre mapas

Hola!

Hoy vamos a ver un poco acerca de los distintos métodos de recorrer mapas en java, esto es válido para toda aquella implementación disponible de Map (HashMap, TreeMap, etc...).

Desde la versión 5 de java en adelante, hay nuevas herramientas para recorrer mapas que pueden acelerar el rendimiento de nuestra aplicación de manera notable, como veremos en la conclusión de este artículo. Vamos a ver varios métodos de recorrer mapas, sus ventajas y sus incovenientes.


Imaginemos que tenemos el siguiente mapa:

Map hm = new HashMap();

for (int i=0; i<100000;i++){
    hm.put(i, i);
}
Ahora, vamos a ver distintos métodos de recorridos sobre mapas: 

long ini = System.currentTimeMillis();

// Metodo1

for (Map.Entry entry : hm.entrySet()) {
    System.out.println("Clave: " + entry.getKey() + ", Valor: " + entry.getValue());
}

long fin = System.currentTimeMillis();
long ini2 = System.currentTimeMillis();

//Metodo 2. Iteramos solo sobre claves
for (Integer clave : hm.keySet()) {
    System.out.println("Clave: " + clave);
}

long fin2 = System.currentTimeMillis();
long ini21 = System.currentTimeMillis();

//Metodo2-1.Iteramos sobre valores
for (Integer valor : hm.values()) {
    System.out.println("Valor: " + valor);
}

long fin21 = System.currentTimeMillis();
long ini3 = System.currentTimeMillis();

//Metodo 3
Iterator&gt; entries = hm.entrySet().iterator();

while (entries.hasNext()) {
    Map.Entry entry = entries.next();
    System.out.println("Clave: " + entry.getKey() + ", Valor: " + entry.getValue());
}

long fin3 = System.currentTimeMillis();
long ini4 = System.currentTimeMillis();

// Metodo 4
for (Integer clave : hm.keySet()) {
    Integer valor = hm.get(clave);
    System.out.println("Clave: " + clave + ", Valor: " + valor);
}

long fin4 = System.currentTimeMillis();
System.out.println("tiempo metodo 1: " + (fin-ini));
System.out.println("tiempo metodo 2: " + (fin2-ini2));
System.out.println("tiempo metodo 21: " + (fin21-ini21));
System.out.println("tiempo metodo 3: " + (fin3-ini3));
System.out.println("tiempo metodo 4: " + (fin4-ini4));


Describimos los métodos que hemos implemetado
  • Método 1: Recorremos el mapa usando Map.Entry, el cual está disponible desde Java 1.5. Este objeto nos da acceso tanto a las claves como a los valores, devuelve un Set de Map.Entry el cual recorremos con un for-each al estilo de java 5 y superior.
  • Método 2: Recorremos solo los valores ( o las claves) ya que no nos hace falta el resto de la información.
  • Método 3: Parece redundante con respecto al método 1, introduce un iterador. En la conclusión veremos las ventajas con respecto al método 1, que las hay.
  • Método 4: Recorremos el mapa con un iterador (las claves), y hacemos get para obtener los valores en cada pasada.
Vamos a realizar 10 ejecuciones, obteniendo el tiempo (en milisegundos) medio de ejecución para cada uno de los métodos:
Metodo1 Metodo2 Metodo21 Metodo3 Metodo4
1 2291 1372 1406 2686 2591
2 2107 1428 1495 2650 2637
3 2033 1488 1453 2821 2709
4 2096 1302 1564 2745 2411
5 2070 1503 1391 2477 2610
6 2161 1417 1453 2627 2584
7 2405 1549 1361 2726 2665
8 2345 1418 1403 2776 2536
9 2343 1357 1547 2592 2675
10 2197 1493 1320 2791 2723
Media 2204,8 1432,7 1439,3 2689,1 2614,1
% 100 64,98 65,28 121,97 118,56
Conclusiones En base a los resultados de las pruebas, podemos concluir que:

  1. Si solo nos interesan los valores o las claves del mapa, debemos decantarnos por el método 2, ya que son un 35% mas eficientes que el mejor del resto de métodos.
  2. Si vamos a recorrer el mapa, debemos usar el método 1, ya que como se ve en los resultados es mas eficiente, un 20%, que el resto de recorridos completos.
  3. Si necesitamos borrar elementos del mapa, debemos usar el método 3, ya que el uso de Map.Entry no nos asegura el borrado. Aunque el rendimiento apriori es un 22% peor que el método 1, al ir eliminando en cada pasada del bucle elementos del mapa, este rendimiento mejorará y se equiparará al método 1 (aunque depende de nuestra política de borrado).
  4. Si estamos en un sistema anterior a Java 5, debemos usar el método 4 obligatoriamente. Si usamos herramientas de calidad como FindBugs, detectará este tipo de operaciones como ineficiente, invitándonos a cambiarla. Usamos el método 1 (ojo, como digo solo podemos hacerlo si estamos en 1.5 o superior).
Bueno, pues esto es todo por hoy :) Espero que sea útil y a alguien el sirva! Hasta pronto!!!

No hay comentarios:

Publicar un comentario