更多相关内容...>>数组的完全随机排列算法javascript实现
数组的完全随机排列算法javascript实现
Array.prototype.sort 方法被许多 JavaScript 程序员误用来随机排列数组。最近做的前端星计划挑战项目中,一道实现 blackjack 游戏的问题,就发现很多同学使用了 Array.prototype.sort 来洗牌。就连最近一期 JavaScript Weekly上推荐的一篇文章也犯了同样的错误。
LhX6C6 http://blog.numino.net/
以下就是常见的完全错误的随机排列算法:
At5DK0 http://blog.numino.net/
function shuffle(arr){
pO07g9 http://blog.numino.net/
return arr.sort(function(){
Gm90np http://blog.numino.net/
return Math.random() - 0.5;
9gt8a0 http://blog.numino.net/
});
o9G0OH http://blog.numino.net/
}
1eUujw http://blog.numino.net/
以上代码看似巧妙利用了 Array.prototype.sort 实现随机,但是,却有非常严重的问题,甚至是完全错误。
jODJgh http://blog.numino.net/
证明 Array.prototype.sort 随机算法的错误
25h4wN http://blog.numino.net/
为了证明这个算法的错误,我们设计一个测试的方法。假定这个排序算法是正确的,那么,将这个算法用于随机数组 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],如果算法正确,那么每个数字在每一位出现的概率均等。因此,将数组重复洗牌足够多次,然后将每次的结果在每一位相加,最后对每一位的结果取平均值,这个平均值应该约等于 (0 + 9) / 2 = 4.5,测试次数越多次,每一位上的平均值就都应该越接近于 4.5。所以我们简单实现测试代码如下:
15w33d http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
B3dNCB http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
nK3GZd http://blog.numino.net/
var t = 10000;
b7U1Fb http://blog.numino.net/
for(var i = 0; i < t; i++){
cGO2Y1 http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
cnO7i9 http://blog.numino.net/
sorted.forEach(function(o,i){
Xg49rS http://blog.numino.net/
res[i] += o;
9eXRj8 http://blog.numino.net/
});
YZ3L1O http://blog.numino.net/
}
OcE5s6 http://blog.numino.net/
res = res.map(function(o){
o0vY3U http://blog.numino.net/
return o / t;
52yHts http://blog.numino.net/
});
1496tJ http://blog.numino.net/
console.log(res);
21fvOO http://blog.numino.net/
将上面的 shuffle 方法用这段测试代码在 chrome 浏览器中测试一下,可以得出结果,发现结果并不随机分布,各个位置的平均值越往后越大,这意味着这种随机算法越大的数字出现在越后面的概率越大。
DiHq75 http://blog.numino.net/
为什么会产生这个结果呢?我们需要了解 Array.prototype.sort 究竟是怎么作用的。
xnnDaf http://blog.numino.net/
首先我们知道排序算法有很多种,而 ECMAScript 并没有规定 Array.prototype.sort 必须使用何种排序算法。在这里,有兴趣的同学不妨看一下 JavaScriptCore 的源码实现:
h93sU3 http://blog.numino.net/
排序不是我们今天讨论的主题,但是不论用何种排序算法,都是需要进行两个数之间的比较和交换,排序算法的效率和两个数之间比较和交换的次数有关系。
HB83xE http://blog.numino.net/
最基础的排序有冒泡排序和插入排序,原版的冒泡或者插入排序都比较了 n(n-1)/2 次,也就是说任意两个位置的元素都进行了一次比较。那么在这种情况下,如果采用前面的 sort 随机算法,由于每次比较都有 50% 的几率交换和不交换,这样的结果是随机均匀的吗?我们可以看一下例子:
ovz3H3 http://blog.numino.net/
function bubbleSort(arr, compare){
22Vi78 http://blog.numino.net/
var len = arr.length;
GE7FJB http://blog.numino.net/
for(var i = 0; i < len - 1; i++){
QU4gBY http://blog.numino.net/
for(var j = 0; j < len - 1 - i; j++){
ye5e5J http://blog.numino.net/
var k = j + 1;
2u3tp5 http://blog.numino.net/
if(compare(arr[j], arr[k]) > 0){
5B0YD0 http://blog.numino.net/
var tmp = arr[j];
19ZuJR http://blog.numino.net/
arr[j] = arr[k];
wpyzdw http://blog.numino.net/
arr[k] = tmp;
w3PVjP http://blog.numino.net/
}
jRQHBR http://blog.numino.net/
}
7r0h53 http://blog.numino.net/
}
fE3y0L http://blog.numino.net/
return arr;
FGie73 http://blog.numino.net/
}
712HWJ http://blog.numino.net/
function shuffle(arr){
n1rCOL http://blog.numino.net/
return bubbleSort(arr, function(){
cLDD4q http://blog.numino.net/
return Math.random() - 0.5;
15A8u3 http://blog.numino.net/
});
lVkEF2 http://blog.numino.net/
}
MZDJ5l http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
30rdt6 http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
032dE7 http://blog.numino.net/
var t = 10000;
0NKIY0 http://blog.numino.net/
for(var i = 0; i < t; i++){
XCm9Zc http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
Rg1r6D http://blog.numino.net/
sorted.forEach(function(o,i){
488JZ0 http://blog.numino.net/
res[i] += o;
vztbn7 http://blog.numino.net/
});
75SYM3 http://blog.numino.net/
}
x7Yrux http://blog.numino.net/
res = res.map(function(o){
QDI876 http://blog.numino.net/
return o / t;
F8LVs2 http://blog.numino.net/
});
6YlC5w http://blog.numino.net/
console.log(res);
8iv8cD http://blog.numino.net/
上面的代码的随机结果也是不均匀的,测试平均值的结果越往后的越大。(笔者之前没有复制原数组所以错误得出均匀的结论,已更正于 2016-05-10)
qRNKd6 http://blog.numino.net/
冒泡排序总是将比较结果较小的元素与它的前一个元素交换,我们可以大约思考一下,这个算法越后面的元素,交换到越前的位置的概率越小(因为每次只有50%几率“冒泡”),原始数组是顺序从小到大排序的,因此测试平均值的结果自然就是越往后的越大(因为越靠后的大数出现在前面的概率越小)。
47T0fQ http://blog.numino.net/
我们再换一种算法,我们这一次用插入排序:
YaaK2i http://blog.numino.net/
function insertionSort(arr, compare){
GUpE1V http://blog.numino.net/
var len = arr.length;
6Uj8wW http://blog.numino.net/
for(var i = 0; i < len; i++){
NRpAQu http://blog.numino.net/
for(var j = i + 1; j < len; j++){
vqpJ58 http://blog.numino.net/
if(compare(arr[i], arr[j]) > 0){
Kk361e http://blog.numino.net/
var tmp = arr[i];
mHwjAP http://blog.numino.net/
arr[i] = arr[j];
yhiHo1 http://blog.numino.net/
arr[j] = tmp;
WNAOoA http://blog.numino.net/
}
Z7IJvW http://blog.numino.net/
}
59ehK8 http://blog.numino.net/
}
sh5oul http://blog.numino.net/
return arr;
TA4i9x http://blog.numino.net/
}
JBRmx8 http://blog.numino.net/
function shuffle(arr){
bTGBs4 http://blog.numino.net/
return insertionSort(arr, function(){
ziLDW7 http://blog.numino.net/
return Math.random() - 0.5;
cpQPK1 http://blog.numino.net/
});
MZ75Bb http://blog.numino.net/
}
ni1F7X http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
8h8lUU http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
ZlLXSy http://blog.numino.net/
var t = 10000;
c3suJC http://blog.numino.net/
for(var i = 0; i < t; i++){
rG8TDE http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
2333YV http://blog.numino.net/
sorted.forEach(function(o,i){
VGey29 http://blog.numino.net/
res[i] += o;
ebn7h3 http://blog.numino.net/
});
0gxm5v http://blog.numino.net/
}
6t27gi http://blog.numino.net/
res = res.map(function(o){
34kL0O http://blog.numino.net/
return o / t;
d7Jg8J http://blog.numino.net/
});
3ZMmpK http://blog.numino.net/
console.log(res);
bzUy93 http://blog.numino.net/
由于插入排序找后面的大数与前面的数进行交换,这一次的结果和冒泡排序相反,测试平均值的结果自然就是越往后越小。原因也和上面类似,对于插入排序,越往后的数字越容易随机交换到前面。
m84aJ2 http://blog.numino.net/
所以我们看到即使是两两交换的排序算法,随机分布差别也是比较大。除了每个位置两两都比较一次的这种排序算法外,大多数排序算法的时间复杂度介于 O(n) 到 O(n2) 之间,元素之间的比较次数通常情况下要远小于 n(n-1)/2,也就意味着有一些元素之间根本就没机会相比较(也就没有了随机交换的可能),这些 sort 随机排序的算法自然也不能真正随机。
TV6D4w http://blog.numino.net/
我们将上面的代码改一下,采用快速排序:
WS8QdP http://blog.numino.net/
function quickSort(arr, compare){
FHwY7N http://blog.numino.net/
arr = arr.slice(0);
JMy6e7 http://blog.numino.net/
if(arr.length <= 1) return arr;
MaLxuP http://blog.numino.net/
var mid = arr[0], rest = arr.slice(1);
HeJpjd http://blog.numino.net/
var left = [], right = [];
PAcij9 http://blog.numino.net/
for(var i = 0; i < rest.length; i++){
QZHiM0 http://blog.numino.net/
if(compare(rest[i], mid) > 0){
GsscN4 http://blog.numino.net/
right.push(rest[i]);
oc6D48 http://blog.numino.net/
}else{
FriDIB http://blog.numino.net/
left.push(rest[i]);
Q1TNBq http://blog.numino.net/
}
dpGRq6 http://blog.numino.net/
}
d9qDA1 http://blog.numino.net/
return quickSort(left, compare).concat([mid])
64Q4vX http://blog.numino.net/
.concat(quickSort(right, compare));
9Edj25 http://blog.numino.net/
}
rtHHC0 http://blog.numino.net/
function shuffle(arr){
BxnRcN http://blog.numino.net/
return quickSort(arr, function(){
K6l2X3 http://blog.numino.net/
return Math.random() - 0.5;
d76HRs http://blog.numino.net/
});
T3b1n8 http://blog.numino.net/
}
x10avH http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
8l443H http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
74tIUa http://blog.numino.net/
var t = 10000;
Qmk4m5 http://blog.numino.net/
for(var i = 0; i < t; i++){
jqBu62 http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
QY1wk0 http://blog.numino.net/
sorted.forEach(function(o,i){
92I9kH http://blog.numino.net/
res[i] += o;
fxWSb4 http://blog.numino.net/
});
NU91qx http://blog.numino.net/
}
R8mU85 http://blog.numino.net/
res = res.map(function(o){
bjWiR6 http://blog.numino.net/
return o / t;
31SeUr http://blog.numino.net/
});
cCImtN http://blog.numino.net/
console.log(res);
X9CgmT http://blog.numino.net/
快速排序并没有两两元素进行比较,它的概率分布也不随机。
AKZom7 http://blog.numino.net/
所以我们可以得出结论,用 Array.prototype.sort 随机交换的方式来随机排列数组,得到的结果并不一定随机,而是取决于排序算法是如何实现的,用 JavaScript 内置的排序算法这么排序,通常肯定是不完全随机的。
pnsjEJ http://blog.numino.net/
经典的随机排列
0HklcY http://blog.numino.net/
所有空间复杂度 O(1) 的排序算法的时间复杂度都介于 O(nlogn) 到 O(n2) 之间,因此在不考虑算法结果错误的前提下,使用排序来随机交换也是慢的。事实上,随机排列数组元素有经典的 O(n) 复杂度的算法:
6xcce5 http://blog.numino.net/
function shuffle(arr){
1qs3oA http://blog.numino.net/
var len = arr.length;
z5P8s1 http://blog.numino.net/
for(var i = 0; i < len - 1; i++){
3j3nAd http://blog.numino.net/
var idx = Math.floor(Math.random() * (len - i));
7Xp040 http://blog.numino.net/
var temp = arr[idx];
z1Pn6a http://blog.numino.net/
arr[idx] = arr[len - i - 1];
2oIX3t http://blog.numino.net/
arr[len - i -1] = temp;
9tV7n3 http://blog.numino.net/
}
7RIoXQ http://blog.numino.net/
return arr;
43spYs http://blog.numino.net/
}
z55qQh http://blog.numino.net/
在上面的算法里,我们每一次循环从前 len - i 个元素里随机一个位置,将这个元素和第 len - i 个元素进行交换,迭代直到 i = len - 1 为止。
uYbZQf http://blog.numino.net/
我们同样可以检验一下这个算法的随机性:
lNj77S http://blog.numino.net/
function shuffle(arr){
24yAIS http://blog.numino.net/
var len = arr.length;
NCF592 http://blog.numino.net/
for(var i = 0; i < len - 1; i++){
KZJq4G http://blog.numino.net/
var idx = Math.floor(Math.random() * (len - i));
Ml2xT3 http://blog.numino.net/
var temp = arr[idx];
OJhlJ1 http://blog.numino.net/
arr[idx] = arr[len - i - 1];
Cc4V6a http://blog.numino.net/
arr[len - i -1] = temp;
23eqPY http://blog.numino.net/
}
X2Tz7d http://blog.numino.net/
return arr;
Lv7t0A http://blog.numino.net/
}
WFt975 http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
l2P0VQ http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
044497 http://blog.numino.net/
var t = 10000;
NYyP7C http://blog.numino.net/
for(var i = 0; i < t; i++){
1MTe4Y http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
x4JAkS http://blog.numino.net/
sorted.forEach(function(o,i){
rL5s53 http://blog.numino.net/
res[i] += o;
AKbAjY http://blog.numino.net/
});
LLZl2q http://blog.numino.net/
}
OAa4pR http://blog.numino.net/
res = res.map(function(o){
Xf7VHN http://blog.numino.net/
return o / t;
LY700J http://blog.numino.net/
});
OChWCp http://blog.numino.net/
console.log(res);
cH2aSH http://blog.numino.net/
从结果可以看出这个算法的随机结果应该是均匀的。不过我们的测试方法其实有个小小的问题,我们只测试了平均值,实际上平均值接近只是均匀分布的必要而非充分条件,平均值接近不一定就是均匀分布。不过别担心,事实上我们可以简单从数学上证明这个算法的随机性。
yA8BnI http://blog.numino.net/
随机性的数学归纳法证明
jaGbHt http://blog.numino.net/
对 n 个数进行随机:
9xbAjC http://blog.numino.net/
首先我们考虑 n = 2 的情况,根据算法,显然有 1/2 的概率两个数交换,有 1/2 的概率两个数不交换,因此对 n = 2 的情况,元素出现在每个位置的概率都是 1/2,满足随机性要求。
K4eJ51 http://blog.numino.net/
假设有 i 个数, i >= 2 时,算法随机性符合要求,即每个数出现在 i 个位置上每个位置的概率都是 1/i。
F442fJ http://blog.numino.net/
对于 i + 1 个数,按照我们的算法,在第一次循环时,每个数都有 1/(i+1) 的概率被交换到最末尾,所以每个元素出现在最末一位的概率都是 1/(i+1) 。而每个数也都有 i/(i+1) 的概率不被交换到最末尾,如果不被交换,从第二次循环开始还原成 i 个数随机,根据 2. 的假设,它们出现在 i 个位置的概率是 1/i。因此每个数出现在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1),也是 1/(i+1)。
2X27UE http://blog.numino.net/
综合 1. 2. 3. 得出,对于任意 n >= 2,经过这个算法,每个元素出现在 n 个位置任意一个位置的概率都是 1/n。
jidiuX http://blog.numino.net/
总结
q15s9W http://blog.numino.net/
一个优秀的算法要同时满足结果正确和高效率。很不幸使用 Array.prototype.sort 方法这两个条件都不满足。因此,当我们需要实现类似洗牌的功能的时候,还是应该采用巧妙的经典洗牌算法,它不仅仅具有完全随机性还有很高的效率。
KmHCXc http://blog.numino.net/
除了收获这样的算法之外,我们还应该认真对待这种动手分析和解决问题的思路,并且捡起我们曾经学过而被大多数人遗忘的数学(比如数学归纳法这种经典的证明方法)。
nDy9PQ http://blog.numino.net/
有任何问题欢迎与作者探讨~
u14bEn http://blog.numino.net/
本文转载自:https://www.h5jun.com/post/array-shuffle.html
更多相关内容...>>数组的完全随机排列算法javascript实现

Bug报告 |  免责声明 |  联系我们 |  加入收藏

Copyright © 2006 NuminoStudio(www.numino.net) All Rights Reserved