红包算法揭秘！哪段代码让你只抢了0.01元？

腾讯云开发者

发布于 2024-05-23 14:10:26

39600

代码可运行

文章被收录于专栏：【腾讯云开发者】【腾讯云开发者】

运行总次数：0

代码可运行

在上一篇《十年前的微信消息收发架构长

01、普通随机法

普通随机法，简单来说其实就是剩余值随机。

普通随机：用余下的值为最大区间进行随机，但可能不均匀，有些人一把随到99，下面很多人都没得随机了。

mt_rand(1, 2); //mt_rand 包含区间前后边界的，即包含最大值和最小值，1和2都会出现。

// 剩余值随机 ，优点：逻辑简单，缺点：随机区间步步减少，可以明显看出随机值的递减特性，
对后面玩家极不公平，且容易被抓到规律，造成舆论不满。
// 做抢红包体验很差，稍微弥补一点的方案：shuffle一下随机数组，让看起来不那么递减明显。
$res = LeftMoneyRedbag($Moneys, $userNums,  $isEveryHave);

//余值随机红包算法 ，一般都是使用剩余值在计算一把。
function LeftMoneyRedbag($Moneys, $userNums, $isEveryHave = 1, $baseMoney = 1)
{
    if ($Moneys <= 0 || $userNums <= 0) {
        return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
    }
    if ($isEveryHave && $userNums > $Moneys) {
        return ['code' => -4, 'msg' => '红包数量不足'];
    }

    //是否每个人都必有
    if ($isEveryHave) {
        $Moneys = $Moneys - ($userNums * $baseMoney);  //此时剩余money可能会无法随机到每一个人
    }

    $userMoney = [];
    //正式执行余值随机
    $leftMoneys = $Moneys; //可能 50分钱 分100人
    $leftUserNums = $userNums;
    while ($leftUserNums > 1) { // 考虑：就一个用户瓜分
        // echo "leftMoneys = " . $leftMoneys . " , leftUserNums = " . $leftUserNums . "<br>";
        $RandVal = 0;
        if ($leftMoneys > 0) { //考虑：剩余的钱不够分
            $RandVal = mt_rand(0, $leftMoneys);
            $leftMoneys = $leftMoneys - $RandVal;
        }
        $userMoney[] = $isEveryHave ? ($baseMoney + $RandVal) : $RandVal;
        $leftUserNums--;
    }

    //最后一位。考虑：剩余的钱太多或者就一个人
    $userMoney[] = $isEveryHave ? ($baseMoney + $leftMoneys) : $leftMoneys;

    echo "总数：" . count($userMoney) . "<br>";
    var_dump($userMoney);
    echo "总值：" . array_sum($userMoney) . "<br>";

    return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}

02、二倍均值算法

正常的算法，定好每个人的最小值，然后就是定下随机区间问题。

二倍均值：实际上就是，用剩下金额的两倍均值为最大区间进行随机，相对正态分布，区间相对合适。但人数越接近总额，分布越均匀。也可以三倍、四倍，倍数越高越随机，正态分布越扁平。

$Moneys = 99 * 10; //单位为分
$userNums  = 990;
$isEveryHave = 0; //是否每个人都有

$res = doubleMeanRedbag($Moneys, $userNums);
// var_dump($res);

