请教各位 V 友一个神奇的夺宝算法(二)

[adkudao]

业务描述见上一个帖子:
http://v2ex.com/t/287935

在众位 V 友的建议下, 我采用 Redis+MySQL 结合的思路:
事先将号码批量生成, 保存在 redis 的 list 中, 夺宝时就 spop 一个, 存入 MySQL

但构想很美好, 现实很残酷, 我用 phpredis (PHP 扩展,性能最优的方案)来批量生成号码时, 一但号码数量上了 45W, 整个操作就失败了,而且就算只生成 40W 号码, 也需要七八秒的时间, 这跟我预想的完全不一样;

我的代码如下:
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
$redis = new Redis();
$redis -> connect('127.0.0.1', 6379);

$haomas = range(1, 480000);
$redis -> delete('test');
$sTime = microtime(true);
$redis -> multi(Redis::PIPELINE);

foreach ($haomas as $key => $value)
{
$redis -> rpush('test', $value);
}

$redis -> exec();
$eTime = microtime(true);

var_dump( ($eTime - $sTime)*1000 );
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---


之前有位 V 友 @lecher 提到过另一种思路, 通过自增 ID 来实现伪随机 id*num1+num2 , 可是光看" id*num1+num2 "这么一串代码 , 我也不知道该如何入手才好, 不知道这个算法有没有具体的案例教程?


或者说集思广益, 请教众位 V 友, 要解决这种生成几百万夺宝号码的需求, 还有更优更聪明的算法吗?

[lecher]

我提的建议不是 id*num1+num2
而是你目前做的预先生成随机序列插入 Redis 或者 MySQL 中。

这个不是算法的锅，查查 PHP 配置环境的内存限制和执行时间限制， Redis 的连接时间也可以查查。几百万条记录的数据分析我偷懒的时候也是一个脚本跑完，跑个三五分钟是常事。这个数量级的处理和内存占用不应该崩。

小优化的话， Redis 可能不需要全部随机数塞到队列了再执行，可以间隔三五千个就执行一次提交。

如果还要更快的生成速度，那就把生成切分任务拆到多进程去，可以开一个常驻内存的进程做任务调度，专门调度多进程去生成随机队列了。

偷懒就用 swoole ，它有 task 的样例。
自己写简版的也行，无非就是 crontab 开个定时任务，定时唤醒调度脚本，用 pcntl 模块检查进程里面跑的任务数够不够，不够就开新的。
Redis 开个任务处理队列，任务进程的脚本定时去取任务出来执行生成指定范围的随机数并插入 Redis 的商品对应的队列中。

[11138]

能否说一下 PHP 版本号？ 我想测试一下，谢谢。
我用 perl 生成 40 万记录是 4 秒， 50 万是 5 秒， 100 万：
10 wallclock secs ( 3.92 usr + 4.40 sys = 8.32 CPU)

[eecjimmy]

range 的问题吧，试试构造器

[just4test]

我建议，不预先生成号码。
首先给所有奖品编号，比如某个房子的编号是 H01
然后当抽奖时，给关联到奖品的彩票顺序生成号码，比如房子的第一张彩票是 H01_00001 ，以此类推。 redis 里面只需要记录该奖品已经发出了几张彩票即可。当然，你需要一个 sql 数据库记录已经发出的彩票和购买者的对应关系。

开奖时，根据星辰轨迹算出一个数字，对他用已经发出的彩票数量求余。比如夜观天象得出数字 75364264 ，而房子发出了 62534 张彩票，则中奖号码为 75364264 % 62534 = 10794 ， 即 H01_10794 这张彩票中奖。当然，要求夜观天象得出的数字远大于单个奖品的彩票总数。

[adkudao]

@lecher
嗯实在不行, 我就开个 2 个 crontab:
第一个 crontab 每隔一秒就检查一次小商品, 哪些小商品的夺宝号码没有全部生成, 就生成 1K 个
第二个 crontab 每隔 10 秒就检查一次大商品, 哪些大商品的夺宝号码没有全部生成, 就生成 10W 个
这样应该就妥了

@11138
我 PHP 版本是 5.6.2 机器是 2.66 GHz Intel Core i7 8 GB 1067 MHz DDR3

