在Java中向后迭代SortedSet/SortedMap的最佳方法

Question

我需要向后遍历SortedMap的入口集(这是一个SortedSet).我写的代码对性能非常敏感,因为它将在很多地方每秒调用数千次,甚至更多.以最快的方式做任何建议吗？

Answer 1

在Java 1.6中,您可以使用NavigableSet.

Answer 2

在填写地图之前使用此选项:

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

Answer 3

迭代集合的更快方法是获取它的数组副本.这可以向前和向后迭代,而无需创建对象甚至方法调用.缺点是,无论何时更改,您都需要更新它.

在下面的示例中,向前或向后迭代超过1000个元素需要平均1,208 ns.

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

现在替换主循环,平均时间变为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();
}

现在让我们将它与每次复制进行比较(我已经说过它不像仅在更改时复制一样),时间下降到15,134 ns!

因此,使用NavigableSet可能是所讨论的三个选项中最慢的.