阅读 944

掘金活动抽奖老不中?快来和我一起“优化”抽奖算法吧

前言

掘金经常在沸点搞一些抽奖活动,身为中奖绝缘体的我每次都是当分母,我一度怀疑是抽奖算法“有问题”,review了它的抽奖算法之后,我决定给他做一次“改良”。

它的抽奖算法有两个版本,核心都是JS随机数。

  1. 站长直播时的抽奖算法(简陋版)

我们都知道掘金的用户名是不会重复的,所以可以用用户名来抽奖:获取所有参与用户的用户名 -> 将用户名放进数组 -> 数组去重 -> 生成0到数组长度范围内的随机数 -> 利用数组索引找到用户名。

这样做的缺点很明显,一个用户可能中奖两次,需要再抽一次。

  1. 沸点活动的新抽奖算法

核心代码如下,去重后的用户先随机乱序,再取前N名。

users.slice().sort(() => Math.random() - 0.5).slice(0, count)
复制代码

旧算法的缺陷

随机数是否公平?答案是肯定的,当你生成的次数足够多,每个数出现的概率是一样的。但是目前我们的生成次数有限,随机数就不再是公平的。

那么如何让每个人都雨露均沾呢?即在有限次生成随机数的情况下中奖概率接近相同。

算法改良1

我先来尝试下修改第一种抽奖算法。

位数相同

想要每个随机数生成的概率接近,首先要让所有人都在同一起点,即每个人编号的位数是相同的。

假设参与人数是0-89,则让每个人的编号都加上10。如果50人参加,即生成10-60的随机数

假设参与人数是90-899,则让每个人的编号都加上100。如果500人参加,即生成100-600的随机数。

假设参与人数是900-8999,则让每个人的编号都加上1000。如果5000人参加,即生成1000-6000的随机数。

以此类推,在不改变所有人编号位数的前提下,所有人的编号都加上最小的N位数

增加随机次数

按照上面的算法,如果500人参加,直接生成100-600的随机数也不太好,边界数字生成的概率还是比中间数小。我们可以按个位、十位、百位、千位分开生成,然后再拼成一起。

假设参与人数是511,那么生成的随机数范围是100-611。

首先生成百位数,范围是1-6。

再生成十位数0-9,个位数0-9。

生成之后需要校验一下,数字是否存在。

比如说分别生成了6、2、0,620是不存在的,继续生成。

优化用户的序号

用户序号以用户最后一次回复为准,比如某个用户回复了两次,序号分别是 220,由于我们会做去重操作,所以这个用户的序号就是 2,但是实际上用户肯定希望以最后一次回复为准,那应该如何处理呢,办法也很简单。数组先倒序,去重再倒序回来即可。

talk is cheap show me the code

const lotteryDraw = () => {
  const luckUserNum = Number(window.prompt('你想抽几位锦鲤?')); // 中奖人数
  const userArr = new Array(300).fill(1).map((item,index) => index); // 模拟参与人数
  const length = userArr.length;
  let add = 0;
  let times = 1;
  if(length<89){
    add = 10;
    times = 2;
  }else if(length < 899){
    add = 100;
    times = 3;
  }else if(length < 8999){
    add = 1000;
    times = 4;
  }else{
    add = 10000;
    times = 5;
  }

  const min = add;
  const max = add + length;
  const luckUser = [];

  const creatNumber = times => {
    let num = '';
    for(let i = 0; i < times; i++){
      const temNum = Math.floor( Math.random ( ) * 10);
      num += temNum;
    }
    return +num;
  }

  while (luckUser.length < luckUserNum) {
    const userIndex = creatNumber(times);
    if(userIndex < max && userIndex >= min && !luckUser.includes(userIndex)){
      luckUser.push(userIndex-add)
    }
  }

  console.log(luckUser);
}

lotteryDraw();
复制代码

算法改良2

2种抽奖算法可以改进的点在于数组截取的起点不要为0,先随机生成一个范围为 [ 0, 数组长度 - 中奖人数 ] 的随机数,以这个数为起点截取数组就好了。

总结

数学渣渣只能尽力保证抽奖公平,希望下次中奖有我!!!