51Testing软件测试论坛

标题: Java实例：通过二倍均值法模拟微信抢红包 [打印本页]
作者: lsekfe    时间: 2022-4-24 09:29
标题: Java实例：通过二倍均值法模拟微信抢红包
　说到抢红包，大家肯定是很熟悉了，尤其是微信抢红包，我们几乎天天都会接触。虽然每次抢到的红包金额有大有小，但是我们都深深的沉浸在抢红包的快乐中。不过话说回来，不知道各位小伙伴有没有思考过抢红包使用的是什么算法呢？是如何实现的呢？今天我们一探究竟...
　　抢红包
　　现在我们发放的红包无非就是两种形式：拼手气红包和固定金额红包。固定金额红包的个数可以是一个也可以是多个，而且每一个红包里的金额都是一样的，所以也就不需要使用过多的算法去计算红包金额，相对来说就简单一些；而拼手气红包就相对复杂一些了，它需要计算每个红包的金额，而且要保证每个红包尽量公平，这也就对算法的要求比较高了。通过查阅百度和咨询实现过抢红包功能的朋友，了解到现在使用频率比较高的算法就是二倍均值法，下面我们就使用二倍均值法来模拟实现抢红包功能。
　　通过二倍均值法模拟抢红包
　　首先我们先看一下拼手气红包的功能要求：
　　·所有红包累计金额等于红包总金额
　　· 每个红包金额不能小于0.01元，也就是说必须保证每个用户至少能抢到一个预设的最小金额，人民币红包设置的最小金额一般是0.01元，如果是发放其他类型的红包（比如积分、其他类型货币等），则需要自定义一个最小金额
　　· 抢红包的期望收益应与先后顺序无关，即每个红包的金额大小和抢红包的先后顺序无关，保证红包尽量的公平
　　在实现上面的功能要求之前，我们还需要了解一下什么是二倍均值法：
  1. 假设红包总金额是X，红包个数为Y，每个红包的最低金额是0.01元，那么每次抢到的红包金额的范围在 (0.01, (X/Y) *2) 之间。
复制代码
咱们举个具体的例子，假如现在有10个人来抢一个金额为100元的红包，那么根据上面的公式可以得出，第一个人抢到的金额范围是在（0.01，20）之间，那么根据正态分布可以得知，第一个人抢到的金额应该是在10元左右，并且远小于10元和远大于10元的概率都会很低，这里咱们就先假设第一个人抢到了10元；这时候第二个人来抢红包了，红包中剩下90元，我们根据公式可以得出，第二个人抢到的红包金额范围也是（0.01，20）之间。以此类推，我们可以看出来每个人所抢到的红包金额都在10元左右，并且远小于10元和远大于10元的概率都会很低，这样就尽可能的保证了每个人抢到的金额都是相近的。
　　接下来我们来看看具体的代码：
  1. import java.math.BigDecimal;
  2. 　　import java.math.RoundingMode;
  3. 　　import java.util.Random;
  4. 　　/**
  5. 　　 * 通过二倍均值法模拟微信抢红包
  6. 　　 * @description: RedEnvelope
  7. 　　 * @author: 庄霸.liziye
  8. 　　 * @create: 2022-02-15 14:43
  9. 　　 **/
  10. 　　public class RedEnvelope {
  11. 　　    public static void main(String[] args) {
  12. 　　        long startTime=System.currentTimeMillis();
  13. 　　        //初始化测试场景，模拟四种情况：
  14. 　　        //10人抢0.1元红包
  15. 　　        //10人抢1元红包
  16. 　　        //10人抢10元红包
  17. 　　        //10人抢100元红包
  18. 　　        BigDecimal[][] scene = {
  19. 　　                {new BigDecimal("0.1"), new BigDecimal("10")},
  20. 　　                {new BigDecimal("1"), new BigDecimal("10")},
  21. 　　                {new BigDecimal("10"), new BigDecimal("10")},
  22. 　　                {new BigDecimal("100"), new BigDecimal("10")}
  23. 　　        };
  24. 　　        //设置每个红包的最低金额为0.01元
  25. 　　        BigDecimal min = new BigDecimal("0.01");
  26. 　　        //分别测试各个红包
  27. 　　        for (BigDecimal[] decimals : scene) {
  28. 　　            final BigDecimal amount = decimals[0];
  29. 　　            final BigDecimal num = decimals[1];
  30. 　　            System.out.println("=====" + num + "个人抢一个"+ amount + "元的红包" + "=====");
  31. 　　            GrabRedEnvelope(amount, min, num);
  32. 　　        }
  33. 　　        long endTime=System.currentTimeMillis();
  34. 　　        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
  35. 　　    }
  36. 　　    //模拟抢红包过程
  37. 　　    private static void GrabRedEnvelope(BigDecimal amount, BigDecimal min, BigDecimal num){
  38. 　　        BigDecimal remain = amount.subtract(min.multiply(num));
  39. 　　        final Random random = new Random();
  40. 　　        final BigDecimal hundred = new BigDecimal("100");
  41. 　　        final BigDecimal two = new BigDecimal("2");
  42. 　　        BigDecimal sum = BigDecimal.ZERO;
  43. 　　        BigDecimal redpeck;
  44. 　　        for (int i = 0; i < num.intValue(); i++) {
  45. 　　            final int nextInt = random.nextInt(100);
  46. 　　            if(i == num.intValue() -1){
  47. 　　                redpeck = remain;
  48. 　　            }else{
  49. 　　                //RoundingMode.CEILING：取右边最近的整数
  50. 　　                //RoundingMode.FLOOR：取左边最近的正数
  51. 　　                redpeck = new BigDecimal(nextInt).multiply(remain.multiply(two).divide(num.subtract(new BigDecimal(i)),2, RoundingMode.CEILING)).divide(hundred,2, RoundingMode.FLOOR);
  52. 　　            }
  53. 　　            if(remain.compareTo(redpeck) > 0){
  54. 　　                remain = remain.subtract(redpeck);
  55. 　　            }else{
  56. 　　                remain = BigDecimal.ZERO;
  57. 　　            }
  58. 　　            sum = sum.add(min.add(redpeck));
  59. 　　            System.out.println("第"+(i+1)+"个人抢到红包金额为："+min.add(redpeck));
  60. 　　        }
  61. 　　        System.out.println("所有红包累计金额是否等于红包总金额："+compare(amount, sum));
  62. 　　    }
  63. 　　    private static boolean compare(BigDecimal a, BigDecimal b){
  64. 　　        if(a.compareTo(b) == 0){
  65. 　　            return true;
  66. 　　        }
  67. 　　        return false;
  68. 　　    }
  69. 　　}
