example - La mejor manera de iterar SortedSet/SortedMap en Java hacia atrás

sorted set java example

Question

Necesito recorrer el conjunto de entradas de SortedMap (que es un SortedSet) hacia atrás. El código que estoy escribiendo es extremadamente sensible al rendimiento, ya que será llamado desde muchos lugares miles de veces por segundo, quizás más. ¿Algún consejo para hacerlo de la manera más rápida?

Answer 1

En Java 1.6 puedes usar NavigableSet .

Answer 2

Podría definir un mapa de clasificación como un TreeMap con un Comparator personalizado que invierta el orden de clasificación. Si necesita iterar en ambas direcciones, ¿tal vez es posible mantener dos copias de la estructura de datos en la memoria?

Answer 3

Una forma más rápida de iterar una colección es tomar una copia de la matriz. Esto se puede iterar hacia adelante y hacia atrás sin crear un objeto o incluso una llamada de método. El inconveniente es que necesita actualizarlo así como su colección cada vez que cambie.

En el siguiente ejemplo, se necesita un promedio de 1,208 ns para iterar más de 1000 elementos hacia adelante o hacia atrás.

import java.util.Comparator;
import java.util.Random;
import java.util.NavigableSet;
import java.util.TreeSet;

/*
Average time for iteration of 1000 elements was 1,208 ns
*/
public class Main {
    public static void main(String... args) {
        doPerfTest(true);
        doPerfTest(false);
    }

    private static void doPerfTest(boolean warmup) {
        NavigableSet<MyData> set = new TreeSet<MyData>(new MyCompataror());
        Random random = new Random();
        for (int i = 0; i < 1000; i++) {
            set.add(new MyData("text-" + random.nextLong(), random.nextInt()));
        }
        MyData[] myDatas = set.toArray(new MyData[set.size()]);
        long start = System.nanoTime();
        final int runs = 500 * 1000;
        for (int i = 0; i < runs; i+=2) {
            // forward iteration
            for (MyData md : myDatas) {

            }
            // reverse iteration
            for (int j = myDatas.length - 1; j >= 0; j--) {
                MyData md = myDatas[j];
            }
        }
        long time = System.nanoTime() - start;
        if (!warmup)
            System.out.printf("Average time for iteration of 1000 elements was %,d ns", time / runs);
    }

    static class MyCompataror implements Comparator<MyData> {
        public int compare(MyData o1, MyData o2) {
            int cmp = o1.text.compareTo(o2.text);
            if (cmp != 0)
                return cmp;
            return o1.value > o2.value ? +1 :
                    o1.value < o2.value ? -1 : 0;
        }
    }

    static class MyData {
        String text;
        int value;

        MyData(String text, int value) {
            this.text = text;
            this.value = value;
        }
    }
}

Ahora reemplace el bucle principal con y el tiempo promedio se convierte en 20,493.

// forward iteration
for(Iterator<MyData> it = set.iterator(); it.hasNext();) {
    MyData md = it.next();
}
// reverse iteration
for(Iterator<MyData> it = set.descendingIterator(); it.hasNext();) {
    MyData md = it.next();
}

Ahora comparemos esto con tomar una copia cada vez (lo que he declarado no es tan óptimo como tomar una copia solo cuando se cambia), ¡el tiempo cae a 15,134 ns!

Por lo tanto, utilizar NavigableSet podría ser la más lenta de las tres opciones discutidas.

Answer 4

Usa esto antes de llenar tu mapa:

SortedMap sortedMap = new TreeMap(java.util.Collections.reverseOrder());