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;
}

results matching ""

    No results matching ""