如何在 JavaScript 中对一个数组进行随机化或洗牌
- 根据 JavaScript 引擎对数组进行洗牌
- 测量我们简单算法的随机性
-
使用
Fisher-Yates
Shuffle 算法对一个数组进行洗牌处理 -
使用
Underscore.js
或Lo-Dash
库对一个数组进行洗牌
在本教程中,我们将学习如何在 JavaScript 中对一个数组进行洗牌或随机化处理;在 JavaScript 中洗牌数组的方法有很多,不管是通过实现洗牌算法还是使用一些库中已有的洗牌函数。
洗牌数组就是将其元素随机排列,所以主要看你如何对数组进行一定程度的重新排序或分类。
让我们继续前进,发现随机化或洗牌一个数组的不同方法。
根据 JavaScript 引擎对数组进行洗牌
让我们先实现一个简单的数组洗牌算法,使用 array.sort()
对数组进行排序,但使用 Math.random()-0.5
等式产生的一些随机性,-0.5
确保每次调用算法时,随机值可以是正值或负值。
让我们借助 JavaScript 引擎的力量实现这个简单的算法,并使用 Console.log()
将洗牌后的 Array 打印到控制台。
function shuffleArray(inputArray){
inputArray.sort(()=> Math.random() - 0.5);
}
var demoArray = [1, 3, 5];
shuffleArray(demoArray);
console.log(demoArray);
输出:
[1, 5, 3]
测量我们简单算法的随机性
可以计算出该数组的排列概率,以检查我们实现的算法有多优秀、多随机。
我们来看看如何衡量它的随机性。
- 创建一个字典,对所有的排列组合进行外观统计。
- 创建一个循环,它将运行
1000000 次
,每一次都将增加形成的排列组合的次数。 - 打印所有可能的排列组合的计数,观察它们之间的概率。
这个简单的测量算法可以像下面这样实现。
function shuffleArray(inputArray){
inputArray.sort(()=> Math.random() - 0.5);
}
//counts of the appearances for all possible permutations
var countDic = {
'153': 0,
'135': 0,
'315': 0,
'351': 0,
'531': 0,
'513': 0,
};
//Creating the loop
for( var i = 0; i<1000000; i++){
var arr = [ 1 , 5 , 3];
shuffleArray(arr);
countDic[arr.join('')]++;
}
//Print the counts of all possible permutations
for(var key in countDic){
console.log(`${key}: ${countDic[key]}`);
}
输出:
135: 62256
153: 375832
315: 62976
351: 311865
513: 124518
531: 62553
从上面的输出中,我们可以清楚地看到偏差,因为 135
、315
、531
出现的次数比其他的少得多,所以彼此之间的计数相似。
使用 Fisher-Yates
Shuffle 算法对一个数组进行洗牌处理
这种基于 JavaScript 引擎的简单算法在过去的部分中是不可靠的,但是一个叫做 Fisher-Yates
的伟大算法就其效率和可靠性而言是更好的。
Fisher-Yates
算法背后的思想是以相反的顺序走到数组,并将每个元素与前面的随机元素交换。Fisher-Yates
是一个简单但非常有效和快速的算法。
让我们来实现 Fisher-Yates
算法。
function fisherYatesShuffle(arr){
for(var i =arr.length-1 ; i>0 ;i--){
var j = Math.floor( Math.random() * (i + 1) ); //random index
[arr[i],arr[j]]=[arr[j],arr[i]]; // swap
}
}
var tmpArray = [1, 3, 5];
fisherYatesShuffle(tmpArray);
console.log(tmpArray);
我们来一步步解释一下吧
for(var i =array.length-1 ; i>0 ;i--)
一个 for 循环,将在数组上按相反的顺序行走。Math.floor( Math.random() * (i + 1) )
生成一个范围在 0 和 i 之间的随机指数。[arr[i],arr[j]]=[arr[j],arr[i]]
是用破坏性赋值
语法将元素arr[i]
和arr[j]
相互交换。
输出:
(3) [3, 1, 5]
现在让我们用之前的方法测试 Fisher -Yates
。
//counts of the appearances for all possible permutations
var countDic = {
'153': 0,
'135': 0,
'315': 0,
'351': 0,
'531': 0,
'513': 0,
};
//Creating the loop
for( var i = 0; i<1000000; i++){
var arr = [ 1 , 5 , 3];
fisherYatesShuffle(arr);
countDic[arr.join('')]++;
}
//Print the counts of all possible permutations
for(var key in countDic){
console.log(`${key}: ${countDic[key]}`);
}
输出:
135: 166734
153: 166578
315: 166908
351: 166832
513: 166535
531: 166413
从上面的输出,你可以看到 Fisher-Yates
算法和我们之前实现的简单算法之间的巨大差异,以及 Fisher-Yates
算法的可靠性。
使用 Underscore.js
或 Lo-Dash
库对一个数组进行洗牌
著名的 Underscore.js
库也提供了一个 shuffle 函数,可以直接随机化一个数组,而不需要你写任何算法的实现。
下面我们来看一下 _.shuffle()
方法的使用实例。
首先,我们需要在 HTML 模板里面使用 Cloudflare CDN
导入这个库。
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.15/lodash.min.js"></script>
然后我们使用 _.shuffle()
方法,如。
var tmpUnderscoreArray = [1, 3, 5];
resultArray = _.shuffle(tmpUnderscoreArray);
console.log(resultArray);
输出:
(3) [1, 5, 3]