今天来看一下红包的分配, 参考几年前流传的微信红包分配算法, 今天用 Golang 实现一版, 并测试验证结果.
微信红包的随机算法是怎样实现的? https://www.zhihu.com/question/22625187
红包核心算法
分配: 红包里的金额怎么算? 为什么出现各个红包金额相差很大?
答: 随机, 额度在 0.01 和 (剩余平均值 * 2) 之间
每次拆红包, 额度范围在[0.01 ~ 剩余平均值 * 2] 之间, 这是很妙的一个设计.
比如发 100 元, 共发 10 个红包, 那么平均值 10 元, 第一个拆出来的红包的额度在 0.01 元~20 元之间波动, 可以确保不会一个人把红包全领了的情况, 因为最大就是剩余平均值的 2 倍.
比如发 0.1 元, 共发 10 个红包, 每个 0.01 元, 这种就不用随机算法了, 直接平均分配吧.
No bb, show your code!
设计红包结构体
- //reward.go
- // 红包
- type Reward struct {
- Count int // 个数
- Money int // 总金额(分)
- RemainCount int // 剩余个数
- RemainMoney int // 剩余金额(分)
- BestMoney int // 手气最佳金额
- BestMoneyIndex int // 手气最佳序号
- MoneyList []int // 拆分列表
- }
我这里用 int 整型做金额计算, 可以避免浮点数精度问题, 展示的时候除 100, 就是元单位了.
核心红包随机分配算法
- //reward.go
- // 抢红包
- func GrabReward(reward *Reward) int {
- if reward.RemainCount <= 0 {
- panic("RemainCount <= 0")
- }
- // 最后一个
- if reward.RemainCount - 1 == 0 {
- money := reward.RemainMoney
- reward.RemainCount = 0
- reward.RemainMoney = 0
- return money
- }`
- // 是否可以直接 0.01
- if (reward.RemainMoney / reward.RemainCount) == 1 {
- money := 1
- reward.RemainMoney -= money
- reward.RemainCount--
- return money
- }
- // 红包算法参考 https://www.zhihu.com/question/22625187
- // 最大可领金额 = 剩余金额的平均值 x2 = (剩余金额 / 剩余数量) * 2
- // 领取金额范围 = 0.01 ~ 最大可领金额
- maxMoney := int(reward.RemainMoney / reward.RemainCount) * 2
- rand.Seed(time.Now().UnixNano())
- money := rand.Intn(maxMoney)
- for money == 0 {
- // 防止零
- money = rand.Intn(maxMoney)
- }
- reward.RemainMoney -= money
- // 防止剩余金额负数
- if reward.RemainMoney <0 {
- money += reward.RemainMoney
- reward.RemainMoney = 0
- reward.RemainCount = 0
- } else {
- reward.RemainCount--
- }
- return money
- }
分配算法完成后, 验证一下, 用单元测试的办法验证
- //reward_test.go
- func TestGrabReward2(t *testing.T) {
- chanReward := make(chan Reward)
- rand.Seed(time.Now().UnixNano())
- go func(){
- // 随机生成 1000 个红包
- for i:=0; i < 1000; i++ {
- // 随机红包个数 1~50
- count := rand.Intn(50) + 1
- // 随机红包总金额 1~100 元
- money := rand.Intn(10000) + 100
- avg := money / count
- for avg == 0 {
- // 保证金额足够分配
- count = rand.Intn(50) + 1
- money = rand.Intn(10000) + 100
- avg = money / count
- }
- reward := Reward{Count: count, Money: money,
- RemainCount: count, RemainMoney: money}
- chanReward <- reward
- }
- close(chanReward)
- }()
- // 打印拆包列表, 带手气最佳
- for reward := range chanReward {
- for i := 0; reward.RemainCount> 0; i++ {
- money := GrabReward(&reward)
- if money> reward.BestMoney {
- reward.BestMoneyIndex, reward.BestMoney = i, money
- }
- reward.MoneyList = append(reward.MoneyList, money)
- }
- t.Logf("总个数:%d, 总金额:%.2f", reward.Count, float32(reward.Money)/100)
- for i := range reward.MoneyList {
- money := reward.MoneyList[i]
- isBest := ""
- if reward.BestMoneyIndex == i {
- isBest = "** 手气最佳"
- }
- t.Logf("money_%d : (%.2f)%s\n", i+1, float32(money)/100, isBest)
- }
- t.Log("-------")
- }
- }
运行结果
reward_test.go:106: 总个数: 7, 总金额: 86.59
- reward_test.go:113: money_1 : (16.29)
- reward_test.go:113: money_2 : (4.93)
reward_test.go:113: money_3 : (22.89) ** 手气最佳
- reward_test.go:113: money_4 : (3.17)
- reward_test.go:113: money_5 : (20.51)
- reward_test.go:113: money_6 : (0.12)
- reward_test.go:113: money_7 : (18.68)
- reward_test.go:115: -------
reward_test.go:106: 总个数: 10, 总金额: 53.79
- reward_test.go:113: money_1 : (3.56)
- reward_test.go:113: money_2 : (6.39)
- reward_test.go:113: money_3 : (0.36)
- reward_test.go:113: money_4 : (2.60)
- reward_test.go:113: money_5 : (10.11)
- reward_test.go:113: money_6 : (5.76)
- reward_test.go:113: money_7 : (2.84)
reward_test.go:113: money_8 : (14.04) ** 手气最佳
- reward_test.go:113: money_9 : (1.95)
- reward_test.go:113: money_10 : (6.18)
- reward_test.go:115: -------
性能测试
- // 性能测试
- func BenchmarkGrabReward(b *testing.B) {
- chanReward := make(chan *Reward, b.N)
- rand.Seed(time.Now().UnixNano())
- go func(){
- // 随机生成红包
- for i:=0; i <b.N; i++ {
- // 随机红包个数 1~50
- count := rand.Intn(50) + 1
- // 随机红包总金额 1~100 元
- money := rand.Intn(10000) + 100
- avg := money / count
- for avg == 0 {
- // 保证金额足够分配
- count = rand.Intn(50) + 1
- money = rand.Intn(10000) + 100
- avg = money / count
- }
- reward := Reward{Count: count, Money: money,
- RemainCount: count, RemainMoney: money}
- chanReward <- &reward
- }
- close(chanReward)
- }()
- // 打印拆包列表, 带手气最佳
- for reward := range chanReward {
- for i := 0; reward.RemainCount> 0; i++ {
- money := GrabReward(reward)
- if money> reward.BestMoney {
- reward.BestMoneyIndex, reward.BestMoney = i, money
- }
- reward.MoneyList = append(reward.MoneyList, money)
- }
- _ = fmt.Sprintf("总个数:%d, 总金额:%.2f", reward.Count, float32(reward.Money)/100)
- for i := range reward.MoneyList {
- money := reward.MoneyList[i]
- isBest := ""
- if reward.BestMoneyIndex == i {
- isBest = "** 手气最佳"
- }
- _ = fmt.Sprintf("money_%d : (%.2f)%s\n", i+1, float32(money)/100, isBest)
- }
- }
- }
性能测试结果
- BenchmarkGrabReward-8 4461 244842 ns/op
- //4 核 8 线的 CPU 运运行 4461 次, 平均每次 244842 纳秒 = 0.244842 毫秒
性能可以说是很优秀的, 这是因为这个测试是纯内存计算, 没有网络 IO, 没有存储写盘, 纯粹是为了验证算法, 所以性能是很高的.
完成!
来源: https://www.cnblogs.com/imbin/p/12320661.html