二倍均值随机算法之抢拼手气红包场景应用

拼手气类的游戏，更能激发用户购物和社交的趣味性，以及游戏竞争心理，拼手气类的活动甚至可以影响人们消费心理。
拼手气红包就是最简单的例子，哪怕你手气红包只有0.01元，在众多竞争者中脱颖而出，抢到的那一刻还是很开心的。对于没有抢到的参与者，还会不服气，想要弥补自己的遗憾，从而更积极地参与活动。

两种生成红包的方式对比

拼手气红包有两种计算方法，一种是预计算，一种是实时算。

预计算在生成拼手气红包的时候，会提前根据总金额M和红包人数N，生成每个红包的金额，在抢红包的过程中，只需要从金额列表中取出，直至取完。这种方式需要占用额外的存储空间并且增加额外的I/O，在高并发场景下并不是最优的解决方案。
实时算采用的是纯内存计算，不需要预算空间存储，实时性很高。

蒙特卡罗方法

蒙特卡罗方法是由著名科学家、“计算机科学之父”和“博弈论之父”冯·诺依曼提出的，此种方法又可称为统计模拟法、随机抽样技术，是一种以概率和统计理论方法为基础的计算方法。主要是通过将待求解的问题采用相同的概率模型进行求解，并用电子计算机实现统计模拟或抽样，以获得问题的近似解。

蒙特卡罗方法生成随机数的主要步骤如下：
（1）针对实际问题建立一个简单且便于实现的概率统计模型，使所求的量恰好是该模型的概率分布或数字特征。
（2）基于模型的随机变量建立抽样方法，在计算机上进行模拟测试，抽取足够多的随机数。 （3）对模拟实验结果进行统计分析，给出所求解的估计值，这就是最终产生的随机数。
（4）必要时，可以通过改进模型以提高估计精度和减少实验费用，最终提高模拟效率。 直白点讲，这种算法主要是通过建立一个模型，并对模型中的随机变量建立抽样方法，在计算机中反复多次进行模拟测试，最终得到一个或多个估计值，即随机数列表。

二倍均值法

蒙特卡罗方法的核心思想主要在于构造一个数学模型，并基于若干个随机变量和统计分析的方法求出若干个估计值（随机数），在某种程度上并不适用于抢红包系统生成随机金额的几率相等、随机金额之和等于总金额等要求。 然而我们却可以借助其构造数学模型的思想，将总金额M和总个数N作为模型变量，从而求得一组红包随机金额。

当用户发出固定总金额为M、红包个数为N的红包后，由于系统后端采用的是预生成方式，因而将在后端生成N个随机金额的小红包并存储至缓存中，等待着被抢。 小红包随机金额的产生对用户而言是透明的，用户也无须知晓红包随机金额的产生原理与规则， 因而对于抢红包系统来说，只需要保证系统后端每次对于总金额M和红包个数N生成的小红包金额是随机且平等的，即间接性地保证每个用户抢到的红包金额是随机产生且概率是平等的即可。

除了保证预生成红包金额的随机性和概率平等性之外，抢红包系统后端还需保证3点要求:
（1）应保证所有人抢到的红包金额之和等于总金额M，这一点是毋庸置疑的。
（2）每个参与抢红包的用户，当抢到红包（即红包金额不为Null）时，金额应至少是1分钱，即0.01元。
（3）应当保证参与抢红包的用户抢到红包金额时，几率是相等的，这一点由于是采用预生成的方式，因而可以交给随机数生成算法进行控制。

目前市面上关于红包随机金额的生成算法有许多种，二倍均值法属于其中比较典型的一种。

二倍均值算法可以避免随机生成的金额，部分人金额过高，导致剩余的人的金额过小的尴尬。

代码实现与测试

顾名思义，二倍均值算法的核心思想是根据每次剩余的总金额M和剩余人数N，执行M/N再乘以2的操作得到一个边界值E，然后制定一个从0到E的随机区间，在这个随机区间内将产生一个随机金额R， 此时总金额M将更新为M-R，剩余人数N更新为N-1。再继续重复上述执行流程，以此类推，直至最终剩余人数N-1为0，即代表随机数已经产生完毕。

