社交软件红包技术解密(十三):微信团队首次揭秘微信红包算法,为何你抢到的是0.01元

本文涉及的产品
图片翻译,图片翻译 100张
文本翻译,文本翻译 100万字符
文档翻译,文档翻译 1千页
简介: 本文中,我们将介绍几种主流的IM红包分配算法,相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。

本文由腾讯梁中原分享,原题“红包算法揭秘!哪段代码让你只抢了0.01元?”,下文进行了排版和内容优化等。

1、引言

在上一篇《来看看微信十年前的IM消息收发架构,你做到了吗》的文章中,有用户提到想了解自己每次微信红包只能抽中 0.01 元的反向手气最佳是怎么在技术上实现的,于是就有了本篇文章的诞生。

其实,微信红包最初在产品设计上有过很多思路,最初曾以多档次、按比例分配的方式,但最后大家试用下来发现还是随机才好玩。那种看到有人抢到 100 块,有人 0.01 元的快乐无以言喻。

最初的随机算法中,领取越早获得大额红包几率越高,为了避免抢红包变成一个拼手速的游戏,后来的随机算法也对随机范围区间进行了一定调整。

本文中,我们将介绍几种主流的IM红包分配算法,相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。

 

 

技术交流:

- 移动端IM开发入门文章:《新手入门一篇就够:从零开发移动端IM

- 开源IM框架源码:https://github.com/JackJiang2011/MobileIMSDK备用地址点此

(本文已同步发布于:http://www.52im.net/thread-4661-1-1.html

2、系列文章

社交软件红包技术解密(一):全面解密QQ红包技术方案——架构、技术实现等

社交软件红包技术解密(二):解密微信摇一摇红包从0到1的技术演进

社交软件红包技术解密(三):微信摇一摇红包雨背后的技术细节

社交软件红包技术解密(四):微信红包系统是如何应对高并发的

社交软件红包技术解密(五):微信红包系统是如何实现高可用性的

社交软件红包技术解密(六):微信红包系统的存储层架构演进实践

社交软件红包技术解密(七):支付宝红包的海量高并发技术实践

社交软件红包技术解密(八):全面解密微博红包技术方案

社交软件红包技术解密(九):谈谈手Q春节红包的设计、容灾、运维、架构等

社交软件红包技术解密(十):手Q客户端针对2020年春节红包的技术实践

社交软件红包技术解密(十一):最全解密微信红包随机算法(含演示代码)

社交软件红包技术解密(十二):解密抖音春节红包背后的技术设计与实践

社交软件红包技术解密(十三):微信团队首次揭秘微信红包算法,为何你抢到的是0.01元》(* 本文)

3、主流的红包算法1:普通随机法

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

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

以下是算法示例:

// 剩余值随机 ,优点:逻辑简单,缺点:随机区间步步减少,可以明显看出随机值的递减特性,

对后面玩家极不公平,且容易被抓到规律,造成舆论不满。

// 做抢红包体验很差,稍微弥补一点的方案: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];

}

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

4、主流的红包算法2:二倍均值算法

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

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

以下是算法示例:

$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];

}

5、主流的红包算法3:线段分割算法

线段分割是相对合理的红包算法,但实现逻辑会更复杂一些。

红包金额如果想随机分成 N 份,可以处理为:一个线段,随机选择 N-1 点进行切割。

以下内容将详细讲解线段分割算法。

6、常规线段分割算法

以下是常规线段分割算法示例:

//线段分割算法  -- 有个致命缺陷,随机值碰撞,分割数量越接近总金额,碰撞概率越大 ,所以最好 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];

}

7、使用array_rand优化后的线段分割算法

以下是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];

}

8、验证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左右:

1 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左右:

1array(100) { [0]=> int(372) [1]=> int(428) [2]=> int(394) [3]=> int(441) ,,,,, [97]=> int(382) [98]=> int(388) [99]=> int(358) }

一次随机取99个时,平均9900左右:

1array(100) { [0]=> int(9892) [1]=> int(9890) [2]=> int(9913) [3]=> int(9909) ,,,,[97]=> int(9908) [98]=> int(9903) [99]=> int(9908) }

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

9、主流的红包算法的耗时和效果对比

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

以下是测试代码:

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;

 

如上图所示:线段分割算法与二倍均值相比,随机区间更大。

如上图所示:线段分割普通版,随着红包总额与红包人数相近时(即切点接近总值时),随机碰撞率显著升高,性能下降。但经过优化后的线段分割算法,性能比二倍均值还优秀。

10、参考资料

[1] 微信红包随机算法初探

[2] 微信红包算法的分析

[3] 微信红包的架构设计简介

[4] 微信红包的随机算法是怎样实现的?

[5] IM开发宝典:史上最全,微信各种功能参数和逻辑规则资料汇总

[6] 微信本地数据库破解版(含iOS、Android),仅供学习研究 [附件下载]

[7] 全面解密QQ红包技术方案——架构、技术实现等

[8] 解密微信摇一摇红包从0到1的技术演进

[9] 微信摇一摇红包雨背后的技术细节

[10] 微信红包系统是如何应对高并发的

[11] 微信红包系统是如何实现高可用性的

[12] 微信红包系统的存储层架构演进实践

[13] 支付宝红包的海量高并发技术实践

[14] 全面解密微博红包技术方案

[15] 谈谈手Q红包的功能逻辑、容灾、运维、架构等

[16] 手Q客户端针对2020年春节红包的技术实践

[17] 解密微信红包随机算法(含代码实现)

[18] 解密抖音春节红包背后的技术设计与实践

11、更多鹅厂技术文章汇总

 

(本文已同步发布于:http://www.52im.net/thread-4661-1-1.html

目录
相关文章
|
11天前
|
算法 安全 搜索推荐
AES(Advanced Encryption Standard)是一种广泛使用的对称密钥加密算法,由美国国家标准技术研究所(NIST)制定。
AES(Advanced Encryption Standard)是一种广泛使用的对称密钥加密算法,由美国国家标准技术研究所(NIST)制定。
|
19天前
|
安全 API Windows
支付系统13------支付系统的资料在技术库里的在线支付当中,怎样获取微信平台证书那?怎样获取微信平台证书那?第一步打开我们的微信支付平台的文档中心
支付系统13------支付系统的资料在技术库里的在线支付当中,怎样获取微信平台证书那?怎样获取微信平台证书那?第一步打开我们的微信支付平台的文档中心
|
26天前
|
存储 算法 Java
技术笔记:JVM的垃圾回收机制总结(垃圾收集、回收算法、垃圾回收器)
技术笔记:JVM的垃圾回收机制总结(垃圾收集、回收算法、垃圾回收器)
19 1
|
27天前
|
传感器 算法
技术心得记录:四元数及姿态解算Mahony算法
技术心得记录:四元数及姿态解算Mahony算法
26 0
|
27天前
|
机器学习/深度学习 算法 数据可视化
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
26 0
|
27天前
|
存储 算法 Python
技术心得记录:大整数算法【10】Comba乘法(实现)
技术心得记录:大整数算法【10】Comba乘法(实现)
14 0
|
27天前
|
Java BI C#
技术笔记:SM4加密算法实现Java和C#相互加密解密
技术笔记:SM4加密算法实现Java和C#相互加密解密
17 0
|
27天前
|
机器学习/深度学习 并行计算 搜索推荐
程序技术好文:桶排序算法及其Java实现
程序技术好文:桶排序算法及其Java实现
18 0
|
27天前
|
算法
技术好文共享:算法之树表的查找
技术好文共享:算法之树表的查找
16 0
|
27天前
|
XML 小程序 前端开发
技术心得记录:微信小程序开发的基本流程
技术心得记录:微信小程序开发的基本流程
22 0

热门文章

最新文章