微信红包随机算法转载

2023-08-14 19:05:52

php固定红包 + 随机红包算法

1 需求
CleverCode最近接到一个需求，需要写一个固定红包 + 随机红包算法。

1 固定红包就是每个红包金额一样，有多少个就发多少个固定红包金额就行。

2 随机红包的需求是。比如红包总金额5元，需要发10个红包。随机范围是 0.01到0.99；5元必需发完，金额需要有一定趋势的正态分布。（0.99可以任意指定，也可以是 avg * 2 - 0.01；比如avg = 5 / 10 = 0.5；（avg * 2 - 0.01 = 0.99））

2 需求分析
2.1 固定红包
如果是固定红包，则算法是一条直线。t就是固定红包的额度。如图。
f(x) = t;（1 <= x <= num）

2.2 随机红包
如果我们使用随机函数rand。rand(0.01,0.99)；那么10次随机，如果最坏情况都是金额0.99，总金额就是9.9元。会超过5元。金额也会不正态分布。最后思考了一下借助与数学函数来当作随机红包的发生器，可以用抛物线，三角函数。最后选定了等腰三角线性函数。

1 算法原理

如果需要发红包总金额是totalMoney，红包个数是num个，金额范围是[min,max]，线性方程如图。

三个点的坐标：

（x1,y1） = (1,min)

(x2,y2) = (num/2,max)

(x3,y3) = (num,min)

确定的线性方程：

$y = 1.0 * ($x - $x1) / ($x2 - $x1) * ($y2 - $y1) + $y1 ; （x1 <= x <= x2）
$y = 1.0 * ($x - $x2) / ($x3 - $x2) * ($y3 - $y2) + $y2; （x2 <= x <= x3）

修数据：
y(合) = y1 + y2 + y3 +...... ynum；
y(合)有可能 > totalMoney ，说明生成金额多了，需要修数据，则从(y1,y2,y3.....ynum)这些每次减少0.01。直到y(合) = totalMoney。
y(合)有可能 < totalMoney ，说明生成金额少了，需要修数据，则从(y1,y2,y3.....ynum)这些每次加上0.01。直到y(合) = totalMoney。

2 算法原理样例

如果需要发红包总金额是11470，红包个数是7400个，金额范围是[0.01,3.09]，线性方程如图。

3 需求设计
3.1 类图设计

3.2 源码设计
<?php
/**
* 随机红包+固定红包算法[策略模式]
* copyright (c) 2016 http://blog.csdn.net/CleverCode
*/

//配置传输数据DTO
class OptionDTO
{/*{{{*/

//红包总金额
public $totalMoney;

//红包数量
public $num;

//范围开始
public $rangeStart;

//范围结算
public $rangeEnd;

//生成红包策略
public $builderStrategy;

//随机红包剩余规则
public $randFormatType; //Can_Left：不修数据,可以有剩余；No_Left：不能有剩余

public static function create($totalMoney,$num,$rangeStart,$rangEnd,
$builderStrategy,$randFormatType = 'No_Left')
{/*{{{*/
$self = new self();
$self->num = $num;
$self->rangeStart = $rangeStart;
$self->rangeEnd = $rangEnd;
$self->totalMoney = $totalMoney;
$self->builderStrategy = $builderStrategy;
$self->randFormatType = $randFormatType;
return $self;
}/*}}}*/

}/*}}}*/

//红包生成器接口
interface IBuilderStrategy
{/*{{{*/
//创建红包
public function create();
//设置配置
public function setOption(OptionDTO $option);
//是否可以生成红包
public function isCanBuilder();
//生成红包函数
public function fx($x);
}/*}}}*/