该算法的执行流程其实是一个for循环产生数据的过程，循环终止的条件是N-1<=0，即代表随机数已经生成完毕。 而对于随机数的生成，主要是在约束的随机区间(0,M/N×2)中产生，这样着实可以保证每次数值R产生的随机性和平等性； 除此之外，由于每次总金额M的更新采用的是递减的方式，即M=M-R，因而可以保证最终产生的所有随机金额之和等于M。

二倍均值法的核心执行逻辑在于不断地更新总金额M和剩余人数N，并根据M和N组成一个随机区间， 最终在这个区间内产生一个随机金额，如此不断地进行循环迭代，直至N-1为0，此时剩余的金额即为最后一个随机金额。

代码实现：

import com.alibaba.fastjson.JSON;
import org.apache.commons.lang3.StringUtils;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Executors;

/**
 * 二倍均值法的代码实战
 * -封装成工具类
 *
 * @author
 */
public class RedPacketUtil {

    /**
     * 发红包算法，金额参数以分为单位
     
     * @param totalAmount    红包总金额-单位为分
     * @param totalPeopleNum 总人数
     * @return
     */
    public static List<Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum) {
        //用于存储每次产生的小红包随机金额List –金额单位为分
        List<Integer> amountList = new ArrayList<Integer>();
        //判断总金额和总个数参数的合法性
        if (totalAmount > 0 && totalPeopleNum > 0) {
            //记录剩余的总金额-初始化时金额即为红包的总金额
            Integer restAmount = totalAmount;
            //记录剩余的总人数-初始化时即为指定的总人数
            Integer restPeopleNum = totalPeopleNum;
            //定义产生随机数的实例对象
            Random random = new Random();
            //不断循环遍历、迭代更新地产生随机金额，直到N-1>0
            for (int i = 0; i < totalPeopleNum - 1; i++) {
                //随机范围：[1，剩余人均金额的两倍)，左闭右开 -amount即为产生的随机金额R -单位为分
                int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
                //更新剩余的总金额 M = M - R
                restAmount -= amount;
                //更新剩余的总人数N = N - 1
                restPeopleNum--;
                //将产生的随机金额添加进列表List中
                amountList.add(amount);
            }
            //循环完毕，剩余的金额即为最后一个随机金额，也需要将其添加进列表中
            amountList.add(restAmount);
        }
        //将最终产生的随机金额列表返回
        return amountList;
    }

    public static void divideRedPackageTester() {
        //总金额单位为分，在这里假设总金额为1000分，即10元
        Integer amount = new Random().nextInt(20000) + 1;
        if (amount < 10) {
            amount += 10;
        }
        //总人数即红包总个数，在这里假设为10个
        Integer total = new Random().nextInt(10) + 1;
        //调用二倍均值法工具类中产生随机金额列表的方法得到小红包随机金额列表
        List<Integer> list = RedPacketUtil.divideRedPackage(amount, total);
        System.out.println(String.format("%s总金额=%d分，即%s元，总个数=%d个",Thread.currentThread().getName(),
                amount, new BigDecimal(amount.toString()).divide(new BigDecimal("100")), total));
        //用于统计生成的随机金额之和是否等于总金额
        Integer sum = 0;
        //遍历输出每个随机金额
        for (Integer i : list) {
            //输出随机金额时包括单位为分和单位为元的信息
            //String s = String.format("随机金额为：%d分，即%s元 ", i, new BigDecimal(i.toString()).divide(new BigDecimal("100")));
            //System.out.println(s);
            sum += i;
        }
        System.out.println(String.format("%s所有随机金额叠加之和=%d分，即%s元", Thread.currentThread().getName(),sum, new BigDecimal(sum.toString()).divide(new BigDecimal("100"))));
        if (!sum.equals(amount)) {
            System.out.println(String.format("%s!!!!!!!!fail!!!!!!!!",Thread.currentThread().getName()));
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                divideRedPackageTester();
            }).start();
        }
    }

}

参考资料

• 《分布式中间件技术实战：Java版》
• 微信红包金额分配的算法 https://timyang.net/architecture/wechat-red-packet/
• 微信红包的架构设计简介 https://www.zybuluo.com/yulin718/note/93148