某天深夜，我翻开了群聊记录，发现每个歪歪斜斜的气泡上都写着“随机“两个字。我横竖睡不着，仔细看了半夜，才从字缝里看出字来，满屏都写着四个字是“洗牌算法”！
-- 鲁迅
20200814截屏.jpg
解决思路
要实现随机发送n个的需求，可以先将数据使用洗牌算法随机重排，然后选用连续的n个数据即可。
洗牌算法有三种，对应三种思想--“抽牌”、“换牌”、“插牌”，后者都是对前者进行了不同程度上的优化，我们来看看这几种洗牌是怎么样实现的，适用于哪些场景。
一、抽牌法 （ Fisher-Yates Shuffle）
- 思路：从牌堆随机抽出，放入新牌堆。
// js实现写法
const shuffle = arr => {
let copy = [], n = arr.length;
while(n) {
let j = parseInt(Math.random() * n--);
copy.push(...arr.splice(j,1));
}
return copy;
};
- 复杂度：时间复杂度O(n²)（循环+删除移动）、空间复杂度O(n)。
-
图示：
洗牌算法之取牌法.png
二、换牌法 （Knuth-Durstenfeld Shuffle）
- 思路：对上述抽牌法做了改进，无需将牌放入新牌堆，而是与现有牌堆中未抽中的最后一张进行交换位置即可。
// js实现写法
const shuffle = arr => {
for(let i=arr.length-1; i>0; i--){
let j = parseInt(Math.random()*(i+1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
};
- 复杂度：时间复杂度O(n)、空间复杂度O(1)，原地重排
- 适用条件：知道数组长度、非动态增加的数组（因为是从后往前扫）
-
图示：
洗牌算法之换牌法.png
三、 插牌法（Inside-Out Algorithm）
- 思路：对以上的换牌法进行了优化，从前往后扫，随机插入到新牌堆中去。
// js实现写法
const shuffle = arr => {
let copy = [], i = 0;
while(!!arr[i]) {
let j = parseInt(Math.random()*(copy.length+1));
if(!!copy[j]) {
let tmp = copy[j];
copy[j] = arr[i];
copy.push(tmp);
}else {
copy[j] = arr[i];
}
i++;
}
return copy;
};
- 复杂度：时间复杂度O(n)、空间复杂度O(n)
- 适用条件：不知长度，或者动态增加的数组也适用。
-
图示：（可以很明显看出，该算法不会改变原数组）
洗牌算法之插牌法.png
后话：刚发现Python直接就有shuffle()函数，我只想说Python牛逼...
更新：
IMG_20200822_235433.jpg
之后问了当时人，当事人给我讲了具体的场景，比较复杂，经过调研，给出了以下解决方案，请移步到蓄水池抽样-reservoir
本文完
网友评论