//固定等额红包策略
class EqualPackageStrategy implements IBuilderStrategy
{/*{{{*/
//单个红包金额
public $oneMoney;

//数量
public $num;

public function __construct($option = null)
{
if($option instanceof OptionDTO)
{
$this->setOption($option);
}
}

public function setOption(OptionDTO $option)
{
$this->oneMoney = $option->rangeStart;
$this->num = $option->num;
}

public function create()
{/*{{{*/

$data = array();
if(false == $this->isCanBuilder())
{
return $data;
}

$data = array();
if(false == is_int($this->num) || $this->num <= 0)
{
return $data;
}
for($i = 1;$i <= $this->num;$i++)
{
$data[$i] = $this->fx($i);
}
return $data;
}/*}}}*/

/**
* 等额红包的方程是一条直线
*
* @param mixed $x
* @access public
* @return void
*/
public function fx($x)
{/*{{{*/
return $this->oneMoney;
}/*}}}*/

/**
* 是否能固定红包
*
* @access public
* @return void
*/
public function isCanBuilder()
{/*{{{*/
if(false == is_int($this->num) || $this->num <= 0)
{
return false;
}

if(false == is_numeric($this->oneMoney) || $this->oneMoney <= 0)
{
return false;
}

//单个红包小于1分
if($this->oneMoney < 0.01)
{
return false;
}

return true;

}/*}}}*/

}/*}}}*/

//随机红包策略(三角形)
class RandTrianglePackageStrategy implements IBuilderStrategy
{/*{{{*/
//总额
public $totalMoney;

//红包数量
public $num;

//随机红包最小值
public $minMoney;

//随机红包最大值
public $maxMoney;

//修数据方式：NO_LEFT: 红包总额 = 预算总额；CAN_LEFT: 红包总额 <= 预算总额
public $formatType;

//预算剩余金额
public $leftMoney;

public function __construct($option = null)
{/*{{{*/
if($option instanceof OptionDTO)
{
$this->setOption($option);
}
}/*}}}*/

public function setOption(OptionDTO $option)
{/*{{{*/
$this->totalMoney = $option->totalMoney;
$this->num = $option->num;
$this->formatType = $option->randFormatType;
$this->minMoney = $option->rangeStart;
$this->maxMoney = $option->rangeEnd;
$this->leftMoney = $this->totalMoney;
}/*}}}*/

/**
* 创建随机红包
*
* @access public
* @return void
*/
public function create()
{/*{{{*/

$data = array();
if(false == $this->isCanBuilder())
{
return $data;
}

$leftMoney = $this->leftMoney;
for($i = 1;$i <= $this->num;$i++)
{
$data[$i] = $this->fx($i);
$leftMoney = $leftMoney - $data[$i];
}

//修数据
list($okLeftMoney,$okData) = $this->format($leftMoney,$data);

//随机排序
shuffle($okData);
$this->leftMoney = $okLeftMoney;

return $okData;
}/*}}}*/

/**
* 是否能够发随机红包
*
* @access public
* @return void
*/
public function isCanBuilder()
{/*{{{*/
if(false == is_int($this->num) || $this->num <= 0)
{
return false;
}

if(false == is_numeric($this->totalMoney) || $this->totalMoney <= 0)
{
return false;
}

//均值
$avgMoney = $this->totalMoney / 1.0 / $this->num;

//均值小于最小值
if($avgMoney < $this->minMoney )
{
return false;
}

return true;

}/*}}}*/

/**
* 获取剩余金额
*
* @access public
* @return void
*/
public function getLeftMoney()
{/*{{{*/
return $this->leftMoney;
}/*}}}*/

/**
* 随机红包生成函数。三角函数。[(1,0.01),($num/2,$avgMoney),($num,0.01)]
*
* @param mixed $x,1 <= $x <= $this->num;
* @access public
* @return void
*/
public function fx($x)
{/*{{{*/

if(false == $this->isCanBuilder())
{
return 0;
}

if($x < 1 || $x > $this->num)
{
return 0;
}

$x1 = 1;
$y1 = $this->minMoney;

//我的峰值
$y2 = $this->maxMoney;

//中间点
$x2 = ceil($this->num / 1.0 / 2);

//最后点
$x3 = $this->num;
$y3 = $this->minMoney;

//当x1,x2,x3都是1的时候(竖线)
if($x1 == $x2 && $x2 == $x3)
{
return $y2;
}

// '/_\'三角形状的线性方程
//'/'部分
if($x1 != $x2 && $x >= $x1 && $x <= $x2)
{

$y = 1.0 * ($x - $x1) / ($x2 - $x1) * ($y2 - $y1) + $y1;
return number_format($y, 2, '.', '');
}

//'\'形状
if($x2 != $x3 && $x >= $x2 && $x <= $x3)
{

$y = 1.0 * ($x - $x2) / ($x3 - $x2) * ($y3 - $y2) + $y2;
return number_format($y, 2, '.', '');
}

return 0;

}/*}}}*/

/**
* 格式化修红包数据
*
* @param mixed $leftMoney
* @param array $data
* @access public
* @return void
*/
private function format($leftMoney,array $data)
{/*{{{*/

//不能发随机红包
if(false == $this->isCanBuilder())
{
return array($leftMoney,$data);
}

//红包剩余是0
if(0 == $leftMoney)
{
return array($leftMoney,$data);
}

//数组为空
if(count($data) < 1)
{
return array($leftMoney,$data);
}

//如果是可以有剩余，并且$leftMoney > 0
if('Can_Left' == $this->formatType
&& $leftMoney > 0)
{
return array($leftMoney,$data);
}

//我的峰值
$myMax = $this->maxMoney;

// 如果还有余钱，则尝试加到小红包里，如果加不进去，则尝试下一个。
while($leftMoney > 0)
{
$found = 0;
foreach($data as $key => $val)
{
//减少循环优化
if($leftMoney <= 0)
{
break;
}

//预判
$afterLeftMoney = (double)$leftMoney - 0.01;
$afterVal = (double)$val + 0.01;
if( $afterLeftMoney >= 0 && $afterVal <= $myMax)
{
$found = 1;
$data[$key] = number_format($afterVal,2,'.','');
$leftMoney = $afterLeftMoney;
//精度
$leftMoney = number_format($leftMoney,2,'.','');
}
}

//如果没有可以加的红包，需要结束,否则死循环
if($found == 0)
{
break;
}
}
//如果$leftMoney < 0 ,说明生成的红包超过预算了，需要减少部分红包金额
while($leftMoney < 0)
{
$found = 0;
foreach($data as $key => $val)
{
if($leftMoney >= 0)
{
break;
}
//预判

$afterLeftMoney = (double)$leftMoney + 0.01;
$afterVal = (double)$val - 0.01;
if( $afterLeftMoney <= 0 && $afterVal >= $this->minMoney)
{
$found = 1;
$data[$key] = number_format($afterVal,2,'.','');
$leftMoney = $afterLeftMoney;
$leftMoney = number_format($leftMoney,2,'.','');
}
}

//如果一个减少的红包都没有的话，需要结束，否则死循环
if($found == 0)
{
break;
}
}
return array($leftMoney,$data);
}/*}}}*/

}/*}}}*/