复制代码
咱们看看代码的执行结果
  1. 　=====10个人抢一个0.1元的红包=====
  2. 　　第1个人抢到红包金额为：0.01
  3. 　　第2个人抢到红包金额为：0.01
  4. 　　第3个人抢到红包金额为：0.01
  5. 　　第4个人抢到红包金额为：0.01
  6. 　　第5个人抢到红包金额为：0.01
  7. 　　第6个人抢到红包金额为：0.01
  8. 　　第7个人抢到红包金额为：0.01
  9. 　　第8个人抢到红包金额为：0.01
  10. 　　第9个人抢到红包金额为：0.01
  11. 　　第10个人抢到红包金额为：0.01
  12. 　　所有红包累计金额是否等于红包总金额：true
  13. 　　=====10个人抢一个1元的红包=====
  14. 　　第1个人抢到红包金额为：0.06
  15. 　　第2个人抢到红包金额为：0.11
  16. 　　第3个人抢到红包金额为：0.14
  17. 　　第4个人抢到红包金额为：0.10
  18. 　　第5个人抢到红包金额为：0.06
  19. 　　第6个人抢到红包金额为：0.06
  20. 　　第7个人抢到红包金额为：0.10
  21. 　　第8个人抢到红包金额为：0.02
  22. 　　第9个人抢到红包金额为：0.13
  23. 　　第10个人抢到红包金额为：0.22
  24. 　　所有红包累计金额是否等于红包总金额：true
  25. 　　=====10个人抢一个10元的红包=====
  26. 　　第1个人抢到红包金额为：1.61
  27. 　　第2个人抢到红包金额为：1.08
  28. 　　第3个人抢到红包金额为：1.45
  29. 　　第4个人抢到红包金额为：1.35
  30. 　　第5个人抢到红包金额为：1.02
  31. 　　第6个人抢到红包金额为：0.57
  32. 　　第7个人抢到红包金额为：0.11
  33. 　　第8个人抢到红包金额为：1.16
  34. 　　第9个人抢到红包金额为：1.31
  35. 　　第10个人抢到红包金额为：0.34
  36. 　　所有红包累计金额是否等于红包总金额：true
  37. 　　=====10个人抢一个100元的红包=====
  38. 　　第1个人抢到红包金额为：10.19
  39. 　　第2个人抢到红包金额为：9.38
  40. 　　第3个人抢到红包金额为：14.47
  41. 　　第4个人抢到红包金额为：2.08
  42. 　　第5个人抢到红包金额为：2.98
  43. 　　第6个人抢到红包金额为：12.42
  44. 　　第7个人抢到红包金额为：13.81
  45. 　　第8个人抢到红包金额为：19.87
  46. 　　第9个人抢到红包金额为：8.58
  47. 　　第10个人抢到红包金额为：6.22
  48. 　　所有红包累计金额是否等于红包总金额：true
  49. 　　程序运行时间： 6ms
