随机填充的数据，取其中一半数据求总和，为什么排序后，用时更短？

This topic created in 3484 days ago, the information mentioned may be changed or developed.

Java 测试代码

        for (int loop = 0; loop < 1000; loop++) {
            int[] data = new Random().ints(0, 256).limit(1024).toArray();
            //Arrays.sort(data); // <- 取消这行注释，对比运行结果

            long start = System.nanoTime();
            int sum = 0;
            for (int num : data)
                if (num > 128) sum += num;
            long end = System.nanoTime();

            System.err.printf("%d\t%d\t%d%n", loop, end - start, sum);
        }

基本上可以认为数据源是随机的，为什么排序后再选择其中 50%的数据计算累加和比不排序直接计算要慢？

也就说同样的数据规模、分布情况下，有序集合比无序集合速度更快，为什么呢？

附 Excel 上的折线图：（据说直接贴地址就行了，我预览下貌似并没有用） Excel 中删除了 5-6 个偏离均值较大的数据，使折线图看起来清楚点。

16 replies • 2016-11-01 08:57:32 +08:00

Xs0ul

Oct 30, 2016

不如试试再运行几次，目测 1000 的循环还是略微少了点。对于这么快的一个小程序，其他的因素影响可能更大。

SoloCompany

Oct 30, 2016

我觉得主要是因为 hostspot 是怎么优化你是无法预估的缘故
建议
1 - （最重要）把 sum 代码单独提取成一个方法
2 - 把循环次数增加到 2000 ，抛弃前 1000 次的执行结果，只统计后 1000 次的执行

你会发现其实结果是很接近的

ldbC5uTBj11yaeh5

Oct 30, 2016

http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array

bazingaterry

Oct 30, 2016 via iPhone

@jigloo 竟然是分支预测的原因，真没想到。

Xs0ul

Oct 31, 2016 via Android

@jigloo 学习了

mind3x

Oct 31, 2016 via Android

你的数据集太小，排序的 O(NlogN)时间复杂度相比分支预测省下的时间不显著。把你的随机数组大小改大，至少超过 L1 cache 大小的 2 倍(64K/4*2=32768)， NlogN 的威力会显示出来的。

ntdll

Oct 31, 2016

感谢各位的答复。 @SoloCompany @Xs0ul @mind3x 提的建议，我均用代码试过，其结果基本与我上面贴的一样，无序数据的基准用时在有序数据之后。甚至我尝试将数组长度设置为 2^16 ，随机数分布 2^32 ，只是运行结果用时更长，两者对比依旧无序要慢，而且随着数据规模扩大，无序相比有序数据之间的用时差距也变得更大了。因为结果基本吻合，就不贴代码了。

@jigloo 提到的，看了半天（其实是英语不过关），由于我对硬件上的东西不甚了解。也许真的是这个原因，只不过没有办法去考量。

其实 @jigloo 的链接中也提到了，先是用 C++，随后使用 Java 写同样的代码，其结果基本吻合。各位也可以用自己顺手的语言试试看（ python 、 JavaScript 等脚本语言也可以丢上去），是否也符合这样的规律。即随机集合中选择一半的数据计算和（或者差、积等都可以），是否有序集合会比无序集合快一些。应该一共也没几行代码。

目前从实践来看，分支预测似乎是最合理的解释了。

mind3x

Oct 31, 2016

@gam2046 我去，原来你计时没有把排序的耗时算进来啊，那有什么好比的……

ntdll

Oct 31, 2016

@mind3x 排序时间试过了，`Arrays.sort()`我记得是堆排序，当数据规模较小时，算上排序时间比不排序直接筛选慢，当数据规模扩大后，即使算上排序时间，依旧有序比无序快。这个可以用你顺手的语言测试一下，如果前面的人所说是分支预测的语言，应该不管什么语言都符合这个特征。

mind3x

Oct 31, 2016

@gam2046 这是不可能的，不然要算法时间复杂度分析来做什么。

分支预测和语言无关，是 CPU 的事情。求和的算法复杂度是 O(N)，分支预测成功率不改变这个复杂度，只影响 O(N)外面的常量系数大小，即实际使用时间 k * O(N)的 k 值。

