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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3065 天前的主题，其中的信息可能已经有所发展或是发生改变。

业务描述见上一个帖子:
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 友, 要解决这种生成几百万夺宝号码的需求, 还有更优更聪明的算法吗?

第 1 条附言 · 2016-07-05 18:19:43 +08:00

此贴已结, 在此感谢 @11138 大神的方案, 同时也分享出来, 希望能帮到更多有需要的朋友

<?php
ini_set ('memory_limit', '500M');
$redis = new Redis();
$redis -> connect('127.0.0.1', 6379);
$haomas = range(1, 1000000);
$a=array();
foreach ($haomas as $key => $value)
{
array_push($a,$value);
}
$redis -> delete('test1y');
$sTime = microtime(true);
$redis -> multi(Redis::PIPELINE);
$redis -> rpush('test', $a);
$redis -> exec();
$eTime = microtime(true);
var_dump( ($eTime - $sTime)*1000 );
?>

这样生成 100 万大概半秒钟。

Redis

号码

生成

test'

60 条回复 • 2016-07-05 22:18:41 +08:00

lecher

2016-07-05 04:58:29 +08:00 via Android

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

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

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

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

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

11138

2016-07-05 05:27:50 +08:00

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

eecjimmy

2016-07-05 07:04:44 +08:00 via iPhone

range 的问题吧，试试构造器

just4test

2016-07-05 09:29:07 +08:00

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

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

adkudao

2016-07-05 12:02:10 +08:00

@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

2016-07-05 12:21:14 +08:00

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

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

takashiki

2016-07-05 12:35:28 +08:00

crc32

takashiki

2016-07-05 12:36:10 +08:00

@takashiki 加上重复判断

just4test

2016-07-05 12:46:02 +08:00

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

adkudao

2016-07-05 13:58:44 +08:00

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

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

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

adkudao

2016-07-05 14:01:48 +08:00

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

adkudao

2016-07-05 14:03:05 +08:00

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

takashiki

2016-07-05 14:04:49 +08:00

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

ykrl089

2016-07-05 14:09:25 +08:00

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

adkudao

2016-07-05 14:10:42 +08:00

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

adkudao

2016-07-05 14:15:11 +08:00

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

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

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

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

admol

2016-07-05 14:39:40 +08:00

到时候客户要你作弊呢

adkudao

2016-07-05 14:47:07 +08:00

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

liubo

2016-07-05 14:55:11 +08:00

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

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

lijinma

2016-07-05 15:02:33 +08:00

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

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

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

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

所以开奖的过程：

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

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

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

嘿嘿，希望给你帮助。

zingl

2016-07-05 15:36:52 +08:00

在随机性可保证的前提下，只需要保证拿号不重复即可，不需要生成随机号，从连续号池里顺序或者随机取都可以

adkudao

2016-07-05 15:48:55 +08:00

@liubo
真好玩, 直接如下是可以的
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
$redis -> rpush('test', '1', '2', '3');
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

但是这样就不行:
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
$haomas = range(1, 3);

foreach ($haomas as $key => $value)
{
$str .= ','. $value;
}

$redis -> rpush('test', substr($str, 1));
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

然后这样也不行:
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
$haomas = range(1, 3);
$redis -> rpush('test', $haomas);
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

天呐, PHP 该怎样批量传递参数啊

adkudao

2016-07-05 15:51:38 +08:00

@lijinma
这个对于用户来讲就完全不可行的, 因为等于是后台可以随机指定一个数字作为幸运号码
也就是说, 后台想让谁中奖谁就中奖, 那这个产品就很难推广了

500miles

2016-07-05 15:57:15 +08:00

@adkudao

使用 pipeline, 可以提高插入性能

adkudao

2016-07-05 15:59:03 +08:00

@500miles
这个测试结果就是用了以后的结果, 不用 pipeline 性能更糟

cevincheung

2016-07-05 15:59:11 +08:00

有用 set 集合。还能实现随机取出。
有批量插入，一般几十万在 0.xs 之内。

500miles

2016-07-05 16:09:35 +08:00

@adkudao 为什么要事先生成呢?

夺宝者购买时, 再临时生成号码, push 进队列满足不了需求么?

adkudao

2016-07-05 16:25:02 +08:00

@cevincheung
有 php 的代码参考吗?

adkudao

2016-07-05 16:27:19 +08:00

