在 Java 中向后迭代 SortedSet / SortedMap 的最佳方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/652311/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
The best way to iterate SortedSet / SortedMap in Java backwards
提问by Alexander Temerev
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?
我需要向后遍历 SortedMap 的条目集（这是一个 SortedSet）。我正在编写的代码对性能非常敏感，因为它将每秒从许多地方调用数千次，甚至可能更多。关于以最快的方式做这件事有什么建议吗？
采纳答案by starblue
In Java 1.6 you can use NavigableSet.
在 Java 1.6 中，您可以使用NavigableSet。
回答by Stephan202
You could define a SortedMap such as a TreeMapwith a custom Comparatorthat reverses the sorting order. If you need to iterate in both directions, then maybe it's feasible to keep twocopies of the data structure in memory?
你可以定义一个SortedMap，如一个TreeMap的使用自定义比较是颠倒排列顺序。如果您需要双向迭代，那么在内存中保留数据结构的两个副本可能是可行的？
回答by Peter Lawrey
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.
在以下示例中，向前或向后迭代 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;
}
}
}
Now replace the main loop with and the average time becomes 20,493.
现在用 替换主循环，平均时间变为 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!
现在让我们将其与每次复制（我已经说过这不如仅在更改时复制最佳）进行比较，时间下降到 15,134 ns！
So using NavigableSet could be the slowestof the three options discussed.
因此，使用 NavigableSet 可能是所讨论的三个选项中最慢的。
回答by user1653195
use this before you fill your map :
在填写地图之前使用它：
SortedMap sortedMap = new TreeMap(java.util.Collections.reverseOrder());
