1. 前言

• 最近在做一個搶紅包的項目，關于紅包怎么分配，才能達到一個最佳效果，我做了一些調研以及對應的實現方案。
• 關于每個紅包金額的范圍采用二倍均值算法[0 .01 - M/N * 2]，其中M表示總金額，N表示紅包個數。比如：總金額100元分為10個紅包，均值：100/10=10元，每個紅包金額的范圍就是 [0.01 - 20]，即1分到20元之間，但范圍內的隨機值該如何產生，接下來進行分析

2.生成隨機數算法

• 線性同余算法：生成一個均勻分布的偽隨機數，例如：java.util.Random.next()方法，有規則的隨機，使用的是48-bit的種子，然后調用一個linear congruential formula線性同余方程，特點：在給定種(seed)的區間內隨機生成數字。相同種子數的Random對象，相同次數生成的隨機數字是完全相同的。
• 正態（高斯）分布：若隨機變量X服從一個數學期望為 $\mu$ 、方差為 ${\sigma }^2$ 的高斯分布，記為N(μ， ${\sigma }^2$ )。其中期望值（均數） $\mu$ 決定了位置，其標準差 $\sigma$ 決定了分布的幅度（ $\sigma$ 越小曲線越尖峭）。N(0, 1)表示標準正態分布。可以利用正態分布近似估算二項分布和泊松分布。正態分布函數密度曲線公式如下：
  $$f(x)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{?\frac{1}{2}{\left(\frac{x?\mu }{\sigma }\right)}^2}$$
  • 正態分布與其它分布的區別：正態分布是連續分布，泊松分布，二項分布都是離散分布； 二項分布的極限分布是泊松分布、泊松分布的極限分布是正態分布。正態分布符合中心極限定理：在特定條件下，大量統計獨立的隨機變量的平均值的分布趨于正態分布。
  • 正態分布的特點：符合68-95-99.7法則，即68.3%的面積在平均數左右的一個標準差 $\sigma$ 范圍內；95.4%兩個 $\sigma$ 范圍內，99.7%三個 $\sigma$ 范圍內；99.9%四個 $\sigma$ 范圍內。
  • 使用正態分布的缺點：無法近似估算符合幾何分布的問題，無法精確解決離散數據概率。
• Box–Muller（博克斯·馬勒）變換：本質用了逆變換法，以兩組獨立的隨機數U和V，這兩組數在(0,1]上均勻分布，用U和V生成兩組獨立的標準正態分布隨機變量X和Y ,公式如下：
  $$X=\sqrt{?2\ln U}\cos (2\pi V),Y=\sqrt{?2\ln U}\sin (2\pi V)$$
• ziggurat算法：比Box–Muller更快，利用拒絕采樣實現。
• 極坐標法：Box–Muller的一種形式，避免了$\sin ,\cos$ 的計算。

3.生成隨機數的代碼實現

3.1 均值分布

3.1.1 Random.next()方法源碼

• java.util.Random.next()方法源碼

/*** Generates the next pseudorandom number. Subclasses should* override this, as this is used by all other methods.** <p>The general contract of {@code next} is that it returns an* {@code int} value and if the argument {@code bits} is between* {@code 1} and {@code 32} (inclusive), then that many low-order* bits of the returned value will be (approximately) independently* chosen bit values, each of which is (approximately) equally* likely to be {@code 0} or {@code 1}. The method {@code next} is* implemented by class {@code Random} by atomically updating the seed to* <pre>{@code (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)}</pre>* and returning* <pre>{@code (int)(seed >>> (48 - bits))}.</pre>** This is a linear congruential pseudorandom number generator, as* defined by D. H. Lehmer and described by Donald E. Knuth in* <i>The Art of Computer Programming,</i> Volume 3:* <i>Seminumerical Algorithms</i>, section 3.2.1.** @param bits random bits* @return the next pseudorandom value from this random number* generator's sequence* @since 1.1*/protected int next(int bits) {long oldseed, nextseed;AtomicLong seed = this.seed;do {oldseed = seed.get();nextseed = (oldseed * multiplier + addend) & mask;} while (!seed.compareAndSet(oldseed, nextseed));return (int)(nextseed >>> (48 - bits));}

3.1.2 具體代碼實現

