这是一个创建于 2946 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 个偏离均值较大的数据，使折线图看起来清楚点。
 |
1
Xs0ul 2016-10-30 21:31:44 +08:00
不如试试再运行几次，目测 1000 的循环还是略微少了点。对于这么快的一个小程序，其他的因素影响可能更大。
|
 |
2
SoloCompany 2016-10-30 22:35:25 +08:00
我觉得主要是因为 hostspot 是怎么优化你是无法预估的缘故
建议 1 - （最重要）把 sum 代码单独提取成一个方法 2 - 把循环次数增加到 2000 ，抛弃前 1000 次的执行结果，只统计后 1000 次的执行 你会发现其实结果是很接近的 |
 |
3
ldbC5uTBj11yaeh5 2016-10-30 22:37:45 +08:00  4
|
 |
4
bazingaterry 2016-10-30 22:46:09 +08:00 via iPhone
@jigloo 竟然是分支预测的原因，真没想到。
|
 |
6
mind3x 2016-10-31 10:58:15 +08:00 via Android
你的数据集太小，排序的 O(NlogN)时间复杂度相比分支预测省下的时间不显著。把你的随机数组大小改大，至少超过 L1 cache 大小的 2 倍(64K/4*2=32768)， NlogN 的威力会显示出来的。
|
 |
7
gam2046 OP 感谢各位的答复。 @SoloCompany @Xs0ul @mind3x 提的建议，我均用代码试过，其结果基本与我上面贴的一样，无序数据的基准用时在有序数据之后。甚至我尝试将数组长度设置为 2^16 ，随机数分布 2^32 ，只是运行结果用时更长，两者对比依旧无序要慢，而且随着数据规模扩大，无序相比有序数据之间的用时差距也变得更大了。因为结果基本吻合，就不贴代码了。
@jigloo 提到的，看了半天（其实是英语不过关），由于我对硬件上的东西不甚了解。也许真的是这个原因，只不过没有办法去考量。 其实 @jigloo 的链接中也提到了，先是用 C++，随后使用 Java 写同样的代码，其结果基本吻合。各位也可以用自己顺手的语言试试看（ python 、 JavaScript 等脚本语言也可以丢上去），是否也符合这样的规律。即随机集合中选择一半的数据计算和（或者差、积等都可以），是否有序集合会比无序集合快一些。应该一共也没几行代码。 目前从实践来看，分支预测似乎是最合理的解释了。 |
|
9
gam2046 OP @mind3x 排序时间试过了，`Arrays.sort()`我记得是堆排序，当数据规模较小时，算上排序时间比不排序直接筛选慢，当数据规模扩大后，即使算上排序时间，依旧有序比无序快。这个可以用你顺手的语言测试一下，如果前面的人所说是分支预测的语言，应该不管什么语言都符合这个特征。
|
|
10
mind3x 2016-10-31 13:58:42 +08:00
@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 事实上排序+求和无论如何也不会快过直接求和。 |
|
11
SoloCompany 2016-10-31 14:46:57 +08:00
@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 下的影响是比较小不容易区分的 |
|
12
gam2046 OP ```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 |
|
13
mind3x 2016-10-31 15:12:24 +08:00
@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 的变大越变越大。 至于你说的"之所以没有用同一个数组，是因为我试的时候发现用同一个数组，后测试的那个速度会明显加快"，当然会啊！因为你先测的先排序，又用同一个数组，后测的那个就直接是在排好序的数据上测了。 |
|
14
mind3x 2016-10-31 15:18:06 +08:00
上面打错了一句，「你回过头去看上面 O(M*N*logN) vs O(M*N)的情况，相差的倍数会随着 MN 的变大越变越大」应该是「你回过头去看上面 O(M*N*logN) vs O(M*N)的情况，相差的倍数会随着 N 的变大越变越大」
|
Select Language