为什么?为什么?Java处理排序后的数组比没有排序的快?想过没有?-阿里云开发者社区

开发者社区> 沉默王二> 正文

为什么?为什么?Java处理排序后的数组比没有排序的快?想过没有?

简介: 为什么?为什么?Java处理排序后的数组比没有排序的快?想过没有?
+关注继续查看

今天周日,没什么重要的事情要做,于是我早早的就醒来了。看了一会渡边淳一的书,内心逐渐感到平静——心情不佳的时候,书好像是最好的药物。心情平静了,就需要做一些更有意义的事情——逛技术网站,学习精进。


Stack Overflow 是我最喜欢逛的一个网站,它是我 Chrome 浏览器的第一个书签。



里面有很多很多经典的问题,其中一些回答,剖析得深入我心。就比如说这个:“为什么处理排序后的数组比没有排序的快?”


毫无疑问,直观印象里,排序后的数组处理起来就是要比没有排序的快,甚至不需要理由,就好像我们知道“夏天吃冰激凌就是爽,冬天穿羽绒服就是暖和”一样。


但本着“知其然知其所以然”的态度,我们确实需要去搞清楚到底是为什么?


来看一段 Java 代码:


/**
 * @author 沉默王二,一枚有趣的程序员
 */
public class SortArrayFasterDemo {
    public static void main(String[] args) {
        // 声明数组
        int arraySize = 32768;
        int data[] = new int[arraySize];
        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c) {
            data[c] = rnd.nextInt() % 256;
        }
        // !!! 排序后,比没有排序要快
        Arrays.sort(data);
        // 测试
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            // 循环
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128) {
                    sum += data[c];
                }
            }
        }
        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}


这段代码非常简单,我来解释一下:


声明一个指定长度(32768)的数组。


声明一个 Random 随机数对象,种子是 0;rnd.nextInt() % 256 将会产生一个余数,余数的绝对值在 0 到 256 之间,包括 0,不包括 256,可能是负数;使用余数对数组进行填充。


使用 Arrays.sort() 进行排序。


通过 for 循环嵌套计算数组累加后的结果,并通过 System.nanoTime() 计算前后的时间差,精确到纳秒级。


我本机的环境是 Mac OS,内存 16 GB,CPU Intel Core i7,IDE 用的是 IntelliJ IDEA,排序后和未排序后的结果如下:


排序后:2.811633398

未排序:9.41434346


时间差还是很明显的,对吧?未排序的时候,等待结果的时候让我有一种担心:什么时候结束啊?不会结束不了吧?


读者朋友们有没有玩过火炬之光啊?一款非常经典的单机游戏,每一个场景都有一副地图,地图上有很多分支,但只有一个分支可以通往下一关;在没有刷图之前,地图是模糊的,玩家并不知道哪一条分支是正确的。


如果侥幸跑的是一条正确的分支,那么很快就能到达下一关;否则就要往回跑,寻找正确的那条分支,需要花费更多的时间,但同时也会收获更多的经验和声望。


作为一名玩过火炬之光很久的老玩家,几乎每一幅地图我都刷过很多次,刷的次数多了,地图差不多就刻进了我的脑袋,即便是一开始地图是模糊的,我也能凭借经验和直觉找到最正确的那条分支,就省了很多折返跑的时间。


读者朋友们应该注意到了,上面的代码中有一个 if 分支——if (data[c] >= 128),也就是说,如果数组中的值大于等于 128,则对其进行累加,否则跳过。


那这个代码中的分支就好像火炬之光中的地图分支,如果处理器能够像我一样提前预判,那累加的操作就会快很多,对吧?


处理器的内部结构我是不懂的,但它应该和我的大脑是类似的,遇到 if 分支的时候也需要停下来,猜一猜,到底要不要继续,如果每次都猜对,那显然就不需要折返跑,浪费时间。


这就是传说中的分支预测!


我需要刷很多次图才能正确地预测地图上的路线,处理器需要排序才能提高判断的准确率。


计算机发展了这么多年,已经变得非常非常聪明,对于条件的预测通常能达到 90% 以上的命中率。但是,如果分支是不可预测的,那处理器也无能为力啊,对不对?