import java.util.ArrayList; import java.util.List; import java.util.Random;public class RedEnvelopeUtil {private static Random random;static {random = new Random();}/*** 返回min~max區間內隨機數，含min和max** @param min 最小值* @param max 最大值* @return 隨機值*/private static int getRandomVal(int min, int max) {return random.nextInt(max - min + 1) + min;}/*** 隨機分配第n個紅包** @param totalAmount 總紅包量* @param totalNum 總份數* @param sentAmount 已發送紅包量* @param sentNum 已發送份數* @param rdMin 隨機下限* @param rdMax 隨機上限* @return Integer*/private static Integer randomOneRedEnvelope(Integer totalAmount, Integer totalNum, Integer sentAmount,Integer sentNum, Integer rdMin, Integer rdMax) {int remainNum = totalNum - sentNum - 1;int remainAmount = totalAmount - sentAmount;Integer boundMin = Math.max(remainAmount - remainNum * rdMax, rdMin);Integer boundMax = Math.min(remainAmount - remainNum * rdMin, rdMax);return getRandomVal(boundMin, boundMax);}/*** 生成紅包一次分配結果** @param totalAmount 總紅包金額* @param totalNum 總紅包個數* @return 小紅包列表*/public static List<Integer> divideRedEnvelope(Integer totalAmount, Integer totalNum) {Integer sentAmount = 0;Integer sentNum = 0;int min = (totalAmount / totalNum) / 10;Integer rdMin = min == 0 ? 1 : min;Integer rdMax = (totalAmount / totalNum * 2);List<Integer> redEnvelope = new ArrayList<>();while (sentNum < totalNum) {Integer bonus = randomOneRedEnvelope(totalAmount, totalNum, sentAmount, sentNum, rdMin, rdMax);redEnvelope.add(bonus);sentNum++;sentAmount += bonus;}return redEnvelope;} }

3.1.3 小結

• 生成的紅包在.0.01-20 元之間均勻分布
• 生成紅包效率：我在本地測試了一下，生成10000個紅包大概需要 5 ms，還是挺快的
• 生成紅包（1-20元）散點圖
  

3.2 正態分布

3.1.1 Random.nextGaussian()方法源碼

