01月17, 2017

5分钟现场撸代码——谈总结会抽奖程序

原文:https://www.h5jun.com/post/luckey-draw-in-5-minutes.html

昨天给奇舞团小伙伴们开年度总结会。JK大大为我们捐了10个小水滴摄像机,在开会前5分钟,裕波临时说要写一个抽奖程序,现场抽10名中奖的小伙伴,于是这个抽奖任务就理(莫)所(名)当(其)然(妙)地落到了我这个团长的头上。

闲话少说,那么如何在开会前现场写一个抽奖程序,满足这一要求呢?

首先,裕波、成银用白纸给同学做了简单的“奖券”,奖券上只有号码,从 1 ~ 62,一共有 62 人,从其中要公平地抽取出 10 人,而且不重复。所以,初步判断,这是一个简单的随机抽取过程,有 N 个数,从中抽出 M 个(M < N)。直接随机抽取是最容易想到的:

直接抽取

const cards = Array(62).fill().map((_,i)=>i+1); //初始化一个 1~62 的数组

function draw(n = 1){ // 一次抽取 n 个,默认一次 1 个
    var ret = [];
    for(var i = 0; i < n; i++){
        let idx = Math.floor(cards.length * Math.random());
        ret.push(...cards.splice(idx, 1));
    }
    return ret;
}
console.log(draw(10)); //抽取一次,10个中奖者

上面这个方法非常直观,首先生成一个顺序的 1 ~ 62 号的数组,然后从其中随机抽取 10 次,为了不重复,将抽取的数字通过 cards.splice(idx, 1) 从原数组中取出来。

上面这种方式可行,但它不是最好的,因为每次 splice 一个数字,取 10 个数字需要 splice 10 次,这看起来不是特别好。可以想到另一种方法,先对数组进行“洗牌”,然后一次把 10 个数字取出来:

先洗牌

function draw(amount, n = 1){
    const cards = Array(amount).fill().map((_,i)=>i+1); 

    for(let i = amount - 1; i >= 0; i--){
        let rand = Math.floor((i + 1) * Math.random());
        [cards[rand], cards[i]] =  [cards[i], cards[rand]];
    }
    return cards.slice(0, n);
}
console.log(draw(62, 10));

上面这个版本是月影实际现场写出的(略有修改),它是不错的,但是它也有明显缺点。首先它先把所有的牌都排序了,但实际上只需要排序 10 张牌就好,多余的排序没有必要。其次,它不方便连续抽奖,比如第一次抽取 10 个号,然后再想多抽取 5 个号,它就做不到了。

我们先解决第一个问题:

不需要洗所有的牌

function draw(amount, n = 1){
    const cards = Array(amount).fill().map((_,i)=>i+1); 

    for(let i = amount - 1, stop = amount - n - 1; i > stop; i--){
        let rand = Math.floor((i + 1) * Math.random());
        [cards[rand], cards[i]] =  [cards[i], cards[rand]];
    }
    return cards.slice(-n);
}
console.log(draw(62, 10));

上面这个版本是优化过的版本,显然如果取 10 个数,只需要循环 10 次即可,不需要把 64 张牌都洗了。

要解决可以连续抽奖的问题,就需要把 cards 提取出来(就像方案 1 的随机抽取一样),但是那样的话就使得函数有副作用,虽说是临时写一个抽奖,也不喜欢设计得太糙。或者,那就加一个构造器执行初始化?

构造器负责初始化

function Box(amount){
    this.cards = Array(amount).fill().map((_,i)=>i+1); 
}
Box.prototype.draw = function(n = 1){
    let amount = this.cards.length, cards = this.cards;

    for(let i = amount - 1, stop = amount - n - 1; i > stop; i--){
        let rand = Math.floor((i + 1) * Math.random());
        [cards[rand], cards[i]] =  [cards[i], cards[rand]];
    }

    let ret = cards.slice(-n);    
    cards.length = amount - n;

    return ret;
}

var box = new Box(62);
console.log(box.draw(5), box.draw(5)); //一次取 5 个,取 2 次

更优雅的解决方式?

实际上,对于一次可能抽取任意多个获奖人的场景,用 ES6 的 generators 非常合适,我们可以直接拿洗牌的版本略做修改:

function * draw(amount){
    const cards = Array(amount).fill().map((_,i)=>i+1); 

    for(let i = amount - 1; i >= 0; i--){
        let rand = Math.floor((i + 1) * Math.random());
        [cards[rand], cards[i]] =  [cards[i], cards[rand]];
        yield cards[i];
    }
}
var drawer = draw(62);

console.log(Array(10).fill().map(()=>drawer.next().value)); //一次取出10个结果

最后补充一个小技巧,利用 Array(n).fill().map(...) 可以方便快速地构造数组:

Array(10).fill().map((_,i) => i+1); // 得到 [1,2,3,4,5,6,7,8,9,10]

总结

现场抽奖需求虽简单,但也有那么多可以思考的点,不知道你 get 到哪些点,不知道你喜欢哪个版本的代码。或者你有自己的思路?欢迎在底部评论区写下来~

本文链接:http://www.75team.com/post/luckey-draw-in-5-minutes.html

-- EOF --

Comments