The best way to iterate SortedSet / SortedMap in Java backwards

Question

I need to iterate through SortedMap's entry set (which is a SortedSet) backwards. The code I'm writing is extremely performance-sensitive, as it's going to be called from many places thousands times per second, maybe more. Any advice on doing it the fastest way?

Answer 1

You could define a SortedMap such as a TreeMap with a custom Comparator that reverses the sorting order. If you need to iterate in both directions, then maybe it's feasible to keep two copies of the data structure in memory?

Answer 2

A faster way to iterate a collection is to take an array copy of it. This can be iterated forward and backwards without creating an object or even a method call. The downside is you need to update it as well as your collection whenever it changes.

In the following example, it takes an average of 1,208 ns to iterate over 1000 element either forward or backward.

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

Now replace the main loop with and the average time becomes 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();
}

Now lets compare this with taking a copy every time (which I have stated is not as optimal as taking a copy only when changed), the time drops to 15,134 ns!

So using NavigableSet could be the slowest of the three options discussed.

Answer 3

In Java 1.6 you can use NavigableSet.