我是如何击败Java自带排序算法的

Java 8 对自带的排序算法进行了很好的优化。对于整形和其他的基本类型, Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个算法是很强大的,可以在很多情况下通用。针对大规模的数组还支持更多变种。我拿自己仓促写的排序算法跟Java自带的算法进行了对比,看看能不能一较高下。这些实验包含了对特殊情况的处理。

首先,我编写了一个经典的快速排序算法。这个算法通过计算样本的平均值来估计整个数组的中心点,然后用作初始枢轴。

我借鉴了一些Java的思路来适当改进我的快速排序,修改后的算法在对小数组进行排序的时候直接调用了插入排序。在这种情况下,我的排序算法和Java的排序算法可以达到相同的运行时间量级。Wild & al指出,如果排序数组有很多的重复数据,标准的快速排序会比双枢轴的快速排序要快。我没有尝试任何字节或汇编级别的分析和优化。在大部分的问题中,我的版本的优化程序都远远不能跟Java系统程序相提并论。

我一直都想测试脑海里的一个简单的排序算法,我称之为Bleedsort。这是一个分布式算法,它通过样本抽样方法对要排序的数组进行分布估计,根据估计结果把数据分配到相应的一个临时的数组里(如图 1 所示),并重写这个初始的数组。这是一个预处理过程,然后再应用其他的排序算法分别进行排序。在我的测试中,我使用了我编写的快速排序版本。如果使用合并排序应该会有更好的结果,因为合并排序被广泛应用在高度结构化的数组中。为了计算简单,我只测试了分布均匀的数据。

Bleedsort在遇到相同的数据的时候都会放到右边,所以此算法在排序相对一致(译者注:会有很多重复数据)的数组的时候表现很差。所以我需要对排序的数组进行样本估计,当重复数很多的情况下应避免使用Bleedsort算法。

我很清楚,Bleedsort算法在内存空间使用方面没办法跟归并排序(快速排序)相提并论,临时数组也比原来的数组要大四倍左右。同时其他的一些分布排序算法,比如Flashsort,在这方面也表现得要好很多。

我运用JMH来作为测试基准。为了简单起见,我就用整形数组进行测试。在1000.000 到10.000.0000 数量级的均匀分布的数组中,我的算法表现的最好。尽管我写的快速排序算法在一定程度上比不过Java自带的算法,但是我的预处理过程很好的弥补了这些不足(调用了我的快速排序的Bleedsort 87ms vs Java 自带算法105ms; 938ms vs 1.144s)

所以,我的这个没有特殊优化的算法程序在这些数据集上要比Java自带算法快大概 10-15% 。

在1000.000数据级,包含 10% 或者 1% 的随机重复数据的均匀增加数据集上,我的算法表现的也不差。

但是,这个算法在只有10.000左右的小二项分布的数据集 (~bin(100,0.5))(译者加:考虑到括号里面是公式代码,并没有修改内部英文括号符号成中文符号)上表现的很差。 在这些数组中,平均下来,出现50这个数字的次数是795.5,而出现40组重复数组的次数是108.4。

同时,在排序1000.0000量级的大数组的时候,这个算法要比 Arrays.sort() 慢两倍左右。这些数组都有很多的重复数据(比如有的大小为1e6的数组里只有450个不同的数值)。

在排序小型的(10.000, 100.000)均匀随机数组下,这个算法表现尚可,但是并不比系统算法更好。

总而言之,在内存不是很紧张的情况下,针对适当的大数据集,我会建议把分布搜索算法做为一个有效的补充选项。

最后,让大家来认识一下二项分布的一些数据集 bin(100, 0.5) 和 bin(1000, 0.5),

这里是两个随机抽样了100个数据的数据集(使用R语言生成)。

原文发布于微信公众号 - java一日一条(mjx_java)

原文发表时间:2016-10-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

3436
来自专栏CSDN技术头条

程序员必须知道的十大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较...

2085
来自专栏智能算法

程序员必须知道的十大基础实用算法及其讲解

出自博客园 原文地址:http://kb.cnblogs.com/page/210687/ 算法一:快速排序算法   快速排序是由东尼·霍尔所发展的一种排序算法...

3838
来自专栏机器之心

入门 | 一文介绍机器学习中基本的数学符号

选自Machine Learning Mastery 作者:Jason Brownlee 机器之心编译 参与:Edison Ke、黄小天 本文介绍了机器学习中的...

3629
来自专栏算法channel

LeetCode实战:动态规划算法是怎么一回事

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

3297
来自专栏游戏开发那些事

【随笔】游戏程序开发必知的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n logn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事...

983
来自专栏ACM算法日常

海战(线段树)- HDU 4027

这一篇是典型的线段树算法,这个算法在日常工作中可能非常少见,因为可以被常规算法所取代,但是在问题达到一定数量级之后,常规算法是很难搞定类似问题的...

1042
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

4926
来自专栏潇涧技术专栏

Python Algorithms - C3 Counting 101

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

934
来自专栏编程之旅

数据结构——最小生成树(C++和Java实现)

快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩...

3434

扫码关注云+社区

领取腾讯云代金券