数组洗牌算法

《JavaScript框架设计》这本书里接触到洗牌算法:shuffle。

我就是个算法小白……痴。

Fisher–Yates Shuffle, January 14, 2012 这篇文章用JavaScript数组讲解了洗牌算法,并且用D3.js演示各自的重排序效果。

###算法演进

下面的代码均来自该博文。

先来一发粗糙的算法:

低效算法-01
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function shuffle_1(array) {
var copy = [], n = array.length, i;
/* While there remain elements to shuffle… */
while (n) {
/* Pick a remaining element… */
/* 问题就在于,越到最后,数组的空值就越多,就越难以选中 */
i = Math.floor(Math.random() * array.length);
/* If not already shuffled, move it to the new array. */
if (i in array) {
copy.push(array[i]);
delete array[i];
n--;
}
}
return copy;
}

这个算法的问题就是,每次做随机运算时所用的范围,跟剩余的数组长度并不一致。导致最后很难“命中”,于是越来越慢,所需的循环次数往往要大于数组长度 n 。所以,随机过程需要有个可变的范围,其上限应该等于剩余的数组项的个数:

改进的算法-02
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function shuffle_2(array) {
var copy = [], n = array.length, i;
/* While there remain elements to shuffle… */
while (n) {
/* Pick a remaining element… */
/* 优化之处:此时每次生成的随机数,都一定能够对应到一个剩余的数组项 */
i = Math.floor(Math.random() * n--);
/* And move it to the new array. */
/* 新的性能瓶颈,splice方法…… */
copy.push(array.splice(i, 1)[0]);
}
return copy;
}

上面的算法对随机过程进行了改进,可以保证在 n 次循环后就完成随机排序。循环次数下来了,下面该优化每一次循环时的操作了。此时的性能瓶颈在于,数组的splice(i, 1)操作,将下标为i的数组项删除掉,然后把后面的所有项依次向前移动一位。因此复杂度是O(n2)。

为什么一定要移动(n-i)个项呢?如果每次随机过程后,把挑出来的项跟队尾那个项交换一次,不就足够了么,毕竟下一次循环的时候n做了自减运算,数组的尾部就不再变动了。于是有:

改进的算法-03
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function shuffle_3(array) {
var m = array.length, t, i;
/* While there remain elements to shuffle… */
while (m) {
/* Pick a remaining element… */
i = Math.floor(Math.random() * m--);
/* And swap it with the current element. */
t = array[m]; /* 把当前剩余数组的最后一项拿出来 */
array[m] = array[i]; /* 跟选中的那个项换一下位置 */
array[i] = t; /* 这样就只是做了三次赋值运算而已,复杂度是1 */
}
return array;
}

这样一来,整个算法的复杂度就是O(n)啦。

要注意的是,原文中的算法-03是直接在传入的数组上进行操作的。也许先搞一个副本出来,对副本进行操作会更合适:

改进的算法-04
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function shuffle_4(arr) {
/* 改变形参名,在局部作用域内创建arr的副本,要求arr必须严格是个数组 */
var array = arr.slice(0);
var m = array.length, t, i;
/* While there remain elements to shuffle… */
while (m) {
/* Pick a remaining element… */
i = Math.floor(Math.random() * m--);
/* And swap it with the current element. */
t = array[m]; /* 把当前剩余数组的最后一项拿出来 */
array[m] = array[i]; /* 跟选中的那个项换一下位置 */
array[i] = t; /* 这样就只是做了三次赋值运算而已,复杂度是1 */
}
return array;
}

###性能对比
测试用一个较长的数组,n=10000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arr = [];
for(var i=0; i<10000; i++){ arr.push(i); }
console.time('shuffle-01');
shuffle_1(arr);
console.timeEnd('shuffle-01');
console.time('shuffle-02');
shuffle_2(arr);
console.timeEnd('shuffle-02');
console.time('shuffle-04');
shuffle_4(arr);
console.timeEnd('shuffle-04');

在 Chrome 39 中的结果是这样的:

  • shuffle-01: 28.587ms
  • shuffle-02: 14.757ms
  • shuffle-04: 0.120ms
Share