//二倍均值算法
function doubleMeanRedbag($Moneys, $userNums, $isEveryHave = 1, $baseMoney = 1)
{
    if ($Moneys <= 0 || $userNums <= 0) {
        return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
    }
    if ($isEveryHave && $userNums > $Moneys) {
        return ['code' => -4, 'msg' => '红包数量不足'];
    }

    //是否每个人都必有
    if ($isEveryHave) {
        $Moneys = $Moneys - ($userNums * $baseMoney);  //此时money可能会无法随机到每一个人
    }

    $userMoney = [];
    //正式执行二倍均值  
    $leftMoneys = $Moneys; //可能 50分钱 分100人
    $leftUserNums = $userNums;
    while ($leftUserNums > 1) { // 考虑：就一个用户瓜分
        // echo "leftMoneys = " . $leftMoneys . " , leftUserNums = " . $leftUserNums . "<br>";
        $RandVal = 0;
        if ($leftMoneys > 0) { //考虑：剩余的钱不够分
            $doubleMeans = ceil($leftMoneys / $leftUserNums * 2);
            $RandVal = mt_rand(0, $doubleMeans);
            $leftMoneys = $leftMoneys - $RandVal;
        }
        $userMoney[] = $isEveryHave ? ($baseMoney + $RandVal) : $RandVal;
        $leftUserNums--;
    }

    //最后一位。考虑：剩余的钱太多
    $userMoney[] = $isEveryHave ? ($baseMoney + $leftMoneys) : $leftMoneys;

    // echo "总数：" . count($userMoney) . "<br>";
    // var_dump($userMoney);
    // echo "总值：" . array_sum($userMoney) . "<br>";

    return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}

03、线段分割算法

线段分割是相对合理的红包算法，但实现逻辑会更复杂一些。红包金额如果想随机分成 N 份，可以处理为：一个线段，随机选择 N-1 点进行切割。

3.1 常规线段分割算法

//线段分割算法  -- 有个致命缺陷，随机值碰撞，分割数量越接近总金额，碰撞概率越大 ，所以最好 userNum数量与总金额差的越大越好
function lineSegmentRedbag($Moneys, $userNums, $isEveryHave = 1, $baseMoney = 1)
{
     if ($Moneys <= 0 || $userNums <= 0) {
        return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
    }
    if ($isEveryHave && $userNums > $Moneys) {
        return ['code' => -4, 'msg' => '红包数量不足'];
    }

    $cutPoints = []; //切割点数组
    $pointNums = $userNums - 1; //存放的
    $userMoney = []; //每一个用户该分得的钱
    //正式线段分割，完全随机 
    // $j = 0;
    // 当 用户数 和 总金额差距不大时，这种写法效率极差
    while ($pointNums > 0) {
        if ($isEveryHave == 1) {
            $randVal = mt_rand(1, $Moneys - 1); //每个人都有，mt_rand包含区间边界的，即包含最大值 和 最小值 ，1和2都会出现
        } else {
            $randVal = mt_rand(0, $Moneys); //所有用户，全区间随机，保证了公平，所有人概率一致 0~10。如果$Moneys设置-1，导致最后一位必定不为0
        }

        if (in_array($randVal, $cutPoints)) {  //这边会产生随机碰撞，500个随机需要2500次左右才能覆盖。
            // $j++;
            continue;
        }
        $cutPoints[] = $randVal;
        $pointNums--;
    }

    // echo "无效循环次数：" . $j . "<br>";
    // echo "最终切割点数组数量：" . count($cutPoints) . "<br>";
    // var_dump($cutPoints);
    // return;

    //根据cutPoint计算每个人所得 同时考虑：就一个人
    $lastVal = 0;
    if (count($cutPoints) > 0) {
        sort($cutPoints);
        foreach ($cutPoints as $RandPoint) {
            $userMoney[] = $RandPoint - $lastVal;
            $lastVal = $RandPoint;
        }
    }

    $lastDiff = $Moneys - $lastVal;
    $userMoney[] =  $lastDiff;

    // echo "总数：" . count($userMoney) . "<br>";
    // echo "总值：" . array_sum($userMoney) . "<br>";
    return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}

3.2 使用 array_rand 优化后算法