排序后花费的时间少,未排序花费的时间多,罪魁祸首就在 if 语句上。


if (data[c] >= 128) {

   sum += data[c];

}



数组中的值是均匀分布的(-255 到 255 之间),至于是怎么均匀分布的,我们暂且不管,反正由 Random 类负责。


为了方便讲解,我们暂时忽略掉负数的那一部分,从 0 到 255 说起。


来看经过排序后的数据:


data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...

branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...


      = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT



N 是小于 128 的,将会被 if 条件过滤掉;T 是将要累加到 sum 中的值。


再来看未排序的数据:


data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...

branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...


      = TTNTTTTNTNNTTTN ...  



完全没有办法预测。


对比过后,就能发现,排序后的数据在遇到分支预测的时候,能够轻松地过滤掉 50% 的数据,对吧?是有规律可循的。


那假如说不想排序,又想节省时间,有没有办法呢?


如果你直接问我的话,我肯定毫无办法,两手一摊,一副无奈脸。不过,Stack Overflow 以上帝视角给出了答案。


把:


if (data[c] >= 128) {

   sum += data[c];

}


更换为:


int t = (data[c] - 128) >> 31;

sum += ~t & data[c];


通过位运算消除了 if 分支(并不完全等同),但我测试了一下,计算后的 sum 结果是相同的。


/**
 * @author 沉默王二,一枚有趣的程序员
 */
public class SortArrayFasterDemo {
    public static void main(String[] args) {
        // 声明数组
        int arraySize = 32768;
        int data[] = new int[arraySize];
        Random rnd = new Random();
        for (int c = 0; c < arraySize; ++c) {
            data[c] = rnd.nextInt() % 256;
        }
        // 测试
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            // 循环
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128) {
                    sum += data[c];
                }
            }
        }
        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
        // 测试
        long start1 = System.nanoTime();
        long sum1 = 0;
        for (int i = 0; i < 100000; ++i)
        {
            // 循环
            for (int c = 0; c < arraySize; ++c)
            {
                int t = (data[c] - 128) >> 31;
                sum1 += ~t & data[c];
            }
        }
        System.out.println((System.nanoTime() - start1) / 1000000000.0);
        System.out.println("sum1 = " + sum1);
    }
}

输出结果如下所示:


8.734795196

sum = 156871800000

1.596423307

sum1 = 156871800000



数组累加后的结果是相同的,但时间上仍然差得非常多,这说明时间确实耗在分支预测上——如果数组没有排序的话。


最后,不得不说一句,大神级程序员不愧是大神级程序员,懂得位运算的程序员就是屌。


建议还在读大学的读者朋友多读一读《计算机操作系统原理》这种涉及到底层的书,对成为一名优秀的程序员很有帮助。毕竟大学期间,学习时间充分,社会压力小,能够做到心无旁骛,加油!


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
我的Java开发学习之旅------&gt;Java利用Comparator接口对多个排序条件进行处理
一需求 二实现Comparator接口 三验证排序结果 验证第一条件首先按级别排序级别最高的排在前面 验证第二条如果级别相等那么按工资排序工资高的排在前面 验证第三条如果工资相当则按入职年数排序入职时间最长的排在前面 附录javautilComparator接口源代码 一、需求 假设现在有个如此的需求:需要对一个这样的雇员列表进行排序,排序规则如下: 1、首先级别最高的排在前面, 2、如果级别相等,那么按工资排序,工资高的排在前面, 3、如果工资相当则按入职年数排序,入职时间最长的排在前面。
804 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
9679 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
9100 0
JAVA并发处理经验(四)并行模式与算法5:并行排序模式-希尔排序
一、前言 前面有冒泡排序引入奇偶性的冒泡排序 这里由插入排序,到希尔分组插入排序 二、插入排序 插入排序:将数据插入有序数列,默认第一个数据位有序数列。
862 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
6150 0
+关注
沉默王二
微信搜索「沉默王二」,回复关键字「00」获取硬核计算机基础资料。
1084
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《Nacos架构&原理》
立即下载
《看见新力量:二》电子书
立即下载
云上自动化运维(CloudOps)白皮书
立即下载