按概率随机抽取物品的原理及实现

[axetroy]

情景：抽奖

大家都懂的，抽奖就安慰奖概率高，头奖概率低。虽然实际的抽奖业务中，都是后端在做，但是谁让咱有nodejs呢。前端开发人员也能过一把瘾。

API的设计

概率性的东西，就要用到随机函数Math.random()，但是只能随机产生0-1范围的随机数，那么怎么制定概率呢？

假设场景：现在要抽奖如下产品

• IPhone 8(1%)
• Ipad(2%)
• 纪念版T恤(12%)
• 纪念版水杯(25%)
• 空空如也(60%)

确保所有概率相加结果为1。

我们先假设API是这样的

let roll = new Roll();

roll.add('IPhone 8', 0.01);
roll.add('Ipad', 0.02);
roll.add('纪念版T恤', 0.12);
roll.add('纪念版水杯', 0.25);
roll.add('空空如也', 0.60);

const result = roll.roll();

console.log(`恭喜您获得: ${result}`);

但是直接指定概率，这样的api是有局限性的。还需要注意让概率之和为1
我们换一个概念 权重

改变后的api

let roll = new Roll();

roll.add('IPhone 8', 1);
roll.add('Ipad', 2);
roll.add('纪念版T恤', 12);
roll.add('纪念版水杯', 25);
roll.add('空空如也', 60);

const result = roll.roll();

console.log(`恭喜您获得: ${result}`);

这不是坑爹吗，就把概率取整了(:，其实不然。

概率不能再直接设置，而是通过第二个参数传入权重。 该物品的概率=它的权重/总权重

例如抛硬币50%的概率：

let roll = new Roll();

roll.add('正面', 1);
roll.add('反面', 1);
const result = roll.roll();

console.log(`硬币是: ${result}`);

原理

那么实际操作中，如何实现概率分布，想象一下0-1是一条轴线。

各个商品的概率均<=1，且总和永远为1. 我们把轴线分成几个部分，各个部分分别被这几个商品占据着(请不要在乎下面的比例(: )

0-----0.01------0.03---------------0.15------------0.40--------------------------------------------------1

• IPhone 8: 0 - 0.01
• Ipad: 0.01 - 0.03
• 纪念版T恤: 0.03 - 0.15
• 纪念版水杯: 0.15 - 0.40
• 空空如也: 0.40 - 1

那么使用 Math.random() 随机出来的数，在哪个区间就相当于抽到了哪个商品

代码实现

function throwError(msg) {
  throw new Error(msg);
}

class Roll {
  constructor() {
    this._ = [];    // 存储要roll的列表
  }

  add(
    item = throwError('Item must be required'), // 验证参数
    rank = throwError('Rank must be required')  // 验证参数
  ) {
    const rankType = typeof rank;
    if (rankType !== 'number')
      throwError(`Rank must be a Number not ${rankType}`);
    if (rank <= 0) throwError('require Rank>0');
    this._.push({ item, rank });                // 把要roll的商品添加要列表中
  }

  roll() {
    let totalRank = 0;
    const random = Math.random();               // 产生一个随机数
    let result = null;

    const items = this._.slice().map(item => (totalRank += item.rank) && item);   // 计算总权重

    let start = 0;                                  // 区间的开始，第一个是为0

    while (items.length) {
      const item = items.shift();                   // 取出第一个商品
      const end = start + item.rank / totalRank;    // 计算区间的结束
      if (random > start && random <= end) {        // 如果随机数在这个区间内，说明抽中了该商品，终止循环
        result = item;
        break;
      }
      start = end;                                  // 当前区间的结束，作为下一个区间的开始
    }

    return result ? result.item : null;
  }
}

验证是否正确

所谓实践才是检验真理的唯一标准，验证硬币正反两面的概率为50%需要无数次的实验。

我们就随机100000次，5轮结果对比看看

const data = {};

for (let i = 0; i < 100000; i++) {
  let roller = new Roll();
  roller.add('IPhone 8', 1);
  roller.add('Ipad', 2);
  roller.add('纪念版T恤', 12);
  roller.add('纪念版水杯', 25);
  roller.add('空空如也', 60);
  const result = roller.roll();
  if (data[result] === void 0) {
    data[result] = 0;
  } else {
    data[result] = data[result] + 1;
  }
}

console.log(JSON.stringify(data, null, 2));

最后的输出结果

{
  "纪念版水杯": 25077,
  "空空如也": 60024,
  "Ipad": 1926,
  "纪念版T恤": 11931,
  "IPhone 8": 1037
}

{
  "空空如也": 59855,
  "纪念版水杯": 25174,
  "Ipad": 2044,
  "IPhone 8": 981,
  "纪念版T恤": 11941
}

{
  "空空如也": 59715,
  "纪念版T恤": 12014,
  "纪念版水杯": 25207,
  "Ipad": 2031,
  "IPhone 8": 1028
}

{
  "空空如也": 60058,
  "纪念版T恤": 12145,
  "纪念版水杯": 24752,
  "Ipad": 2015,
  "IPhone 8": 1025
}

{
  "空空如也": 59940,
  "纪念版水杯": 24946,
  "纪念版T恤": 12159,
  "Ipad": 1961,
  "IPhone 8": 989
}

结论

可以看出，靠谱

但是可能还有些问题，float64的计算是有精度问题的

0.1 + 0.2 = 0.30000000000000004

这时候可能需要进行矫正，有很多的轻量运算库，比如Big.js