@500miles
如果是小件商品, 用户买 1 个,就临时生成一个, 买 100 个, 就临时生成 100 个, 可能问题不大
主要是大宗商品, 比如房车之类的, 用户会不会一次买个几十万难说, 但客户测试的时候,我估计必然会直接买个几十上百万的, 如果临时生成, 估计要等好几分钟, 这样体验不好

cevincheung

2016-07-05 16:30:45 +08:00

@adkudao

http://redis.io/commands/sadd
http://redis.io/commands/srandmember

3dwelcome

2016-07-05 16:47:12 +08:00

就是 GUID 的数字化表示吧，只要保证不重复就可以了。

连续生成 1 百万个 GUID, 问题不大的。

lijinma

2016-07-05 16:52:10 +08:00

@adkudao

我的方法的关键要靠你自己控制：最后一步必须要调用 https://www.random.org/ 来获取随机数。

按照你的方法，任何人都看不到幸运号码是多少，你后台仍然可以随时修改整个幸运号码，不是吗？

morethansean

2016-07-05 16:57:46 +08:00

是说不相信随机数生成函数吗？
为什么不能从 0 到 n 分配？

3dwelcome

2016-07-05 16:59:36 +08:00

可以考虑用当天的双色球开奖号码作为随机数，取个余数就可以了，对用户透明，也公证无比。

11138

2016-07-05 17:14:02 +08:00

用 perl 的 C 扩展生成 100 万大概 2.5 秒。
用 PHP5.6.2 生成 100 万大概 4 秒。

Martin9

2016-07-05 17:14:49 +08:00

@3dwelcome
虽然很有道理，但感觉有点喜感。
（中奖的人一定后悔没买双色球

11138

2016-07-05 17:15:54 +08:00

@adkudao “一但号码数量上了 45W, 整个操作就失败了”有什么错误信息么？
默认的 PHP 有内存限制，我加了
ini_set ('memory_limit', '300M');
才成功。

11138

2016-07-05 17:24:59 +08:00

@adkudao

$a = array();
array_push($a,'1','2','3');
$redis -> rpush('test', $a);

11138

2016-07-05 17:31:02 +08:00

<?php
ini_set ('memory_limit', '500M');
$redis = new Redis();
$redis -> connect('127.0.0.1', 6379);
$haomas = range(1, 1000000);
$a=array();
foreach ($haomas as $key => $value)
{
array_push($a,$value);
}
$redis -> delete('test1y');
$sTime = microtime(true);
$redis -> multi(Redis::PIPELINE);
$redis -> rpush('test', $a);
$redis -> exec();
$eTime = microtime(true);
var_dump( ($eTime - $sTime)*1000 );
?>

这样生成 100 万大概半秒钟。

11138

2016-07-05 17:31:53 +08:00

test1y 改为 test

adkudao

2016-07-05 18:00:12 +08:00

@11138
屌炸天!!! 性能比 call_user_func_array 快了 6 倍!

adkudao

2016-07-05 18:08:52 +08:00

@11138

贴一段之前的方案, 要十几秒不止, 你这个方案简直炸了! 不是提升 6 倍, 是提升了十几二十倍! 你牛逼!!

$redis = new Redis();
$redis -> connect('127.0.0.1', 6379);

$arrayName = array('test');
// $redis -> delete('test');
$sTime = microtime(true);
// $redis -> multi(Redis::PIPELINE);

$haomas = range(1, 1000000);

foreach ($haomas as $key => $value)
{
array_push( $arrayName , $value );
}

call_user_func_array([$redis, 'rpush'], $arrayName);

$eTime = microtime(true);

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

adkudao

2016-07-05 18:13:44 +08:00

@Martin9 @3dwelcome
哈哈, 两位可以考虑兼职相声演员, 俺们 V 站的朋友一定给你们捧场

adkudao

2016-07-05 18:41:54 +08:00

@11138
兄弟, 好像闹了个乌龙, 你这个代码插进去直接变为了 test => 'Array', 所以速度那么快....

11138

2016-07-05 19:04:30 +08:00

@adkudao 抱歉，刚才赶着出门，还想着回头再测试各种情况。
PHP 用 call_user_func_array 来处理 100 万记录我测试这大概 0.7 秒。等下再测试其它集合的速度。
E5-2680 v3 @ 2.50GHz

jhdxr

2016-07-05 19:13:16 +08:00

