java - 为什么在我实现的插入排序中处理有序数组时,普通版比特殊版慢4倍?
问题描述
我觉得full JIT后这两种方法没有什么区别,但事实是这两种方法的时间差是4倍
这里发生了什么
插入排序的实现如下
public class Insert {
public static void special(int[] unsorted) {
for (int now = 1; now < unsorted.length; now++) {
int target = 0;
final int value = unsorted[now];
for (int i = now - 1; i >= 0; i--) {
if (unsorted[i] < value) {
target = i + 1;
break;
}
}
if (target != now) {
System.arraycopy(unsorted, target, unsorted, target + 1, now - target);
unsorted[target] = value;
}
}
}
public static void general(int[] unsorted, boolean isDown, int start, int end) {
for (int now = start + 1; now < end; now++) {
int target = start;
final int value = unsorted[now];
if (isDown) {
for (int i = now - 1; i >= start; i--) {
if (unsorted[i] > unsorted[now]) {
target = i + 1;
break;
}
}
} else {
for (int i = now - 1; i >= start; i--) {
if (unsorted[i] < unsorted[now]) {
target = i + 1;
break;
}
}
}
if (target != now) {
System.arraycopy(unsorted, target, unsorted, target + 1, now - target);
unsorted[target] = value;
}
}
}
}
测试代码如下
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Thread)
public class TestInset {
final int[][] src = new int[100000][5];
final int[][] waitSort = new int[100000][5];
@Setup(Level.Trial)
public void init() {
Random r = new Random();
for (int i = 0; i < src.length; i++) {
src[i] = r.ints(5).toArray();
Arrays.sort(src[i]);
}
}
@Setup(Level.Invocation)
public void freshData() {
for (int i = 0; i < waitSort.length; i++) {
System.arraycopy(src[i], 0, waitSort[i], 0, src[i].length);
}
}
@Benchmark
public int[][] general() {
for (int[] ints : waitSort) {
Insert.general(ints, true, 0, ints.length);
}
return waitSort;
}
@Benchmark
public int[][] special() {
for (int[] ints : waitSort) {
Insert.special(ints);
}
return waitSort;
}
}
测试结果如下
Benchmark Mode Cnt Score Error Units
TestInset.general avgt 25 2934.461 ± 13.148 us/op
TestInset.special avgt 25 682.403 ± 5.875 us/op
测试环境如下
JMH 版本:1.21
虚拟机版本:JDK 1.8.0_212,OpenJDK 64 位服务器虚拟机,25.212-b04
解决方案
该general()
方法isDown = true
将按降序对数组进行排序,而该special()
方法将按升序对数组进行排序。注意if
语句中的区别:>
vs <
。general()
方法与方法isDown = false
相同special()
。
由于src
输入数组按升序排序,因为Arrays.sort()
基准isDown = true
运行最坏情况(输入以相反方向排序),而special()
基准运行最佳情况(输入已排序)。
如果你用isDown
true
和写一个基准测试false
:
@Benchmark
public int[][] generalIsDown() {
for (int[] ints : waitSort) {
Insert.general(ints, true, 0, ints.length);
}
return waitSort;
}
@Benchmark
public int[][] generalIsUp() {
for (int[] ints : waitSort) {
Insert.general(ints, false, 0, ints.length);
}
return waitSort;
}
JDK 11 上的结果是:
Benchmark Mode Cnt Score Error Units
MyBenchmark.generalIsDown avgt 100 2738.320 ± 8.678 us/op
MyBenchmark.generalIsUp avgt 100 697.735 ± 3.902 us/op
MyBenchmark.special avgt 100 690.968 ± 3.559 us/op
再加上一些东西:
- 我不确定在 5 元素排序数组上进行测试是否是一个有意义的测试。您是否尝试在小数组上测试最坏情况下的插入排序性能?
- 我不确定您是否应该在
@Benchmark
方法内循环,这就是其他注释@Measurement
的用途。
推荐阅读
- asp.net-core - 这很令人困惑.. 我正在创建 .net 核心 Web 应用程序,并且可以看到 .NetFramework 支持 .NetCore
- android - 迁移到 Androidx 后出现错误 ':app:compileDebugKotlin' java.lang.reflect.InvocationTargetException
- python - 如何缩短此代码以创建 django 模型,使其在功能方面工作相同
- sql - 如何在 Redshift 中以 YYYY-MON-DD 格式从日期获取周数?
- flutter - 如何更改 Flutter 底部导航栏中的 SVG 图标?
- mysql - 与MYSQL sequelize 中的一对多关系
- java - 如何将此 lambda 代码转换为 Java 中的方法引用?
- java - main_activity.xml 内容显示在 NavigationDrawer 的前面
- operating-system - 单个应用程序实例
- amazon-web-services - Route53 + CloudFront + ELB + Apache2