如何实现新浪微博的抽奖系统算法？

Question

最近公司要做一个抽奖系统，抽奖源数据量不到1000（数据包括姓名、手机号、所属部门）。

共5个奖项，每一奖项至少5人，可能还有特等奖，当然这些都是已知的。
我现在想到的是，一次性取出所有数据的唯一ID，然后抽每一个奖项的每一个人都随机一次（这样应该更公平吧？），抽完一次后更新已经抽出的人的状态，取出数据展现，接着继续。

问：
1、总感觉这样的算法不太合适，是否有更好的算法？
2、像新浪微博的转发抽奖系统，数据量可能几十万到几百万，显然上面的算法是不合适的，不知道是怎么样一种算法？

 

Answer 1

1. 你的需求其实很简单，就是从N个元素中随机抽取k个，并且要尽量保证每个元素被抽中的概率都是k/N。最简单的办法就是将这N个元素存在一个数组中，随机打乱（保证每个元素出现在每个位置的概率都相同），然后选取前k个就行。具体的算法，直接用stl algorithm里的random_shuffle。

2. 对于微博这种转发抽奖系统，其难度在于
(1) N很大
(2) N未知
如果是在活动结束后才给出所有中奖结果，那么就可以采用一种叫做“蓄水池抽样”的算法，时间复杂度O(N)（扫一遍），空间复杂度O(k)，从数学上可以保证（只要随机数发生器是真随机），每一个元素中奖的概率是 k/N。