//维护策略的环境类
class RedPackageBuilder
{/*{{{*/

// 实例
protected static $_instance = null;

/**
* Singleton instance（获取自己的实例）
*
* @return MemcacheOperate
*/
public static function getInstance()
{ /*{{{*/
if (null === self::$_instance)
{
self::$_instance = new self();
}
return self::$_instance;
} /*}}}*/

/**
* 获取策略【使用反射】
*
* @param string $type 类型
* @return void
*/
public function getBuilderStrategy($type)
{ /*{{{*/
$class = $type.'PackageStrategy';

if(class_exists($class))
{
return new $class();
}
else
{
throw new Exception("{$class} 类不存在！");
}
} /*}}}*/

public function getRedPackageByDTO(OptionDTO $optionDTO)
{/*{{{*/
//获取策略
$builderStrategy = $this->getBuilderStrategy($optionDTO->builderStrategy);

//设置参数
$builderStrategy->setOption($optionDTO);

return $builderStrategy->create();
}/*}}}*/

}/*}}}*/

class Client
{/*{{{*/
public static function main($argv)
{
//固定红包
$dto = OptionDTO::create(1000,10,100,100,'Equal');
$data = RedPackageBuilder::getInstance()->getRedPackageByDTO($dto);
//print_r($data);

//随机红包[修数据]
$dto = OptionDTO::create(5,10,0.01,0.99,'RandTriangle');
$data = RedPackageBuilder::getInstance()->getRedPackageByDTO($dto);
print_r($data);

//随机红包[不修数据]
$dto = OptionDTO::create(5,10,0.01,0.99,'RandTriangle','Can_Left');
$data = RedPackageBuilder::getInstance()->getRedPackageByDTO($dto);
//print_r($data);

}
}/*}}}*/

