为什么处理排序的数组比处理未排序的数组慢？(Java的ArrayList.indexOf)
为什么处理排序的数组比处理未排序的数组慢？(Java的ArrayList.indexOf)
提问于 2016-01-27 00:37:25
标题引用了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
*/回答 1
Stack Overflow用户
发布于 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()));
}此排序列表与原始列表(我的计时)具有相同的性能。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35018999
复制相关文章
相似问题