研究微信红包分配算法之Golang版
追忆似水年华 · 694浏览 · 发布于2020-02-17
红包核心算法
分配:红包里的金额怎么算?为什么出现各个红包金额相差很大? 答:随机,额度在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.gofunc 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,没有存储写盘,纯粹是为了验证算法,所以性能是很高的。
完成!
相关推荐
PHP实现部分字符隐藏
沙雕mars · 1325浏览 · 2019-04-28 09:47:56
Java中ArrayList和LinkedList区别
kenrry1992 · 908浏览 · 2019-05-08 21:14:54
5月语言排行榜:R 跌出前二十,Python 紧咬 C++
manongba · 687浏览 · 2019-05-09 17:27:24
Tomcat 下载及安装配置
manongba · 970浏览 · 2019-05-13 21:03:56
什么是SpringBoot
iamitnan · 1086浏览 · 2019-05-14 22:20:36
分类专栏
最新发布
最热排行
0评论