标题引用了Why is it faster to process a sorted array than an unsorted array?
这也是一种分支预测效果吗?注意:在这里,排序数组的处理速度更慢!
考虑以下代码:
private static final int LIST_LENGTH = 1000 * 1000;
private static final long SLOW_ITERATION_MILLIS = 1000L * 10L;
@Test
public void testBinarySearch() {
Random r = new Random(0);
List<Double> list = new ArrayList<>(LIST_LENGTH);
for (int i = 0; i < LIST_LENGTH; i++) {
list.add(r.nextDouble());
}
//Collections.sort(list);
// remove possible artifacts due to the sorting call
// and rebuild the list from scratch:
list = new ArrayList<>(list);
int nIterations = 0;
long startTime = System.currentTimeMillis();
do {
int index = r.nextInt(LIST_LENGTH);
assertEquals(index, list.indexOf(list.get(index)));
nIterations++;
} while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
long duration = System.currentTimeMillis() - startTime;
double slowFindsPerSec = (double) nIterations / duration * 1000;
System.out.println(slowFindsPerSec);
...
}
这将在我的机器上打印出大约720的值。
现在,如果我激活集合排序调用,该值将下降到142。为什么?!?
结果是决定性的,如果我增加迭代次数/时间,它们不会改变。
Java版本是1.8.0_71 (Oracle,64位),运行在Windows10下,在Eclipse Mars中进行JUnit测试。
更新
似乎与连续内存访问(按顺序访问双对象与按随机顺序访问)有关。对于我来说,当数组长度大约为10k或更少时,这种效果就会消失。
感谢assylias提供the results
/**
* Benchmark Mode Cnt Score Error Units
* SO35018999.shuffled avgt 10 8.895 ± 1.534 ms/op
* SO35018999.sorted avgt 10 8.093 ± 3.093 ms/op
* SO35018999.sorted_contiguous avgt 10 1.665 ± 0.397 ms/op
* SO35018999.unsorted avgt 10 2.700 ± 0.302 ms/op
*/
发布于 2016-01-27 01:21:42
我认为我们看到了内存缓存未命中的影响:
创建未排序列表时
for (int i = 0; i < LIST_LENGTH; i++) {
list.add(r.nextDouble());
}
所有的双精度最有可能被分配在一个连续的内存区。迭代遍历它将产生很少的缓存未命中。
另一方面,在排序列表中,引用以一种混乱的方式指向内存。
现在,如果您创建了一个具有连续内存的排序列表:
Collection.sort(list);
List<Double> list2 = new ArrayList<>();
for (int i = 0; i < LIST_LENGTH; i++) {
list2.add(new Double(list.get(i).doubleValue()));
}
此排序列表与原始列表(我的计时)具有相同的性能。
https://stackoverflow.com/questions/35018999
复制相似问题