投身烈火
Keep Walking

一场抽奖引发的扯淡

起因

今年年会的抽奖算法写的实在是太烂。整个整个抽奖流程大概是这样的:每次抽奖是抽奖人先说开始,于是开始播放动画遍历队列,然后过一段时间,抽奖人说停,遍历结束,停在哪儿谁就中奖。可是不用看代码我都知道,每次抽奖时没有对队列进行随机排序。因为有动画效果,遍历的速度不可能很快,抽奖人又不会等很久才说停,所以排在后面的怎么可能中奖(我就是排在后面的)……于是我开始思考,如果是我,我会怎么写这个抽奖的程序呢。

实现

抽奖可以概括的描述为:从一个指定的集合中,随机选出若干个元素。

ok,用编程语言翻译翻译:

1
2
3
4
5
6
7
8
9
10
function draw(list = [], number = 0) {
list = list.concat()
let result = []
while (number--) {
result.push(list.splice(Math.floor(Math.random()*list.length), 1)[0])
}
return result
}
let drawResult = draw(['刘能', '谢大脚', '王长贵', '赵四', '刘英', '李大国', '赵玉田', '刘大脑袋', '王天来', '王大拿', '李秋歌'], 3)
console.log(`中奖者为:${drawResult.join(',')}`)

质疑

程序是写好了,但是这个程序真的能保证公平公正的抽奖吗?从上面的程序中一眼就能看出来,我们的抽奖程序是依赖于Math.random生成的随机数的。

但是,可能会有人质疑,Math.random生成的随机数真的是随机的,没有规律的吗?有没有可能通过预测出规律从而控制中奖结果?

Math.random

说到javascript的Math.random,ECMAScript是这么规定的:

‘20.2.2.27Math.random ( )’

Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

Each ‘Math.random’ function created for distinct realms must produce a distinct sequence of values from successive calls.

并没有提到是如何实现的。所以各家浏览器实现的方法也都不一样。

比如,V8是这样实现的MathRandom,SpiderMonkey是这样实现的ensureRandomNumberGenerator,webkit是这样实现的WeakRandom

但是,不管是什么方法生成,基本规则都是基于一个种子(seed),经过一系列计算,最终生成一个值。也就是说,如果种子是确定的,那么最终生成的值也一定是确定的……

那么种子又是根据什么确定的呢?一般是使用函数调用时的当前时间作为种子的。

结论

既然上面说到了,所有的结果都是计算的结果,那么是不是说明抽奖结果并不是随机的是可预测的呢?其实也不是,因为在抽奖的过程中引入了随机的外部输入。没错,抽奖函数的执行时机是由人掌控的,而人的思想是不可掌控的,所以可以把抽奖的时机当做随机事件,这样抽奖的结果也肯定是随机的了……大概吧……

但是,如果提前确定下了抽奖的时间了,理论上,抽奖的结果就是可预测的了。

那么有没有办法不依赖用户输入来产生随机的结果呢?只要引入一些无法认为控制的元素就可以了,比如使用一些无法预测和控制的物理信息或者自然现象来生成随机数。

例如,Linux中的接口/dev/random就是引入了物理噪音作为输入来产生随机数的。

还有RANDOM.ORG,这个网站使用大气噪音来生成随机数。(他们提供的服务还是免费的,可以再这里查看他们提供的服务列表)

P.S.

其实所有的伪随机数生成器都长周期相关现象,不过只要这个周期足够长,短时间内是不会出现问题的。之前V8就爆出过乱度不足的问题,后来在49版本改用xorshift128+算法解决了这个问题。
gab-draw-1
xorshift128+算法拥有极长的周期长度:

This has been pointed out to us, and having understood the problem and after some research, we decided to reimplement Math.random based on an algorithm called xorshift128+. It uses 128 bits of internal state, has a period length of 2128 - 1, and passes all tests from the TestU01 suite.

应付年会抽奖这种小范围的活动肯定是绰绰有余的了。但是如果要在密码或者安全领域使用伪随机数,最好还是使用CSPRNG(密码学安全伪随机数生成器)来生成。浏览器环境可以使用crypto.getRandomValues,nodejs环境可以使用crypto.randomBytes

需要注意的是crypto.getRandomValues函数接收的是一个TypedArray(Int8Array,Uint8Array……)而不是普通的数组,然后返回一个随机数队列。crypto.randomBytes函数接受一个字符指定返回值得长度,然后返回一个buffer而不是数字。要想转换为数字的话需要先用toString(‘hex’)转换为16进制字符串,再用parseInt将其转化为数字。

ok,那么这次的扯淡就到这里,感谢您的收看,咱们下次再扯,完结撒花~\( ̄︶ ̄)/

扩展阅读