//利用array_rand一次拿出多个随机值时，随机且去重,且随机区间包括首尾。
function lineSegmentOptimize($Moneys, $userNums, $isEveryHave = 1) //$baseMoney = 1默认为1
{
    if ($Moneys <= 0 || $userNums <= 0) {
        return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
    }
    if ($isEveryHave && $userNums > $Moneys) {
        return ['code' => -4, 'msg' => '红包数量不足'];
    }

    $cutPoints = [];
    $userMoney = [];

    if ($isEveryHave) {
        $MoneysArr = array_fill(1, $Moneys - 1, 0); //转成数组时,去掉头尾得-1，如果10，则下标是1-9
    } else {
        $MoneysArr = array_fill(0, $Moneys + 1, 0); //转成数组,为了保留头尾得+1，如果10，则下标是0-10，array_rand区间包含首尾
    }

    if ($userNums == 1) {
        $userMoney[] = $Moneys;
        return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
    }

    $cutPoints = array_rand($MoneysArr, $userNums - 1); //多随机、且去重、且区间包含首尾，array_rand第二个值不可为0
    sort($cutPoints);
    $lastVal = 0;
    foreach ($cutPoints as  $randPoint) {
        $diff = $randPoint - $lastVal;
        $userMoney[] =  $diff;
        $lastVal = $randPoint;
    }
    $lastDiff = $Moneys - $lastVal;
    $userMoney[] =  $lastDiff;

    // echo "总数：" . count($userMoney) . "<br>";
    // var_dump($userMoney);
    // echo "总值：" . array_sum($userMoney) . "<br>";
    return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}

04、验证 array_rand 随机特性

在写线段分割算法时，发现当全区间 mt_rand 后，出现重复切点需要去重，生成非重复的切点。这里第一时间想到了使用 array_rand，但不确定 array_rand 的随机特性，不知道它的随机特性是否有去重处理。经过验证，array_rand($arr, 8) 同时随机取多个索引下标时有去重处理，且随机特性很好。

事实证明 array_rand 一次拿出多个随机值时，随机且去重，且随机区间包括首尾。

$res = checkRand(10, 10000);
var_dump($res);
function checkRand($range, $num)
{
    $statiArr = array_fill(0, 100, 0);
    $sourceArr = range(0, 99);
    for ($i = 0; $i < 10000; $i++) {
        $indexArr = array_rand($sourceArr, 4); //array_rand随机性可以，且去重性也可以
        
        foreach ($indexArr as $index) {    //中途也用array_unique统计，是否单把拿值重复
            $statiArr[$index]++;
        }
    }
    return $statiArr;
}

一次随机取2个时，平均200左右
array(100) { [0]=> int(196) [1]=> int(210) [2]=> int(206) [3]=> int(202)  ，，，，[97]=> int(196) [98]=> int(197) [99]=> int(188) }

一次随机取4个时，平均400左右
array(100) { [0]=> int(372) [1]=> int(428) [2]=> int(394) [3]=> int(441) ,,,,, [97]=> int(382) [98]=> int(388) [99]=> int(358) }

一次随机取99个时，平均9900左右
array(100) { [0]=> int(9892) [1]=> int(9890) [2]=> int(9913) [3]=> int(9909) ,,,,[97]=> int(9908) [98]=> int(9903) [99]=> int(9908) }

事实证明array_rand一次拿出多个随机值时，随机且去重。

05、统计算法耗时与效果

最后，我们对全文提到的红包算法的随机性以及计算性价比进行一个整体比较。

function microTime_float()
{
    //$usec 精确到微秒  ，$sec 秒   1秒(second) = 1000毫秒(millisecond) = 1000,000微秒(microsecond)
    list($usec, $sec) = explode(' ', microtime());
    return ((float)$usec + (float)$sec); //float保留小数点后四位
}

$starTime = microTime_float();  //0.35529400 1616661516

for ($i = 0; $i < 100000; $i++) {
    lineSegmentRedbag($Moneys, $userNums, $isEveryHave);
    // lineSegmentOptimize($Moneys, $userNums, $isEveryHave);
    // doubleMeanRedbag($Moneys, $userNums, $isEveryHave);
}

$endTime = microTime_float();

$diff = floatval($endTime)  - floatval($starTime);

echo "线段分割时间差：" . floatval($diff) . "<br/>";   //时间差：0.33733010292053   //Optimize时间差：0.11269283294678
exit;