/*** Returns the next pseudorandom, Gaussian ("normally") distributed* {@code double} value with mean {@code 0.0} and standard* deviation {@code 1.0} from this random number generator's sequence.* <p>* The general contract of {@code nextGaussian} is that one* {@code double} value, chosen from (approximately) the usual* normal distribution with mean {@code 0.0} and standard deviation* {@code 1.0}, is pseudorandomly generated and returned.** <p>The method {@code nextGaussian} is implemented by class* {@code Random} as if by a threadsafe version of the following:* <pre> {@code* private double nextNextGaussian;* private boolean haveNextNextGaussian = false;** public double nextGaussian() {* if (haveNextNextGaussian) {* haveNextNextGaussian = false;* return nextNextGaussian;* } else {* double v1, v2, s;* do {* v1 = 2 * nextDouble() - 1; // between -1.0 and 1.0* v2 = 2 * nextDouble() - 1; // between -1.0 and 1.0* s = v1 * v1 + v2 * v2;* } while (s >= 1 || s == 0);* double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);* nextNextGaussian = v2 * multiplier;* haveNextNextGaussian = true;* return v1 * multiplier;* }* }}</pre>* This uses the <i>polar method</i> of G. E. P. Box, M. E. Muller, and* G. Marsaglia, as described by Donald E. Knuth in <i>The Art of* Computer Programming</i>, Volume 3: <i>Seminumerical Algorithms</i>,* section 3.4.1, subsection C, algorithm P. Note that it generates two* independent values at the cost of only one call to {@code StrictMath.log}* and one call to {@code StrictMath.sqrt}.** @return the next pseudorandom, Gaussian ("normally") distributed* {@code double} value with mean {@code 0.0} and* standard deviation {@code 1.0} from this random number* generator's sequence*/synchronized public double nextGaussian() {// See Knuth, ACP, Section 3.4.1 Algorithm C.if (haveNextNextGaussian) {haveNextNextGaussian = false;return nextNextGaussian;} else {double v1, v2, s;do {v1 = 2 * nextDouble() - 1; // between -1 and 1v2 = 2 * nextDouble() - 1; // between -1 and 1s = v1 * v1 + v2 * v2;} while (s >= 1 || s == 0);double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);nextNextGaussian = v2 * multiplier;haveNextNextGaussian = true;return v1 * multiplier;}}

• 分析：
  • java8線程安全的Random.nextGaussian()使用了極坐標法（Box–Muller的一種形式），
  • 該方法來源：單位圓 -> 均勻分布 -> 指數分布 -> 自由度為2的卡方分布 -> 反推出2個隨機變量的表達式
  • 具體理論（nextGaussian方法源碼剖析）
    ①隨機變量 U,V 服從(-1,1) 的均勻分布
    ②計算 $S=U^2+V^2$
    ③如果 $S\ge 1$, 接著計算, 否則轉④
    ④$X=U\sqrt{\frac{?2\ln S}{S}},Y=V\sqrt{\frac{?2\ln S}{S}}$, X,Y 獨立,并且都符合高斯正態分布

3.2.2 具體代碼實現

import java.util.ArrayList; import java.util.List; import java.util.Random;public class RedEnvelopeUtil {private static Random random;static {random = new Random();}/*** 獲取一個符合高斯分布的隨機值** @param min 范圍最小值* @param max 范圍最大值* @return 隨機值*/private static int getGaussianRandomVal(int min, int max) {// 均值 = 紅包總金額 / 紅包個數 * 2int μ = max / 2;// 期望 = 68%的紅包金額落在均值80%范圍內int σ = μ / 10 * 4;long randomVal = Math.round(getGaussianValue(μ, σ));// 高斯分布函數有百萬分之一的情況不在期望內，對隨機值進行一個范圍內的兜底。return (int) Math.max(min, Math.min(randomVal, max));}/*** 獲取一個符合高斯（正態）分布的隨機值* 例如：參數: (10, 4)，返回的隨機值大部分在6-14之間，符合68-95-99.7法則** @param μ 期望值（均值）* @param σ 標準差* @return 隨機數*/private static double getGaussianValue(int μ, int σ) {return Math.sqrt(σ) * random.nextGaussian() + μ;}/*** 隨機分配第n個紅包** @param totalAmount 總紅包量* @param totalNum 總份數* @param sentAmount 已發送紅包量* @param sentNum 已發送份數* @param rdMin 隨機下限* @param rdMax 隨機上限* @return Integer*/private static Integer randomOneRedEnvelope(Integer totalAmount, Integer totalNum, Integer sentAmount,Integer sentNum, Integer rdMin, Integer rdMax) {int remainNum = totalNum - sentNum - 1;int remainAmount = totalAmount - sentAmount;Integer boundMin = Math.max(remainAmount - remainNum * rdMax, rdMin);Integer boundMax = Math.min(remainAmount - remainNum * rdMin, rdMax);return getGaussianRandomVal(boundMin, boundMax);}/*** 生成紅包一次分配結果** @param totalAmount 總紅包金額* @param totalNum 總紅包個數* @return 小紅包列表*/public static List<Integer> divideRedEnvelope(Integer totalAmount, Integer totalNum) {Integer sentAmount = 0;Integer sentNum = 0;int min = (totalAmount / totalNum) / 10;Integer rdMin = min == 0 ? 1 : min;Integer rdMax = (totalAmount / totalNum * 2);List<Integer> redEnvelope = new ArrayList<>();while (sentNum < totalNum) {Integer bonus = randomOneRedEnvelope(totalAmount, totalNum, sentAmount, sentNum, rdMin, rdMax);redEnvelope.add(bonus);sentNum++;sentAmount += bonus;}return redEnvelope;}

3.2.3 小結

• 生成的紅包在.0.01-20 元之間符合高斯分布
• 生成紅包效率：我在本地測試了一下，生成10000個紅包大概需要 10 ms
• 生成紅包（1-20元）散點圖
  

3.3 兩種紅包分配算法的對比

• 生成紅包（1-20元）優化前后的散點對比圖
  

參考：

微信紅包隨機算法(含代碼實現)

漫談正態分布的生成

Java中的random函數是如何實現的

總結

以上是生活随笔為你收集整理的红包分配算法的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。