$redis -> rpush('test', $a);
应该是
$redis -> rpush('test', ...$a);

另外
array_push( $arrayName , $value );
建议直接改为
$arrayName[] = $value;

这种都是手册上有的内容，有问题不能先看看手册么

3dwelcome

2016-07-05 19:15:30 +08:00 via Android

楼主貌似没理解我的意思。夺宝这种投注类游戏、最重要的是公信度透明化、一旦有暗盒操作嫌疑、以后就再也没人气了。

比如一百人夺宝、要开奖的时候、你去查一下上证指数、取小数点最后两位、作为获奖者随机 id 、这样后台也不可能作假、很有公信度。

jhdxr

2016-07-05 19:15:43 +08:00

call_user_func_array 与直接调用函数相比肯定是后者更快。你顶楼所提到的方案之所以慢的无法忍受是因为循环中有 IO 操作

11138

2016-07-05 19:58:02 +08:00

call_user_func_array([$redis, 'rpush'], $a);
改为
$redis -> rpush('test', ...$a);
这样快了 0.1~0.2 秒。

array_push($a,$value);
改为
$a[] = $value;
速度没变化。

adkudao

2016-07-05 20:20:10 +08:00

@3dwelcome 这样其实也是好的, 而且具有实时性, 不像时时彩还有延迟, 不过客户不同意

adkudao

2016-07-05 20:25:51 +08:00

@jhdxr 嗯,谢谢建议, 已改进

adkudao

2016-07-05 20:30:32 +08:00

@11138
兄弟, 用你之前的 rpush 方法, 插入 list 不成功, 还是用的 call_user_func_array, 时间大概在 3 秒左右,
代码如下:
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
$sTime = microtime(true);

ini_set ('memory_limit', '800M');
$redis = new Redis();
$redis -> connect('127.0.0.1', 6379);

$arrayName = array('test');
$redis -> delete('test');
$redis -> multi(Redis::PIPELINE);

$haomas = range(1, 1000000);

foreach ($haomas as $key => $value)
{
array_push( $arrayName , $value );
}

$f = call_user_func_array([$redis, 'rpush'], $arrayName);

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

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

你之前的 rpush 方法, 还是可以成功吗?

just4test

2016-07-05 21:04:50 +08:00

@adkudao 客户对幸运号码的生成方式有什么要求？

adkudao

2016-07-05 21:09:11 +08:00

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

重点不是幸运号码如何得出, 重点是用户能 "随机" 抽取幸运号码

随机抽取几千个号码不是事, 重点是当一个商品, 比如一套房子, 往往有上百万个号码, 这时要供用户随机抽取, 就比较考验算法和架构了

目前用 call_user_func_array 来向 redis 中生成百万个号码, 大概用时三秒左右, 是目前已验证的最有效率的, 不知道网易他们是怎么解决的

感觉他们的更快

11138

2016-07-05 21:42:23 +08:00

@
$f = call_user_func_array([$redis, 'rpush'], $arrayName);
改为
$redis -> rpush('test', ...$arrayName);

<?php
ini_set ('memory_limit', '500M');
$redis = new Redis();
$redis -> connect('127.0.0.1', 6379);
$haomas = range(1, 1000000);
$a = array();
foreach ($haomas as $key => $value)
{
$a[] = $value;
}
$redis -> delete('test');
$sTime = microtime(true);
$redis -> multi(Redis::PIPELINE);
$redis -> rpush('test', ...$a);
$redis -> exec();
$eTime = microtime(true);
var_dump( ($eTime - $sTime)*1000 );
?>

刚才同时测试了 Set 集合，比 List 列表慢一秒。

11138

2016-07-05 21:43:44 +08:00

@adkudao 快慢这也跟 CPU 有关啊。

adkudao

2016-07-05 22:00:42 +08:00

@11138
我刚试过了, 完全可以了, 我这里大概一秒多, 这应该是 Redis 批量生成号码, 最快的形式了,非常感谢

fuxkcsdn

2016-07-05 22:00:58 +08:00

https://gist.github.com/ccb69768e2b4619801bc8d0a4edda395.git

fuxkcsdn

2016-07-05 22:05:14 +08:00

每次帖 gist 总是忘记咋贴...

https://gist.github.com/consatan/ccb69768e2b4619801bc8d0a4edda395

adkudao

2016-07-05 22:18:41 +08:00

@fuxkcsdn
哈哈, 手疾眼快, 好习惯