Client::main($argv);

3.3 结果展示
1 固定红包

//固定红包
$dto = OptionDTO::create(1000,10,100,100,'Equal');
$data = RedPackageBuilder::getInstance()->getRedPackageByDTO($dto);
print_r($data);

2 随机红包（修数据）

这里使用了php的随机排序函数， shuffle($okData)，所以看到的结果不是线性的，这个结果更加随机性。

//随机红包[修数据]
$dto = OptionDTO::create(5,10,0.01,0.99,'RandTriangle');
$data = RedPackageBuilder::getInstance()->getRedPackageByDTO($dto);
print_r($data);

3 随机红包（不修数据）

不修数据，1 和num的金额是最小值0.01。

//随机红包[不修数据]
$dto = OptionDTO::create(5,10,0.01,0.99,'RandTriangle','Can_Left');
$data = RedPackageBuilder::getInstance()->getRedPackageByDTO($dto);
print_r($data);

---------------------
作者：CleverCode
来源：CSDN
原文：https://blog.csdn.net/clevercode/article/details/53239681
版权声明：本文为博主原创文章，转载请附上博文链接！

微信红包随机生成算法（PHP版）

最近在研究发红包的功能，于是写了个红包的生成算法。

红包生成算法的需求
预先生成所有的红包还是一个请求随机生成一个红包
简单来说，就是把一个大整数m分解（直接以“分为单位，如1元即100）分解成n个小整数的过程，小整数的范围是[min, max]。

最简单的思路，先保底，每个小红包保证有min，然后每个请求都随机生成一个0到(max-min)范围的整数，再加上min就是红包的钱数。

这个算法虽然简单，但是有一个弊端：最后生成的红包可能都是min钱数的。也就是说可能最后的红包都是0.01元的。

另一种方式是预先生成所有红包，这样就比较容易控制了。我选择的是预先生成所有的红包。

理想的红包生成算法
理想的红包生成结果是平均值附近的红包比较多，大红包和小红包的数量比较少。

可以想像下，生成红包的数量的分布有点像正态分布。

那么如何实现这种平均线附近值比较多的要求呢？

就是要找到一种算法，可以提高平均值附近的概率。那么利用一种”膨胀“再”收缩“的方式来达到这种效果。

先平方，再生成平方范围内的随机数，再开方，那么概率就不再是平均的了。

具体算法：（设置的总钱数，总人数，最大值，最小值要合理）

/**
* 求一个数的平方
* @param $n
*/
function sqr($n){
return $n*$n;
}

/**
* 生产min和max之间的随机数，但是概率不是平均的，从min到max方向概率逐渐加大。
* 先平方，然后产生一个平方值范围内的随机数，再开方，这样就产生了一种“膨胀”再“收缩”的效果。
*/
function xRandom($bonus_min,$bonus_max){
$sqr = intval(sqr($bonus_max-$bonus_min));
$rand_num = rand(0, ($sqr-1));
return intval(sqrt($rand_num));
}

