- 浏览: 897495 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
小宇宙_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 6002全文转载:http://www.iteye ... -
【JDK优化】 Integer 自动打包机制的优化
2010-03-12 19:14 4189我们首先来看一段代码: Integer i=100; In ... -
【总结】Java与字符编码问题详谈
2009-12-30 09:11 9424一、字符集和字符编码方式 计算机只懂得0/1两种信号 ... -
【解惑】 正确理解线程等待和释放(wait/notify)
2009-12-29 13:40 19756对于初学者来说,下面这个例子是一个非常常见的错误。 /** ... -
【解惑】JVM如何理解Java泛型类
2009-12-16 11:08 12372//泛型代码 public class Pair<T& ... -
【解惑】正确的理解this 和 super
2009-12-05 09:46 4469转载: 《无聊 ... -
【解惑】真正理解了protected的作用范围
2009-11-21 18:00 5086一提到访问控 ... -
【总结】String in Java
2009-11-21 17:52 10977作者:每次上网冲杯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 1887问题提出: 有两个类Manager和Em ... -
【总结】java命令解析以及编译器,虚拟机如何定位类
2009-11-01 16:25 5813学Java有些日子了,一直都使用IDE来写程序。这 ... -
【解惑】剖析float型的内存存储和精度丢失问题
2009-10-26 15:10 16062问题提出:12.0f-11.9f=0.10 ... -
【解惑】领略内部类的“内部”
2009-10-19 15:38 3596内部类有两种情况: (1) 在类中定义一个类(私有内部类 ... -
【解惑】深入jar包:从jar包中读取资源文件
2009-10-08 21:13 65923我们常常在代码中读取一些资源文件(比如图片,音乐,文 ... -
【解惑】理解java枚举类型
2009-09-26 09:37 3422枚举类型是JDK5.0的新特征。Sun引进了一个全新的关键字e ... -
编写自己的equals方法
2009-09-20 14:18 129在我的《令人头疼的"相等"关 ... -
【解惑】Java类型间的转型
2009-09-11 16:03 5679★ 基本数据类型间的转换 1、Java要做到平台无关 ...
相关推荐
10. **并行数组操作**:`java.util.Arrays`类增加了并行版本的排序和搜索方法,利用多核CPU的优势提高性能。 通过这份JDK1.8中文API文档,开发者可以深入学习并掌握以上各项特性,提高开发效率,编写出更加优雅和...
例如,`Arrays.sort(names, String::compareToIgnoreCase)` 使用了`compareToIgnoreCase`方法引用。 4. **Stream API**:Java 8引入了Stream API,用于处理集合数据。它提供了一种声明式、链式编程风格,使得数据...
JDK 1.8对并发库进行了优化,包括Fork/Join框架的改进,`ConcurrentHashMap`的更新,以及`java.util.concurrent.ExecutorService`的`submit()`方法返回`Future`的改进。 ### 9. Type Annotations 类型注解允许在...
Java Development Kit(简称JDK)是Oracle公司发布的用于开发和运行Java应用程序的工具包,它包含Java编译器、Java虚拟机(JVM)、Java类库以及相关的开发工具。在这个特定的压缩包"jdk_8.0.1310.11_64.zip"中,我们...
JDK 1.8是Java编程语言的一个重要版本,它引入了许多新特性、优化和改进,对于开发者来说是一份不可或缺的参考资料。API(Application Programming Interface)是Java的核心,它包含了各种类库、接口和异常,使得...
这通常用于函数式接口,如`Arrays.sort(list, Collections.reverseOrder())`,其中`Collections.reverseOrder()`就是一个方法引用。 8. **Parallel Collectors** Java 8的`Collectors`类提供了并行收集器,如`...
3. **方法引用**:除了lambda表达式,Java 8还提供了方法引用,可以直接引用已有方法作为函数参数,比如`Arrays.sort(list, Integer::compareTo)`。 4. **Stream API**:Stream API是Java 8中的一大亮点,它提供了...
本文将对Java.lang.Object类、Java.lang.Integer类、Java.lang.String类、java.util.Arrays类、java.util.ArrayList类、java.util.LinkedList类、java.util.HashMap类、java.util.HashSet类、java.util....
例如,`Arrays.sort()`可以使用`Comparator.comparing()`方法引用,简化比较逻辑。 3. **接口默认方法** 在JDK 1.8中,接口可以拥有默认方法,用`default`关键字定义。这使得接口可以提供默认实现,而不会破坏现有...
Java开发工具包(Java Development Kit,简称JDK)是Oracle公司发布的用于开发Java应用程序的软件包,它包含了Java运行环境(Java Runtime Environment,JRE)、Java编译器(javac)、Java文档生成器(javadoc)以及...
1. **Fork/Join框架**:JDK 1.8进一步完善了Fork/Join框架,通过`java.util.concurrent.ForkJoinPool`和`java.util.concurrent.RecursiveTask`,可以方便地实现并行计算。 2. **原子变量类**:`java.util....
4. **工具类**:如`java.util`包中的各种实用工具类,如`Collections`、`Arrays`等。 5. **性能优化**:了解如何使用并发工具类,优化内存管理和垃圾回收。 通过深入研究这两个版本的API文档,开发者可以对比不同...
5. **新数据类型**:增加了`byte[]`的便捷操作,如`Arrays.copyOf()`,以及新的`java.nio.file`包,提供了一套更完善的文件I/O操作API。 6. **Fork/Join框架**:这是一个并行编程模型,用于高效地执行大量计算任务...
此外,JDK 1.8还增强了日期和时间API,引入了`java.time`包,替代了之前易用性较差的`java.util.Date`和`java.util.Calendar`。新API更直观,更易于理解和操作,如`LocalDate`、`LocalTime`和`LocalDateTime`等类,...
- `java.util.Arrays#asList()`: 将数组转换为列表。 - `javax.swing.JTable(TableModel)`: 使用`TableModel`作为数据模型的适配器。 - `java.io.InputStreamReader(InputStream)`: 从输入流中读取字符。 - `java.io...
例如,`Arrays.sort()`用于对整型、浮点型或对象数组进行排序,`Arrays.asList()`可以将数组转换为列表,方便进行集合操作。 2. **java.util.Collections**: 类似于`Arrays`,`Collections`提供了针对集合框架的...
**Java JDK 1.8.0_301 安装详解** Java Development Kit(JDK)是Oracle公司提供的用于开发和运行Java应用程序的工具集合。JDK 1.8.0_301是Java 8的一个更新版本,包含了Java编译器、Java虚拟机(JVM)、Java类库...
在JDK 1.7版本中,"util"指的是`java.util`包,它是Java标准库中的核心部分,提供了大量用于日常编程的工具类和接口。这个包的源码对于理解Java内部机制和提高编程技能至关重要。 `java.util`包包含了多种数据结构...
5. **日期与时间API的改进**:Joda-Time库在Java社区中广泛使用,但Java 8引入了新的java.time包,提供了一套全面且易用的日期和时间API,取代了过时的java.util.Date和java.util.Calendar。 6. **新的Optional类**...
List<String> list = Arrays.asList("a", "b", "c"); list.parallelStream().map(String::toUpperCase).collect(Collectors.toList()); ``` 此外,`Fork/Join`框架的优化,提高了并发程序的性能。 八、模块系统...