复制代码
我们通过执行结果可以看出，二倍均值法尽可能的保证了每个红包的金额大致相近。当然了，这个算法也不能做到绝对的公平，还是按照10个人抢一个金额为100元的红包为例，如果此时第一个人抢到了15元，那么第二个人的红包金额范围就变成了（0.01，18.88），假如此时第二个人又抢了很高的金额，那对后面的人是不利的。就像上面的执行结果中一样，10个人抢100元的红包，有人抢到了16.58，还有人抢到了0.26。
　　除二倍均值法之外，还有一个比较有意思的算法——割线法，那么咱们再简单看看什么是割线法。
　　通过割线法模拟抢红包
　　顾名思义，割线法在计算的时候就将红包总金额看作是一根绳子，然后对这根绳子进行切割，每一段绳子的长度代表了每一个红包的金额大小。
　　举个例子：现在有10个人抢一个10元的红包，那么在（0，10）的范围内随机9个间隔大于等于0.01的数，假设这9个分割数是[1,1.6,2,3,4,5,6,7,8]，那么每个红包金额的大小也就是1、0.6、0.4、1、1、1、1、1、1、2。
　　咱们还是来看看具体的代码：
  1. 　import java.math.BigDecimal;
  2. 　　import java.math.RoundingMode;
  3. 　　import java.util.Random;
  4. 　　/**
  5. 　　 * 通过割线法模拟微信抢红包
  6. 　　 * @description: RedEnvelope
  7. 　　 * @author: 庄霸.liziye
  8. 　　 * @create: 2022-02-15 14:43
  9. 　　 **/
  10. 　　public class RedEnvelope {
  11. 　　    public static void main(String[] args) {
  12. 　　        long startTime=System.currentTimeMillis();
  13. 　　        //初始化测试场景，模拟四种情况：
  14. 　　        //10人抢0.1元红包
  15. 　　        //10人抢1元红包
  16. 　　        //10人抢10元红包
  17. 　　        //10人抢100元红包
  18. 　　        BigDecimal[][] scene = {
  19. 　　                {new BigDecimal("0.1"), new BigDecimal("10")},
  20. 　　                {new BigDecimal("1"), new BigDecimal("10")},
  21. 　　                {new BigDecimal("10"), new BigDecimal("10")},
  22. 　　                {new BigDecimal("100"), new BigDecimal("10")}
  23. 　　        };
  24. 　　        //设置每个红包的最低金额为0.01元
  25. 　　        BigDecimal min = new BigDecimal("0.01");
  26. 　　        //分别测试各个红包
  27. 　　        for (BigDecimal[] decimals : scene) {
  28. 　　            final BigDecimal amount = decimals[0];
  29. 　　            final BigDecimal num = decimals[1];
  30. 　　            System.out.println("=====" + num + "个人抢一个"+ amount + "元的红包" + "=====");
  31. 　　            GrabRedEnvelope(amount, min, num);
  32. 　　        }
  33. 　　        long endTime=System.currentTimeMillis();
  34. 　　        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
  35. 　　    }
  36. 　　    //模拟抢红包过程
  37. 　　    private static void GrabRedEnvelope(BigDecimal amount,BigDecimal min ,BigDecimal num){
  38. 　　        final Random random = new Random();
  39. 　　        final int[] rand = new int[num.intValue()];
  40. 　　        BigDecimal sum1 = BigDecimal.ZERO;
  41. 　　        BigDecimal redpeck ;
  42. 　　        int sum = 0;
  43. 　　        for (int i = 0; i < num.intValue(); i++) {
  44. 　　            rand[i] = random.nextInt(100);
  45. 　　            sum += rand[i];
  46. 　　        }
  47. 　　        final BigDecimal bigDecimal = new BigDecimal(sum);
  48. 　　        BigDecimal remain = amount.subtract(min.multiply(num));
  49. 　　        for (int i = 0; i < rand.length; i++) {
  50. 　　            if(i == num.intValue() -1){
  51. 　　                redpeck = remain;
  52. 　　            }else{
  53. 　　                redpeck = remain.multiply(new BigDecimal(rand[i])).divide(bigDecimal,2,RoundingMode.FLOOR);
  54. 　　            }
  55. 　　            if(remain.compareTo(redpeck) > 0){
  56. 　　                remain = remain.subtract(redpeck);
  57. 　　            }else{
  58. 　　                remain = BigDecimal.ZERO;
  59. 　　            }
  60. 　　            sum1= sum1.add(min.add(redpeck));
  61. 　　            System.out.println("第"+(i+1)+"个人抢到红包金额为："+min.add(redpeck));
  62. 　　        }
  63. 　　        System.out.println("所有红包累计金额是否等于红包总金额：" + compare(amount, sum1));
  64. 　　    }
  65. 　　    private static boolean compare(BigDecimal a, BigDecimal b){
  66. 　　        if(a.compareTo(b) == 0){
  67. 　　            return true;
  68. 　　        }
  69. 　　        return false;
  70. 　　    }
  71. 　　}