/**
*
* @param $bonus_total 红包总额
* @param $bonus_count 红包个数
* @param $bonus_max 每个小红包的最大额
* @param $bonus_min 每个小红包的最小额
* @return 存放生成的每个小红包的值的一维数组
*/
function getBonus($bonus_total, $bonus_count, $bonus_max, $bonus_min) {
$result = array();

$average = $bonus_total / $bonus_count;

$a = $average - $bonus_min;
$b = $bonus_max - $bonus_min;

//
//这样的随机数的概率实际改变了，产生大数的可能性要比产生小数的概率要小。
//这样就实现了大部分红包的值在平均数附近。大红包和小红包比较少。
$range1 = sqr($average - $bonus_min);
$range2 = sqr($bonus_max - $average);

for ($i = 0; $i < $bonus_count; $i++) {
//因为小红包的数量通常是要比大红包的数量要多的，因为这里的概率要调换过来。
//当随机数>平均值，则产生小红包
//当随机数<平均值，则产生大红包
if (rand($bonus_min, $bonus_max) > $average) {
// 在平均线上减钱
$temp = $bonus_min + xRandom($bonus_min, $average);
$result[$i] = $temp;
$bonus_total -= $temp;
} else {
// 在平均线上加钱
$temp = $bonus_max - xRandom($average, $bonus_max);
$result[$i] = $temp;
$bonus_total -= $temp;
}
}
// 如果还有余钱，则尝试加到小红包里，如果加不进去，则尝试下一个。
while ($bonus_total > 0) {
for ($i = 0; $i < $bonus_count; $i++) {
if ($bonus_total > 0 && $result[$i] < $bonus_max) {
$result[$i]++;
$bonus_total--;
}
}
}
// 如果钱是负数了，还得从已生成的小红包中抽取回来
while ($bonus_total < 0) {
for ($i = 0; $i < $bonus_count; $i++) {
if ($bonus_total < 0 && $result[$i] > $bonus_min) {
$result[$i]--;
$bonus_total++;
}
}
}
return $result;
}
$bonus_total = 200;
$bonus_count = 100;
$bonus_max = 10;//此算法要求设置的最大值要大于平均值
$bonus_min = 1;
$result_bonus = getBonus($bonus_total, $bonus_count, $bonus_max, $bonus_min);
$total_money = 0;
$arr = array();
foreach ($result_bonus as $key => $value) {
$total_money += $value;
if(isset($arr[$value])){
$arr[$value] += 1;
}else{
$arr[$value] = 1;
}

}
//输出总钱数，查看是否与设置的总数相同
echo $total_money;
//输出所有随机红包值
var_dump($result_bonus);
//统计每个钱数的红包数量，检查是否接近正态分布
ksort($arr);
var_dump($arr);

原文：http://mulandong.duapp.com/?m=post&id=21
---------------------
作者：iteye_5904
来源：CSDN
原文：https://blog.csdn.net/iteye_5904/article/details/82618957
版权声明：本文为博主原创文章，转载请附上博文链接！

https://www.cnblogs.com/lhat/p/6359039.html

最近看了一篇文章，讲微信红包随机算法的。感觉很不错，所以自己实现了下，并进行了简单测试。

算法

算法很简单，不是提前算好，而是抢红包时计算：

红包里的金额怎么算？为什么出现各个红包金额相差很大？
答：随机，额度在0.01和剩余平均值*2之间。

实现

实现上述算法的逻辑主要是：

 1 public static double getRandomMoney(RedPackage _redPackage) {
 2     // remainSize 剩余的红包数量
 3     // remainMoney 剩余的钱
 4     if (_redPackage.remainSize == 1) {
 5         _redPackage.remainSize--;
 6         return (double) Math.round(_redPackage.remainMoney * 100) / 100;
 7     }
 8     Random r     = new Random();
 9     double min   = 0.01; //
10     double max   = _redPackage.remainMoney / _redPackage.remainSize * 2;
11     double money = r.nextDouble() * max;
12     money = money <= min ? 0.01: money;
13     money = Math.floor(money * 100) / 100;
14     _redPackage.remainSize--;
15     _redPackage.remainMoney -= money;
16     return money;
17 }

RedPackage数据结构如下：

class RedPackage {
    int    remainSize;
    double remainMoney;
}

测试时初始化相关数据是：

static void init() {
    redPackage.remainSize  = 30;
    redPackage.remainMoney = 500;
}

测试结果

单词测试随机红包

以上面的初始化数据（30人抢500块），执行了两次，结果如下：

// 第一次
15.69    21.18    24.11    30.85    0.74    20.85    2.96    13.43    11.12    24.87    1.86    19.62    5.97    29.33    3.05    26.94    18.69    34.47    9.4    29.83    5.17    24.67    17.09    29.96    6.77    5.79    0.34    23.89    40.44    0.92

