go实现一个红包分配算法与标准包中的随机数

翻代码翻出三四年前写的一个红包分配算法,拿出来批评一番

这个的场景是企业通过微信支付发放红包,最小支付额为0.3元。代码中单位是分
应该是根据网上传言微信红包是根据2倍均值分配算法实现的
rand.Seed(全局)的注释:

1
2
3
4
5
6
// Seed uses the provided seed value to initialize the default Source to a
// deterministic state. If Seed is not called, the generator behaves as
// if seeded by Seed(1). Seed values that have the same remainder when
// divided by 2³¹-1 generate the same pseudo-random sequence.
// Seed, unlike the Rand.Seed method, is safe for concurrent use.
func Seed(seed int64) { globalRand.Seed(seed) }

Rand.Seed的注释:

1
2
3
// Seed uses the provided seed value to initialize the generator to a deterministic state.
// Seed should not be called concurrently with any other Rand method.
func (r *Rand) Seed(seed int64) {...}

标准包中的rand,必须要设置不同的随机数种子,不然每次都会输出既定顺序的数值
math/rand 包中默认的随机数相关函数是并发安全的,实际是共享了globalRand,也会使用一个全局锁,所以性能会随着竞争强度增加而降低
原代码中Seed的用法是不对的,不应该每次调用(且存在并发调用)时尝试设置种子
如果全局锁并不对性能造成可感知的影响,那么包初始化时调用一次Seed完成种子设置就行了
如果全局锁的性能损耗不可接受,应该给generator结构体中增加一个锁(Rand.Seed非并发安全),再加一个*rand.Rand,即不用globalRand而是自定义来细化锁粒度,避免全局锁竞争。同样init时调用一次Seed
当然,如果对随机数生成的性能有更高的要求,可以考虑其它的算法,如XorShift

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package model

import (
"math/rand"
"time"
)

// +这命名不符合规范
const MINAMOUNT = 30

// Generate ...
// +还单独暴露方法
func Generate(totalAmount, number, minAmount int) (result []int, ok bool) {
data := generator{
totalAmount: totalAmount,
minAmount: minAmount,
number: number,
}
return data.Result()
}

type generator struct {
// 红包总金额
totalAmount int
// 红包数量
number int
// 最小红包金额
minAmount int
// 红包生成结果
result []int
}

func (g *generator) paramsCheck() bool {
if g.totalAmount <= 0 || g.minAmount <= 0 || g.number <= 0 {
return false
}

if g.totalAmount < g.number*g.minAmount {
return false
}

return true
}

// Result 执行生成逻辑,并返回结果
func (g *generator) Result() (result []int, ok bool) {
if !g.paramsCheck() {
return
}

g.init()

g.generate()

return g.result, g.resultCheck()
}

func (g *generator) init() {
g.result = make([]int, g.number, g.number)

// 每个红包先填充最小值
for index := range g.result {
g.result[index] = g.minAmount
}

// +每次都设置
rand.Seed(time.Now().UnixNano())
}

// generate 执行生成逻辑
func (g *generator) generate() {
// 红包余额
remainAmount := g.totalAmount - g.number*g.minAmount
// 剩余数量
remainNumber := g.number
// 2倍剩余均值金额
var averageMax int
// 单个红包金额
var amount int

for index := range g.result {
if remainNumber == 0 || remainAmount == 0 {
break
}

// 剩余红包的2倍平均值
averageMax = 2 * remainAmount / remainNumber

// 最后一个得到全部剩余
if remainNumber == 1 {
amount = remainAmount
} else {
amount = g.random(averageMax)
}

g.result[index] += amount
remainAmount -= amount
remainNumber--
}
}

func (g *generator) random(max int) int {
if 0 == max {
return 0
}

return rand.Intn(max)
}

func (g *generator) resultCheck() bool {
totalAmount := 0
for index := 0; index < g.number; index++ {
totalAmount += g.result[index]
}

return totalAmount == g.totalAmount
}

参考链接

XorShift
RNG
原文链接