您好,匿名用户
随意问技术百科期待您的加入

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

+3 投票

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

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

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

 

用户头像 提问 2012年 12月6日 @ 匿名用户
编辑 2012年 12月11日 @Saber
分享到:

1个回答

+3 投票
 
最佳答案

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

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

用户头像 回复 2012年 12月6日 @ 匿名用户
编辑 2012年 12月11日 @Saber
提一个问题:

相关问题

+1 投票
1 回复 42 阅读
用户头像 提问 2013年 9月10日 @ hacker 上等兵 (362 威望)
0 投票
1 回复 37 阅读
0 投票
1 回复 40 阅读
用户头像 提问 2012年 12月1日 @ Wukong 上等兵 (475 威望)
0 投票
1 回复 1 阅读
用户头像 提问 2017年 2月10日 @ Nocturne 上等兵 (262 威望)

欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。
温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。

欢迎访问随意问技术百科,为了给您提供更好的服务,请及时反馈您的意见。
...