// 第二次
10.44    18.01    17.01    21.07    11.87    4.78    30.14    32.05    16.68    20.34    12.94    27.98    9.31    17.97    12.93    28.75    12.1    12.77    7.54    10.87    4.16    25.36    26.89    5.73    11.59    23.91    17.77    15.85    23.42    9.77

对应图表如下：

还有一张：

多次均值

可以看到，这个算法可以让大家抢到的红包面额在概率上是大致均匀的。

转一下原文

微信红包的架构设计简介

@来源于QCon某高可用架构群整理，整理朱玉华。

背景：有某个朋友在朋友圈咨询微信红包的架构，于是乎有了下面的文字（有误请提出，谢谢）

概况：2014年微信红包使用数据库硬抗整个流量，2015年使用cache抗流量。

微信的金额什么时候算？

答：微信金额是拆的时候实时算出来，不是预先分配的，采用的是纯内存计算，不需要预算空间存储。
采取实时计算金额的考虑：预算需要占存储，实时效率很高，预算才效率低。

实时性：为什么明明抢到红包，点开后发现没有？

答：2014年的红包一点开就知道金额，分两次操作，先抢到金额，然后再转账。
2015年的红包的拆和抢是分离的，需要点两次，因此会出现抢到红包了，但点开后告知红包已经被领完的状况。进入到第一个页面不代表抢到，只表示当时红包还有。

分配：红包里的金额怎么算？为什么出现各个红包金额相差很大？

答：随机，额度在0.01和(剩余平均值*2)之间。
例如：发100块钱，总共10个红包，那么平均值是10块钱一个，那么发出来的红包的额度在0.01元～20元之间波动。
当前面3个红包总共被领了40块钱时，剩下60块钱，总共7个红包，那么这7个红包的额度在：0.01～（60/7*2）=17.14之间。
注意：这里的算法是每被抢一个后，剩下的会再次执行上面的这样的算法（Tim老师也觉得上述算法太复杂，不知基于什么样的考虑）。

这样算下去，会超过最开始的全部金额，因此到了最后面如果不够这么算，那么会采取如下算法：保证剩余用户能拿到最低1分钱即可。

如果前面的人手气不好，那么后面的余额越多，红包额度也就越多，因此实际概率一样的。

红包的设计

答：微信从财付通拉取金额数据郭莱，生成个数/红包类型/金额放到redis集群里，app端将红包ID的请求放入请求队列中，如果发现超过红包的个数，直接返回。根据红包的裸祭(逻辑)处理成功得到令牌请求，则由财付通进行一致性调用，通过像比特币一样，两边保存交易记录，交易后交给第三方服务审计，如果交易过程中出现不一致就强制回归。

发性处理：红包如何计算被抢完？

答：cache会抵抗无效请求，将无效的请求过滤掉，实际进入到后台的量不大。cache记录红包个数，原子操作进行个数递减，到0表示被抢光。财付通按照20万笔每秒入账准备，但实际还不到8万每秒。

通如何保持8w每秒的写入？

答：多主sharding，水平扩展机器。

据容量多少？

答：一个红包只占一条记录，有效期只有几天，因此不需要太多空间。

询红包分配，压力大不？

答：抢到红包的人数和红包都在一条cache记录上，没有太大的查询压力。

一个红包一个队列？

答：没有队列，一个红包一条数据，数据上有一个计数器字段。

有没有从数据上证明每个红包的概率是不是均等？

答：不是绝对均等，就是一个简单的拍脑袋算法。

拍脑袋算法，会不会出现两个最佳？

答：会出现金额一样的，但是手气最佳只有一个，先抢到的那个最佳。

每领一个红包就更新数据么？

答：每抢到一个红包，就cas更新剩余金额和红包个数。

红包如何入库入账？

数据库会累加已经领取的个数与金额，插入一条领取记录。入账则是后台异步操作。

入帐出错怎么办？比如红包个数没了，但余额还有？

答：最后会有一个take all操作。另外还有一个对账来保障。

转载自微信红包随机算法初探

码农公寓