我觉得full JIT后两种方式没有什么区别,但事实是两种方式的时间差是四倍
这里发生了什么
插入排序的实现如下
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
中的差异声明:>
对比<
. 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
在那里。
关于java - 为什么在我实现的插入排序中处理有序数组时,通用版比专用版慢4倍?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58648345/