- 浏览: 887955 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
小宇宙_WZY:
膜拜一下大神,解决了我一个大问题,非常感谢 orz
【解惑】深入jar包:从jar包中读取资源文件 -
JKL852qaz:
感谢,遇到相同的问题!
【解惑】深入jar包:从jar包中读取资源文件 -
lgh1992314:
为什么java中调用final方法是用invokevirtua ...
【解惑】Java动态绑定机制的内幕 -
鲁曼1991:
说的都有道理,protected只能被同一级包的类所调用
【解惑】真正理解了protected的作用范围 -
鲁曼1991:
...
【总结】String in Java
作者题记:JDK中有很多算法具有优化的闪光点,值得好好研究。
【java.uti.Arrays】 包含用来操作数组(比如排序和搜索)的各种方法。这篇文章我们就来研究一些大师们写的排序算法。
(1) 基本数据类型数组的排序,如Arrays.sort(int[])等。采用了一种经 过调优的快速排序 。 该算法改编自 Jon L. Bentley 和 M. Douglas McIlroy 合著的 Engineering a Sort Function", Software-Practice and Experience Vol. 23(11) P. 1249-1265 (November 1993)。此算法在许多数据集上提供 n*log(n) 性能,这导致其他快速排序会降低二次型性能。
下面是JDK中调优快速排序算法的源代码:
/** * 将指定范围的整形数组升序排序。 * x[] 待排数组 * off 从数组的第off个元素开始排序 * len 数组长度 */ private static void sort1(int x[], int off, int len) { //优化1:在小规模(size<7)数组中,直接插入排序的效率要比快速排序高。 if (len < 7) { for (int i=off; i<len+off; i++) for (int j=i; j>off && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } //优化2:精心选择划分元素,即枢轴 //如果是小规模数组(size<=7),直接取中间元素作为枢轴 //如果是中等规模数组(7=<size<=40),则在数组首、中、尾三个位置上的数中取中间大小的数作为枢轴 //如果是大规模数组(size>40),则在9个指定的数中取一个伪中数(中间大小的数s) int m = off + (len >> 1); if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); } int v = x[m]; //优化3:每一次枢轴v的划分,都会形成形成一个形如 (<v)* v* (>v)* //阶段一,形成 v* (<v)* (>v)* v* 的数组 int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } //阶段二,将枢轴和与枢轴相等的元素交换到数组中间 int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); //阶段三,递归排序与枢轴不相等都元素区间 if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); }
★ 优化1:在小规模(size<7)数组中,直接插入排序的效率要比快速排序高。
没有一种排序在任何情况下都是最优的《基于比较的内部排序总结 》。 O(N^2)级别的排序看起来似乎比所有先进排序要差的多。但实际上也并非如此,Arrays中的sort()算法就给了我们一个很好的例子。当待排数组规模非常小的时候(JDK中规模的阈值为INSERTIONSORT_THRESHOLD=7),直接插入排序反而要比快排,归并排序要好。
这个道理很简单。数组规模小,简单算法的比较次数不会比先进算法多多少。相反,诸如快排,归并排序等先进算法使用递归操作,所付出的运行代价更高。
★ 优化2:精心选择划分元素,即枢轴。
快排有一种最差的情况,即蜕化成效率最差的起跑排序(见《 交换排序 》)。 导致这种情况产生的主要原因就是枢轴的选择并不能把整个数组划分成两个大致相等的部分。比如对于基本有序的数组,选择第一个元素作为枢轴就会产生这种蜕化。
既然如此,我们可以看看Arryas.sort()是如何为我们选择枢轴的。
● 如果是小规模数组(size<=7),直接取中间元素作为枢轴。
● 如果是中等规模数组(7=<size<=40),则在数组首、中、尾三个位置上的数中取中间大小的数作为枢轴
● 如果是大规模数组(size>40),则在9个指定的数中取一个伪中数(中间大小的数s)
中小规模时,这种取法尽量可以避免数组的较小数或者较大数成为枢轴。值得一提的是大规模的时候,首先在数组中寻找9个数据(可以通过源代码发现这9个数据的位置较为平均的分布在整个数组上);然后每3个数据找中位数;最后在3个中位数上再找出一个中位数作为枢轴。
仔细想想,这种精心选择的枢轴,使得快排的最差情况成为了极小概率事件了。
★ 优化3:根据枢轴v划分,形成一个形如 (<v)* v* (>v)* 的数组
普通快排算法,都是使得枢轴元素移动到数组的较中间位置。枢轴之前的元素全部小于或等于枢轴,之后的元素全部大于枢轴。但与枢轴相等的元素并不能移动到枢轴附近位置。这一点在Arrays.sort()算法中有很大的优化。
我们举个例子来说明Arrays的优化细节 15、93、15、41、6、15、22、7、15、20
第一次枢轴:v=15
阶段一,形成 v* (<v)* (>v)* v* 的数组:
15、15、 7、6、 41、20、22、93、 15、15
我们发现,与枢轴相等的元素都移动到了数组的两边。而比枢轴小的元素和比枢轴大的元素也都区分开来了。
阶段二,将枢轴和与枢轴相等的元素交换到数组中间的位置上
7、6、 15、15、 15、15、 41、20、22、93
阶段三,递归排序与枢轴不相等都元素区间{7、6}和{41、20、22、93}
仔细想想,对于重复元素较多的数组,这种优化无疑能到达更好的效率。
(1) 对象数组的排序,如Arrays.sort(Object[])等。采用了一种经 过修改的归并排序 。 其也有几个优化的闪光点。
下面是JDK中改进归并排序算法的源代码:
/** * 将指定范围的对象数组按自然顺序升序排序。 * src[] 原待排数组 * dest[] 目的待排数组 * low 待排数组的下界位置 * high 待排数组的上界位置 * off 从数组的第off个元素开始排序 */ private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) { int length = high - low; //优化1:规模很小的数组的排序,直接插入排序的效率反而比归并要高。 //规模定在INSERTIONSORT_THRESHOLD=7之内 if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) swap(dest, j, j-1); return; } // 递归排序dest的一半元素并赋值给src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >> 1; mergeSort(dest, src, low, mid, -off); mergeSort(dest, src, mid, high, -off); //优化2:如果低子列表中的最高元素小于高子列表中的最低元素,则忽略合并 //如果需要归并的两端low~(middle-1),middle~high已经有序,即src[mid-1]==src[mid]。 //那么只需要将src的low~high赋值对应的dest即可,无需再归并。 if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } //将src的两个部分合并,并赋值给dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) dest[i] = src[p++]; else dest[i] = src[q++]; } }
★ 优化1: 同上面的快速排序
★ 优化2: 如果低子列表中的最高元素小于高子列表中的最低元素,则忽略合并。 这个优化措施无疑对基本有序序列是极大的效率改进。
评论
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
如给出如下需要排序的序列(假设给序列对应的是对象中的一个字段):24,13,88,33,21,78,2
前半部分排序后13,24,88 后半部分排序后2,21,33,78
初始值:high=7, mid=3, p=0, q=3
当src中只剩下88时,q已经等于7了,这个时候((Comparable)src[p]).compareTo(src[q])<=0中的src[q]为什么不会报ArrayIndexOutOfBoundsException
发表评论
-
NIO
2010-08-05 10:36 0在JDK1.4以前,I/O输入输出处理,我们把它称为旧 ... -
【总结】Java线程同步机制深刻阐述
2010-05-16 10:21 5931全文转载:http://www.iteye ... -
【JDK优化】 Integer 自动打包机制的优化
2010-03-12 19:14 4077我们首先来看一段代码: Integer i=100; In ... -
【总结】Java与字符编码问题详谈
2009-12-30 09:11 9346一、字符集和字符编码方式 计算机只懂得0/1两种信号 ... -
【解惑】 正确理解线程等待和释放(wait/notify)
2009-12-29 13:40 19653对于初学者来说,下面这个例子是一个非常常见的错误。 /** ... -
【解惑】JVM如何理解Java泛型类
2009-12-16 11:08 12222//泛型代码 public class Pair<T& ... -
【解惑】正确的理解this 和 super
2009-12-05 09:46 4413转载: 《无聊 ... -
【解惑】真正理解了protected的作用范围
2009-11-21 18:00 4999一提到访问控 ... -
【总结】String in Java
2009-11-21 17:52 10810作者:每次上网冲杯Java时,都能看到关于String无休无止 ... -
【解惑】真正理解了protected的作用范围
2009-11-16 17:11 585一提到访问控制符protected,即使是初学者 ... -
总结Java标准类库中类型相互转化的方法
2009-11-09 21:57 210组一: ☆ String → byte[ ... -
方法没覆盖住带来的烦恼
2009-11-05 09:18 100Object类是所有类的祖宗,它的equals方法比较的 ... -
【解惑】数组向上转型的陷阱
2009-11-03 11:44 1836问题提出: 有两个类Manager和Em ... -
【总结】java命令解析以及编译器,虚拟机如何定位类
2009-11-01 16:25 5744学Java有些日子了,一直都使用IDE来写程序。这 ... -
【解惑】剖析float型的内存存储和精度丢失问题
2009-10-26 15:10 15821问题提出:12.0f-11.9f=0.10 ... -
【解惑】领略内部类的“内部”
2009-10-19 15:38 3535内部类有两种情况: (1) 在类中定义一个类(私有内部类 ... -
【解惑】深入jar包:从jar包中读取资源文件
2009-10-08 21:13 65418我们常常在代码中读取一些资源文件(比如图片,音乐,文 ... -
【解惑】理解java枚举类型
2009-09-26 09:37 3353枚举类型是JDK5.0的新特征。Sun引进了一个全新的关键字e ... -
编写自己的equals方法
2009-09-20 14:18 129在我的《令人头疼的"相等"关 ... -
【解惑】Java类型间的转型
2009-09-11 16:03 5591★ 基本数据类型间的转换 1、Java要做到平台无关 ...
相关推荐
jdk源码java.util包,所有类解析,包含整体架构及各个类详解
详细介绍了java.util.logging.Logger的用法和结构,对如果扩展Logger起到抛砖引玉的作用!尊重劳动成果,亲下载了要给个评价!
java.util.stream.Stream:Stream 代码示例
这是我在编写struts2中遇到的问题,整理出来,包括截图,希望可以帮到大家
JDK1.5中的线程池(java.util.concurrent.ThreadPoolExecutor)使用
Wrox.Professional.Java.JDK.6.Edition.Jan.2007.rar
最新版windows jdk-11.0.18_windows-x64_bin.zip最新版windows jdk-11.0.18_windows-x64_bin.zip
jdk-11.0.15.1(jdk-11.0.15.1_osx-x64_bin.tar.gz )适用于macOS x64 Compressed Archive系统:是一款Java ...JAVA JDK软件是整个Java的核心,不仅操作很简单,而且JAVA JDK有着实用、稳定、安全、高效的特色功能。
最新版windows jdk-11.0.20_windows-x64_bin.exe最新版windows jdk-11.0.20_windows-x64_bin.exe最新版windows jdk-11.0.20_windows-x64_bin.exe
Java JDK 11.0.8 版本,包含了 windows 和 mac os 的安装包程序,非解压版本
可以用于解决jdk1.6下rt.jar中不支持Base64的问题。资源中包含替代包
Java API 文档 jdk-17.0.2_doc-all
JDK是 Java 语言的软件开发工具包,主要用于移动设备、嵌入式设备上的java应用程序。JDK是整个java开发的核心,它包含了JAVA的运行环境(JVM+Java系统类库)和JAVA工具. JDK是学好Java的第一步。不管是你要学习java...
合适研究底层研发员,但,一般程序员也必须掌握的要点 JDK研究系列--》util.concurrent(java.util part3)
1.打开cmd,cd到jdk的path,本机是:cd C:\Java\jdk6\bin 2.资源javaConcurrentAnimated.jar放在D盘根目录 3.使用java -cp命令: java -cp D:\javaConcurrentAnimated.jar vgrazi.concurrent.samples.launcher....
最新版linux jdk-11.0.20_linux-x64_bin.tar.gz最新版linux jdk-11.0.20_linux-x64_bin.tar.gz最新版linux jdk-11.0.20_linux-x64_bin.tar.gz
主要介绍了出现java.util.ConcurrentModificationException 问题及解决办法的相关资料,需要的朋友可以参考下
jdk-11.0.15.1(jdk-11.0.15.1_linux-aarch64_bin.rpm )适用于Linux ARM 64 RPM Package系统:是一款Java 语言...JAVA JDK软件是整个Java的核心,不仅操作很简单,而且JAVA JDK有着实用、稳定、安全、高效的特色功能。
https://www.oracle.com/java/technologies/downloads/#java11 现在下载JDK 要登录 才可以,这里转一次, 截止2021-12-22,目前jdk-11.0.13是最新版本。
jdk-11.0.15.1(jdk-11.0.15.1_windows-x64_bin.zip)适用于Windows x64 Compressed Archive系统:是一款Java ...JAVA JDK软件是整个Java的核心,不仅操作很简单,而且JAVA JDK有着实用、稳定、安全、高效的特色功能。