加上排序以后，时间复杂度一下就变成 O(NlogN)，只要 N 稍微大一点，分支预测省的那点时间根本不够看。作为参考，分支预测失败的 penalty 虽然大于 L1 cache 访问时间，但比 L2 cache 访问时间还要小点。

下面是我拿你的代码测的结果，只改了 long start = System.nanoTime() 的位置和生成数组大小

public static void main(String[] args) {
for (int loop = 0; loop < 1000; loop++) {
int[] data = new Random().ints(0, 256).limit(65536).toArray();
long start = System.nanoTime();
Arrays.sort(data); // <- 取消这行注释，对比运行结果

int sum = 0;
for (int num : data)
if (num > 128) sum += num;
long end = System.nanoTime();

System.err.printf("%d\t%d\t%d%n", loop, end - start, sum);
}
}

数组大小为 65536 时，
不排序，最后 10 次运行时间
990 161240 6209232
991 161415 6252012
992 161209 6283107
993 161179 6207880
994 166293 6220546
995 161209 6265626
996 1262967 6236605
997 161269 6199788
998 161101 6244670
999 161109 6239128

排序，最后 10 次运行时间
990 2426694 6264825
991 2553366 6255119
992 2510335 6234796
993 2381404 6253152
994 2500855 6278084
995 2502657 6264268
996 2466819 6235365
997 2455288 6237932
998 2404866 6247138
999 2416455 6199959

数组大小为 2048 时，
不排序，最后 10 次运行时间
990 5229 193642
991 5232 196327
992 5208 198862
993 5223 198061
994 5279 198222
995 5254 196125
996 5249 193539
997 5215 202792
998 5265 193889
999 5227 198240

排序，最后 10 次运行时间
990 89312 194321
991 88549 198128
992 98797 194627
993 88444 191445
994 90597 194749
995 90107 198396
996 89240 195159
997 88931 197912
998 90946 189114
999 89749 191097

事实上排序+求和无论如何也不会快过直接求和。

SoloCompany

Oct 31, 2016

@mind3x 我测试和你得出来的结论完全不一样
主要是循环次数 1000 造成的不确定性太多了，我把循环次数改为 20000 然后只取后 10000 次的结果平均值作为参考
无论怎么测试，顺序还是乱序的，结果几乎无差别（在 java 下）

但是，如果把累加的代码提取为一个方法，和直接内联进行比较，则差异巨大

测试环境
$ /usr/bin/java -version
java version "1.8.0_51"
Java(TM) SE Runtime Environment (build 1.8.0_51-b16)
Java HotSpot(TM) 64-Bit Server VM (build 25.51-b03, mixed mode)

代码
class Untitled {
public static void main(String[] args) throws Exception {
long t = 0;
for (int loop = 0; loop < 20000; loop++) {
int[] data = new java.util.Random().ints(0, 256).limit(1024).toArray();
java.util.Arrays.sort(data); // <- 取消这行注释，对比运行结果

long start = System.nanoTime();
int sum = sum(data);
// int sum = 0;
// for (int num : data)
// if (num > 128) sum += num;
long end = System.nanoTime();
if (loop >= 10000) {
t += (end - start);
}
System.err.printf("%d\t%d\t%d%n", loop, end - start, sum);
}
System.err.printf("%.2f%n", t/10000d);
}

static int sum(int[] data) {
int sum = 0;
for (int num : data)
if (num > 128) sum += num;
return sum;
}
}

测试结果
手动内联（也就是你的原始代码），一万次累加的时间平均值是 36xx ~ 38xx 不等
提取方法（让 jvm 去内联），一万次累加的时间平均值是 117x ~ 12xx 的范围

当然我不否认分支预测所可能引起的副作用，但我认为这个在 java 下的影响是比较小不容易区分的

ntdll

Oct 31, 2016