@eecjimmy
已感谢


@just4test
这样可能不太符合业务需求,夺宝类的网站,号码基本上都是随机分配, 也就是说一个商品有 10 个号码的话, 就必须买一个, 随机分配一个出去, 如果第一个买的分配 1 号, 第十个买的分配十号, 那别人是完全可以根据这个规则来推算中奖号码的, 所以分配出去的号码必须随机

[zingl]

真会有几十万个人来“夺宝？

连续号、排队随机取、开奖的时候随机大数取余

[takashiki]

crc32

[takashiki]

@takashiki 加上重复判断

[just4test]

@adkudao 没明白如何推算中奖号码。可以举例说明吗？

[adkudao]

@just4test
1. 一个 10 块钱的商品, 分别对应 10 个号码
2. 用户花一块钱, 可以随机抽取一个号码
3. 10 个号码抽完后, 得出一个幸运号码, 谁拥有这个号码, 谁就可以获得商品


为什么不能固定按 1,2,3,4,5..这样分配?
因为计算幸运号码的公式是固定的, 那如果夺宝号码也是按固定顺序分配的话,那么依据幸运号码公式, 是可以反推出中奖号码的;
比如根据刚才那个 10 块钱的商品, 根据公式, 我大概可以推算它的幸运号码会在 4~6 之间产生
但如果号码是随机分配的, 那么即使我推算出幸运号码会出现在哪个数字区间, 我也很难作弊, 因为我不知道分配给我的号码是哪个
注:
这里的公式可以是任何公式, 比如常见的去最后 50 条参与记录的时间, 计算时间总和+最近一期时时彩开奖号码结果, 再除以参与人数, 得到余数就是幸运号码


所以现在的问题不在于如何生成幸运号码, 而是如何将连续的一百万个号码, 随机分配出去

[adkudao]

@takashiki
这.... 我要生成一百万个连续的号码, 别人夺宝一次就随机分配一个出去, 用 crc32 可以做到?

[adkudao]

@zingl
现在其实卡在生成号码这一环节了, 生成 100W 个号码很费时, 我在想有没有什么聪明的办法可以解决

[takashiki]

@adkudao 额，用 crc32 生成伪抽奖号

[ykrl089]

估计是页面超时了吧，不能多次调用， 每次 40w ？

[adkudao]

@takashiki
很抱歉, 没明白, 比如有个商品, 有 10 个号码, 分别是 1 2 3 4 5 6 7 8 9 10
我如何用 crc32 随机生成这 10 个号码呢?

[adkudao]

@ykrl089
估计是的, @lecher 也提到过可能是脚本时间限制;


但是现在的问题在于就算脚本不限时间, 每次生成几百万的号码都要花费好几分钟的话, 效率有点低

因为夺宝类目好多夺车的, 一辆车二三十万个号码, 一期结束了立马开始夺新一期, 等于立刻就要分配新号码, 几分钟的时间有点长

像网易一元夺宝, 他们的车子, 房子, 都是几十几百万的号码这么发放, 一期结束后立马就能开始夺取新的一期, 真不清楚网易是怎么解决这个问题的

[admol]

到时候客户要你作弊呢

[adkudao]

@admol
不会, 这个要拉风投的, 所有数据都要公开透明, 这个客户有要求不能作弊不能留后门, 到时候会审查的

[liubo]

rpush 是支持多值的，一次性把整个数组提交过去试试？

我用 python 测试两种情况还是差距比较明显..

[lijinma]

你这做法太麻烦了，我给你个简单的思路，即简单又保证绝对公平，透明。

只需要在 Redis 中记录每个商品的自增值，初始化为 1

比如一个商品有 10 个人参与，那每个人分配一个号： 1 ， 2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8 ， 9 ， 10

你现在要做的是在这 1-10 个号中随机选取一个人，对吗？

所以开奖的过程：

调用： https://www.random.org/ 随机的函数，获取 1-10 的随机数，这是真随机，不是伪随机，获取到谁就是谁。

如果是 100 万人参加？那也不用担心啊，没任何压力，而且 Redis 的并发能撑个几万。


你需要考虑的问题是，如何正确随机，而不是提前生成号码。

嘿嘿，希望给你帮助。