刚刚开刷红宝书,好奇测了一下发现 Java 实现的选择排序比插入排序速度快,个人推测是 JVM 上交换位置操作比对比操作消耗大。 当然还是担心是我自己粗心导致的,请大家帮忙看下, tldr 的可以直接看最后面的运行结果。
public static void sort(Comparable[] a) {
int min = 0;
for (int i = 0; i < a.length; i++) {
min = i;
for (int j = i + 1; j < a.length; j++) {
if (less(a[j], a[min])) {
min = j;
}
}
exch(a, i, min);
}
}
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = i + 1; j > 0; j--) {
if (less(a[j], a[j-1])) {
exch(a, j, j - 1);
} else {
break;
}
}
}
}
public static void timeTest(int n, int repeat) {
double selectionSortTime = 0;
long compareInSelection = 0;
long swapInSelection = 0;
double bubbleSortTime = 0;
double insertionSortTime = 0;
long compareInInsertion = 0;
long swapInInsertion = 0;
for (int i = 0; i < repeat; i++) {
Integer[] arr0 = genRandomArray(n);
Integer[] arr1 = copyArray(arr0);
Integer[] arr2 = copyArray(arr0);
Stopwatch stopwatch0 = new Stopwatch();
SelectionSort.sort(arr0);
selectionSortTime += stopwatch0.elapsedTime();
compareInSelection += SelectionSort.compare;
swapInSelection += SelectionSort.swap;
Stopwatch stopwatch1 = new Stopwatch();
BubbleSort.sort(arr1);
bubbleSortTime += stopwatch1.elapsedTime();
Stopwatch stopwatch2 = new Stopwatch();
InsertionSort.sort(arr2);
insertionSortTime += stopwatch2.elapsedTime();
compareInInsertion += InsertionSort.compare;
swapInInsertion += InsertionSort.swap;
}
StdOut.printf("algorithm avg compare swap\n");
StdOut.printf("SelectionSort %f %d %d\n", selectionSortTime / repeat, compareInSelection / repeat, swapInSelection / repeat);
StdOut.printf("BubbleSort %f \n", bubbleSortTime / repeat);
StdOut.printf("InsertionSort %f %d %d\n", insertionSortTime / repeat, compareInInsertion / repeat, swapInInsertion / repeat);
}
algorithm avg compare swap
SelectionSort 0.001032 499500 1000
BubbleSort 0.001788
InsertionSort 0.001293 250824 249831
1
davie 2019-07-02 15:27:43 +08:00 via Android
数据量多大?
|
3
davie 2019-07-02 15:42:00 +08:00 via Android
随机性呢?
|
4
yusuzhan OP @davie 随机性用的红宝书里提供的库,描述是 uniformly
``` /** * Rearranges the elements of the specified array in uniformly random order. * * @param a the array to shuffle * @throws IllegalArgumentException if {@code a} is {@code null} */ public static void shuffle(Object[] a) { validateNotNull(a); int n = a.length; for (int i = 0; i < n; i++) { int r = i + uniform(n-i); // between i and n-1 Object temp = a[i]; a[i] = a[r]; a[r] = temp; } } ``` |
6
AmmeLid 2019-07-02 15:53:16 +08:00
用数组来做插入排序,还要考虑插入后数据移动的开销吧。
|
7
wutiantong 2019-07-02 16:00:32 +08:00
很可能是 exch 引入了额外的开销
|
8
yusuzhan OP @wutiantong 真没啥,书里原文
``` private static void exch(Comparable[] a, int i, int j) { swap++; final Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; } ``` |
9
xuwei0056 2019-07-02 16:07:19 +08:00
创建 Comparable 的开销大?
|
10
jmc891205 2019-07-02 16:08:10 +08:00
你再测一下 less 和 exch 的速度好了
|
11
wutiantong 2019-07-02 16:14:53 +08:00
|
12
lance6716 2019-07-02 16:19:54 +08:00 via Android
我咋记得插入排序不是这么写…一个一个往后移,而不是交换
|
13
yusuzhan OP |
14
yusuzhan OP @xuwei0056 用的 Integer 数组,创建的开销没算, 只统计的排序的速度。刚才看了一下, 确实是 exch 速度比 less 慢导致的。
|
15
wizardoz 2019-07-02 17:24:27 +08:00
选择排序移动很少,插入排序有很多移动
算法书上的时间复杂度是以比较次数来计的。 |
16
littlewing 2019-07-03 02:27:39 +08:00 via Android
复杂度低并不代表任何情况下速度就快,因为复杂度算得是极限
|
17
capljf 2019-12-12 19:53:46 +08:00
我的 mac pro 上也是选择排序比插入排序快,100 ~ 10000 个 double 随机数,用 StdRandom.shuffle 打乱了。100 ~ 10000 次都试了,都是选择比插入快。搞得我检查了好几遍代码是不是写反了,但代码确实没问题。还得继续找原因
|
18
capljf 2019-12-12 19:58:26 +08:00
我猜是插入排序没有做优化,因为每次比较都做了 exch,exch 比较耗时,我去按书上的优化一下,将较大元素都往右移动而不是总是 exch。访问数组的次数能减少一半
|
19
capljf 2019-12-12 21:07:28 +08:00
为啥回复不了了,提示验证手机号
|
20
capljf 2019-12-12 21:10:17 +08:00
好像我的回复有些词被 block 了。简单说下,刚刚是我的代码写得有问题,插入是比选择快的,优化后的代码 swap 次数确实比优化前少一半左右
|