```java
protected static void test(int[] data, int size) {
int sum = 0;
long start = System.nanoTime();

for (int loop = 0; loop < size; loop++) {
for (int num : data)
if (num < 128) sum += num;
}
long end = System.nanoTime();

System.err.printf("Unsort\t%d\t%d%n", end - start, sum);
}

protected static void testBySort(int[] data, int size) {
int sum = 0;
long start = System.nanoTime();

Arrays.sort(data); // <- 取消这行注释，对比运行结果
for (int loop = 0; loop < size; loop++) {
for (int num : data)
if (num < 128) sum += num;
}
long end = System.nanoTime();

System.err.printf("Sort\t%d\t%d%n", end - start, sum);
}

public static void main(String[] args) {
int[] dataA = new Random().ints(0, 256).limit(65536).toArray();
int[] dataB = new Random().ints(0, 256).limit(65536).toArray();
final int size = 10000; //放大倍率
testBySort(dataA,size);
test(dataB,size);
}
```

这是我的测试代码，因为规模扩大了，我把 sum 改成 long 类型，原来计算大于 128 ，改成计算小于 128 ，在我已经淘汰的老电脑上跑（ CPU E7300 ），多次结果差不多是这样的。之所以没有用同一个数组，是因为我试的时候发现用同一个数组，后测试的那个速度会明显加快（可能由于 JVM 内部有缓存或者其他什么优化之类的情况），因此使用了两组不同的数据源。

我觉得 @mind3x 说的也对。可能这个所谓的分支预测依赖于具体的硬件实现，不同的 CPU 上影响的效果差距较大吧。

无论怎样，这是有一个有意思的测试。

size -> 100000 （数字太大，计时单位为 currentTimeMillis ，其他几组都是 nanoTime ）
Sort 15499 207147800000
Unsort 38274 207932200000

size -> 10000
Sort 1908208198 20769020000
Unsort 3788565998 20795440000

size -> 1000
Sort 191129828 2083522000
Unsort 443468946 2084494000

size -> 100
Sort 27209133 207403100
Unsort 39159150 206028200

size -> 10
Sort 21933511 20871060
Unsort 5386091 20815650

mind3x

Oct 31, 2016

@SoloCompany 大哥，你这算时间根本没把排序放进来啊。

@gam2046 我也是服气了，你后面贴的代码明明只排了一次序，和你之前贴出来的代码根本是两回事，我解释了半天根本是在浪费自己时间。

重新再给你讲一遍：
你在正文里贴的代码，假设外层循环 M 次，每次都随机生成大小是 N 的数组，先排序的时间复杂度是 O(M*N*logN)，不排序的时间复杂度是 O(M*N)。

你在评论里贴的代码，就直接把排序给移到外层循环外面去了！随机数组也只生成一次！！这还比个鬼啊！！！

这种情况下先排序的时间复杂度是 O(M*N+N*logN)，即 O((M+logN)*N)，在 M 远大于 logN 的情况下 logN 可以忽略不计，看成是 O(M*N)，而不排序的时间复杂度也是 O(M*N)，两者所花时间的是同一个**规模**，但先排序因为有常数 k 的优势(CPU 分支预测成功率高)，因而在 M 和 N 都比较大的时候会明显更快一点。我换个说法，先排序花的时间是 k1*O(M*N)，不排序花的时间是 k2*O(M*N)，虽然大头在 O(M*N)，但 k1 < k2 ，你会观察到前者更快。话说回来，你可以从时间上验证，两种做法所花的时间，在 N 一定的情况下，都是随 M 线性增长的，不管 M 或 N 多大，都是快一个固定的比例，不会有时快 1 倍，有时快 5 倍这种情况。你回过头去看上面 O(M*N*logN) vs O(M*N)的情况，相差的倍数会随着 MN 的变大越变越大。

至于你说的"之所以没有用同一个数组，是因为我试的时候发现用同一个数组，后测试的那个速度会明显加快"，当然会啊！因为你先测的先排序，又用同一个数组，后测的那个就直接是在排好序的数据上测了。

mind3x

Oct 31, 2016

上面打错了一句，「你回过头去看上面 O(M*N*logN) vs O(M*N)的情况，相差的倍数会随着 MN 的变大越变越大」应该是「你回过头去看上面 O(M*N*logN) vs O(M*N)的情况，相差的倍数会随着 N 的变大越变越大」

Xs0ul

Oct 31, 2016 via Android

@mind3x 以我的理解，楼主的问题是对数组中大于某个阈值的部分求和，“为什么有序数组比无序数组快”，而不是“我发现了新的算法，排序+求和比求和更快”

mind3x

Nov 1, 2016 via Android

@Xs0ul 你说得对