复制代码
接下来再看看割线法的执行结果：
  1. 　=====10个人抢一个0.1元的红包=====
  2. 　　第1个人抢到红包金额为：0.01
  3. 　　第2个人抢到红包金额为：0.01
  4. 　　第3个人抢到红包金额为：0.01
  5. 　　第4个人抢到红包金额为：0.01
  6. 　　第5个人抢到红包金额为：0.01
  7. 　　第6个人抢到红包金额为：0.01
  8. 　　第7个人抢到红包金额为：0.01
  9. 　　第8个人抢到红包金额为：0.01
  10. 　　第9个人抢到红包金额为：0.01
  11. 　　第10个人抢到红包金额为：0.01
  12. 　　所有红包累计金额是否等于红包总金额：true
  13. 　　=====10个人抢一个1元的红包=====
  14. 　　第1个人抢到红包金额为：0.07
  15. 　　第2个人抢到红包金额为：0.12
  16. 　　第3个人抢到红包金额为：0.01
  17. 　　第4个人抢到红包金额为：0.10
  18. 　　第5个人抢到红包金额为：0.10
  19. 　　第6个人抢到红包金额为：0.08
  20. 　　第7个人抢到红包金额为：0.06
  21. 　　第8个人抢到红包金额为：0.06
  22. 　　第9个人抢到红包金额为：0.04
  23. 　　第10个人抢到红包金额为：0.36
  24. 　　所有红包累计金额是否等于红包总金额：true
  25. 　　=====10个人抢一个10元的红包=====
  26. 　　第1个人抢到红包金额为：1.19
  27. 　　第2个人抢到红包金额为：1.01
  28. 　　第3个人抢到红包金额为：0.60
  29. 　　第4个人抢到红包金额为：0.69
  30. 　　第5个人抢到红包金额为：0.66
  31. 　　第6个人抢到红包金额为：0.44
  32. 　　第7个人抢到红包金额为：0.39
  33. 　　第8个人抢到红包金额为：0.62
  34. 　　第9个人抢到红包金额为：0.41
  35. 　　第10个人抢到红包金额为：3.99
  36. 　　所有红包累计金额是否等于红包总金额：true
  37. 　　=====10个人抢一个100元的红包=====
  38. 　　第1个人抢到红包金额为：17.51
  39. 　　第2个人抢到红包金额为：14.62
  40. 　　第3个人抢到红包金额为：2.47
  41. 　　第4个人抢到红包金额为：4.19
  42. 　　第5个人抢到红包金额为：8.63
  43. 　　第6个人抢到红包金额为：0.01
  44. 　　第7个人抢到红包金额为：0.23
  45. 　　第8个人抢到红包金额为：6.15
  46. 　　第9个人抢到红包金额为：3.66
  47. 　　第10个人抢到红包金额为：42.53
  48. 　　所有红包累计金额是否等于红包总金额：true
  49. 　　程序运行时间： 11ms
复制代码
通过执行结果我们可以看出来割线法的随机性比较大，并不能保证每个红包的金额大致相近（10个人抢一个100元的红包，还有人会抢到0.01，这不得给人家气坏了??）；而且割线法的性能也不是很好，虽然上面的代码体现出二倍均值法和割线法的执行时间相差不大，但是当生产环境中有大量的红包需要计算时，这差距肯定是巨大的。所以我们要实现抢红包的功能时一定要仔细斟酌，选择一个既能保证金额的相近又能保证高效的算法哦~







欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/) Powered by Discuz! X3.2