一起来洗牌

  • 2019-10-22
  • 0
  • 0

一副扑克牌:

const arr = ["A","2","3","4","5","6","7","8","9","10","J","Q","K","S"]

通过何种方式洗牌才是足够乱的呢?

如果单论“洗牌”二字,很多前端的伙计肯定想都不想就这么写了:

arr.sort(()=> Math.random() - 0.5)

但我这里强调了“足够乱”,是否让你驻足思考下,如何才能证明一个洗牌算法是足够乱的?

“足够乱”说明每张牌出现在任意位置的概率理论上应该是接近的,按照统计学的说法,当独立重复实现足够多的时候,实验数据越接近理论数据。

如何表示某张牌出现在某位置的概率?

有点费解,我们这里换下概念,把“概率”换成“次数”,表述换成:

如何表示实验xx次,某张牌出现在某位置的次数呢?

这好办,如下:

let ret = {
    "A-0": 12, // 表示A出现在0位置12次
    "A-1": 6, // 表示A出现在1位置6次
    "2-1": 9 // 表示2出现在1位置9次
    // ...
}

定好数据结构,我们就可以来实现我们的统计算法了:

function statistics(shuffle, loopCount = 2e5) {
    const arr = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "S"]
    let obj = {}
    let i = 0
    while (i++ < loopCount) {
        let copy = shuffle(arr)
        for (let j = 0; j < arr.length; j++) {
            // 打乱后 j 位置的字符
            let item = copy[j]
            // 以item与j组合 记录出现次数
            const key = `${item}-${j}`
            if (obj[key] === undefined) obj[key] = 0
            obj[key]++
        }
    }
    // 为了看出差异,我们按次数排序,并放到数组中
    return Object.keys(obj)
        .sort((a, b) => obj[b] - obj[a])
        .reduce((acc, cur) => [...acc, { [cur]: obj[cur] }], [])
}

我们把上面那个“洗牌算法”,稍微改造下,以适配这个统计函数:

function shuffle(arr) {
    let copy = [...arr]
    return copy.sort(() => Math.random() - 0.5)
}

测试一波:

// 测试20万次出结果
const ret = statistics(shuffle,  2e5)
console.log(ret)
// [{"A-0":30278},{"S-6":25056},{"S-13":24947},{"A-1":23413}...{"4-13":8261},{"2-12":7133},{"2-13":3190}]

注意到:20万次试验中,A出现在位置0处的次数达30278(概率约为15.14%),而2出现在位置13处的次数仅有3190次(概率约为1.60%),结果明显不均匀。

多重复几次的结果:

[{"A-0":30354},{"S-13":25075},{"S-6":24972},{"A-1":23243}...{"4-13":8115},{"2-12":7175},{"2-13":3182}]
[{"A-0":30421},{"S-13":24925},{"S-6":24847},{"A-1":23298}...{"4-13":8328},{"2-12":7124},{"2-13":2998}]
[{"A-0":30248},{"S-13":24944},{"S-6":24888},{"A-1":23321}...{"4-13":8348},{"2-12":7230},{"2-13":3134}]
[{"A-0":30151},{"S-6":25103},{"S-13":24851},{"A-1":23201}...{"4-13":8125},{"2-12":6950},{"2-13":3226}]
[{"A-0":29966},{"S-6":24984},{"S-13":24941},{"A-1":23181}...{"4-13":8354},{"2-12":7078},{"2-13":3032}]
// ...

我们还是得换种方式实现洗牌算法(Fisher–Yates shuffle):

function shuffle(arr) {
    let copy = [...arr]
    let i = copy.length, j;
    // 倒着循环
    while (i--) {
        // 从[0,i) 随机找一个位置j
        j = parseInt(Math.random() * i);
        // 交换位置i与位置j处的值
        [copy[i], copy[j]] = [copy[j], copy[i]]
    }
    return copy;
}

实现其实很简单,不会写记住就好了,总有你会用到的场合

再测试一波:

// 测试20万次出结果
const ret = statistics(shuffle,  2e5)
console.log(ret)
// [{"3-6":15716},{"Q-2":15715},{"A-12":15686},{"K-10":15681}...{"3-13":15152},{"5-5":15124},{"S-12":15101}]

已经肉眼可见的“均匀”了,我们算下概率:概率最高的A出现在位置13处的概率约为7.89%,而概率最低的6出现在位置10处的位置约为7.54%,差距已经在0.3%左右了。

多重复几次的结果

[{"5-13":15678},{"10-6":15667},{"3-8":15621},{"10-11":15612}...{"10-8":15127},{"8-11":15081},{"7-3":15033}]
[{"4-5":15756},{"6-4":15755},{"K-0":15655},{"4-6":15654}...{"4-0":15069},{"S-7":15006},{"A-0":1}]
[{"A-8":15741},{"8-1":15681},{"4-2":15656},{"K-7":15627}...{"J-9":15112},{"4-1":15100},{"A-0":1}]
[{"K-0":15705},{"5-6":15621},{"Q-2":15614},{"5-3":15596}...{"S-6":15119},{"5-12":15105},{"K-7":15088}]
[{"2-11":15804},{"7-1":15770},{"5-12":15745},{"K-7":15727}...{"S-0":15106},{"7-9":15075},{"K-3":15057}]
// ...

上面的数据,是跑了20w遍测试得到的,而我自己后面在尝试加到100w次试验时,这个差距降到了0.1%左右。

[{"5-12":77936},{"3-9":77495},{"J-13":77464},{"2-12":77445}...{"J-3":76355},{"2-11":76273},{"2-9":76233}]

你说会写测试代码重不重要?

上一篇:    下一篇:

me@ccc5.cc - 衫小寨