1. 带有权重的随机算法
add: 2019-11-14
首先,得认为语言本身自带的随机,是真随机(其实好像很多都是伪随机,甚至有些语言不加seed,每次重新启动,随机出来的数都是一样的)....
1.1.1. 前戏
先分析一个问题,假如
- 你面前有3个碗,其中一个碗里有东西
- 让你先选一个,不打开
- 我打开其中一个,里面没有东西
- 再让你选一次(不选了,就要自己手里的,或者选另外一个),求 你选中有东西的概率多大
1.1.2. 思路
先假设 有A,概率百分之二十,B概率百分之三十,C概率百分之四十五,D概率百分之五
- 数组大法
- 定义一个数组,里面A有20个,B有30个,C有45个,D有5个,然后随机这个数组..
- 但是这样有个问题,生成数组可能需要很大空间,因为万一有很多种类.....或者数量巨大,所以不推荐!
- 随机数隐射
- 用语言自带的随机函数,随机1~100之间的值
- 定义:
- 如果随机的值是在1 ~ 20之间,就是A
- 随机的值是21 ~ 50之间,就是B
- 随机的值是51 ~ 95之间的就是C
- 随机的值是95 ~ 100中间的就是D
- 好处就是不需要特别大的内存空间,个人推荐这种
1.1.3. 实现
咱就用随机数隐射来做,不过有个问题,实际业务里,假如上面的 ABCD是红包金额,20,30,45,5是红包金额对应的库存,库存是会减少的
当第一个人来抽红包,概率确实是 A概率百分之二十,B概率百分之三十,C概率百分之四十五,D概率百分之五,但是A抽了一个之后,库存减少了,概率还是这个概率么
- 这样就出现了问题,如果考虑实际,库存会减少,后续的人抽取的概率就会发生改变
- 一种就是永远用这个比例来抽取,假设A的20个红包都抽没了,但是随机数又随机到了1~20以内,就通知没抽中..或者显示其他的,这样概率肯定最平均的!只不过...估计用户会骂爹
- 恩,这是概率论里的.. 怎么计算概率早已忘光了.. 还给老师了...
1.1.4. 代码
两种区别(库存变化其实区别不是很大,核心代码是一样的)
数组方法就不写了.. 感觉有点浪费性能
- Golang代码
type ModelRes struct{
Id int `json:"id"`
Name string `json:"name"`
Num int `json:"num"`
}
func main() {
// 假设这是数据库里的数据
mr1 := ModelRes{
Id: 1,
Name: "A奖品",
Num: 19,
}
mr2 := ModelRes{
Id: 2,
Name: "B奖品",
Num: 30,
}
mr3 := ModelRes{
Id: 3,
Name: "C奖品",
Num: 45,
}
mr4 := ModelRes{
Id: 4,
Name: "D奖品",
Num: 5,
}
// 假设只是数据库查出来的结果
var mrs []ModelRes
mrs = append(mrs,mr1,mr2,mr3,mr4)
// 定义两个map,一个是数据库里的数据ID==>数据名字,数据ID==>数据的数量
prize := make(map[int]string)
pack := make(map[int]int)
for _,v := range mrs {
prize[v.Id] = v.Name
pack[v.Id] = v.Num
}
RedPack(prize,pack)
}
func RedPack(prize map[int]string,pack map[int]int) (id int) {
// 定义一个map,key对应数据ID,value是个定长为2的数组,下标0对应数值左范围,下标1对应数值右范围
randArr := make(map[int][2]int)
// sum为所有库存的和,并赋值randArr
var sum int
for k,v := range pack {
var randArr1 [2]int
randArr1[0] = sum
sum += v
randArr1[1] = sum
randArr[k] = randArr1
}
// Golang随机得设置seed,否则每次随机的数是一样顺序的,
rand.Seed(time.Now().Unix())
// 获取某个随机值
s := rand.Intn(sum)
fmt.Println(s,randArr)
// 查找随机出来的值在哪个范围内
for m,n := range randArr {
if s >= n[0] && s < n[1] {
id = m
break
}
}
fmt.Println(prize[id])
// 返回产品ID,一般后续操作是 返回奖品ID,然后将该产品在数据库里的库存-1
// 如果你想永远概率都一样,那么每次抽中之后该函数传值 pack后的值不能变,需要另外一个参数比较当前奖品还有库存否,如果没有,返回其他值
return
}
- PHP代码
这是我多年前在公司业务代码里自己实现的(我加了一层redis缓存,是Laravel框架里使用的),是源码,斟酌着看吧..
/**
* 获取随机数,大于等于左边,小于右边
* @param $min
* @param $max
* @return int|null
*/
function get_rand_num($min,$max)
{
if ($min == $max) {
return null;
}
$num = rand($min,$max);
if($num == $max)
{
$num = get_rand_num($min,$max);
}
return $num;
}
/**
* @date 2017-11-14 11:48:58
* @param (array) $array ['金额' => '数目']
* @param (string) $cacheKeyRemainRedPackNumArr 还剩红包个数的数组(缓存的key)
* @param (string) $cacheKeyHadSendRedPackArr 已发送红包个数的数组(缓存的key)
* @param (string) $cacheKeyRedPackNum 还剩红包个数(缓存的key)
* @param (string) $cacheKeyHadSendRedPackSumMoney 已发红包总金额(缓存的key)
* @return int|mixed
* @note 为什么参数都写的这么长呢??? 因为我自己过段时间我自己都他喵的忘了是什么意思!只能这样写,我以后才能想起来是啥东西!
* -------------------------------------------------------------------------------
* $ Author: xzghua. | Email: xzghua@gmail.com | Date: 2017
* ===============================================================================
*/
function zhu_red_pack($array,$cacheKeyRemainRedPackNumArr,$cacheKeyHadSendRedPackArr,$cacheKeyRedPackNum,$cacheKeyHadSendRedPackSumMoney)
{
// $cacheKeyRemainRedPackNumArr = 'nov_remain_red_pack_num_arr';
// $cacheKeyHadSendRedPackArr = 'nov_had_send_red_pack_arr';
// $cacheKeyRedPackNum = 'nov_had_send_red_pack_num';
// $cacheKeyHadSendRedPackSumMoney = 'nov_had_send_red_pack_sum_money';
$money = [];
$redPackNumber = [];
$originNum = [];
$allSum = 0;
foreach ($array as $key => $value) {
$allSum += $key * $value;
$money[] = $key;
$redPackNumber[] = $value;
$originNum[$key] = 0;
}
$number = \Cache::get($cacheKeyRemainRedPackNumArr) ? \Cache::get($cacheKeyRemainRedPackNumArr) : $redPackNumber;
$count = count($money);
$keySum = array_sum($number);
$newRed = [];
$i = 0;
foreach ($number as $key => $value) {
$i = $i + $value;
$newRed[$key] = $i;
}
array_unshift($newRed, 0);
$rand = get_rand_num(0, $keySum);
$hadSendRedPackArr = \Cache::get($cacheKeyHadSendRedPackArr) ? \Cache::get($cacheKeyHadSendRedPackArr) : $originNum;
$redPack = 0;
for ($k = 0; $k < $count; $k++) {
if ($rand >= $newRed[$k] && $rand < $newRed[$k + 1]) {
$number[$k] = $number[$k] - 1;
\Cache::put($cacheKeyRemainRedPackNumArr, $number, 100000);
\Cache::put($cacheKeyRedPackNum, $keySum - 1, 100000);
$redPack = $money[$k];
$hadSendRedPackArr[$redPack]++;
\Cache::put($cacheKeyHadSendRedPackArr, $hadSendRedPackArr, 10000);
//加一个限制条件
$cacheCommonRedPack = \Cache::get($cacheKeyHadSendRedPackSumMoney) ? \Cache::get($cacheKeyHadSendRedPackSumMoney) : 0;
\Cache::put($cacheKeyHadSendRedPackSumMoney, $redPack + $cacheCommonRedPack, 10000);
if ($cacheCommonRedPack >= $allSum) {
\Cache::put($cacheKeyRedPackNum, '0', 100000);
}
\Log::info('"controller.error" to listener "' . __METHOD__ . '".', [
'redPackMoney' => $redPack,
'redPackNum' => \Cache::get($cacheKeyRedPackNum),
'sumHadSendMoney' => \Cache::get($cacheKeyHadSendRedPackSumMoney)
]);
}
}
return $redPack;
}
/**
* @param $array ['id' => '库存数量']
* @return int|mixed 返回是$array的key即id
* @date 2017-11-22 19:02:58
* @note 将上面的红包算法拆检,不利用缓存,目前用在数据库抽奖活动里
* -------------------------------------------------------------------------------
* $ Author: xzghua. | Email: xzghua@gmail.com | Date: 2017
* ===============================================================================
*/
function zhu_draw($array)
{
$money = [];
$redPackNumber = [];
foreach ($array as $key => $value) {
$money[] = $key;
$redPackNumber[] = $value;
}
$count = count($money);
$keySum = array_sum($redPackNumber);
if ($keySum == 0) {
return null;
}
$newRed = [];
$i = 0;
foreach ($redPackNumber as $key => $value) {
$i += $value;
$newRed[$key] = $i;
}
array_unshift($newRed, 0);
$rand = get_rand_num(0, $keySum);
$redPack = 0;
for ($k = 0; $k < $count; $k++) {
if ($rand >= $newRed[$k] && $rand < $newRed[$k + 1]) {
$redPack = $money[$k];
\Log::info('奖品(数据库里建议为ID)='.$redPack.'随机数='.$rand);
}
}
return $redPack;
}