研究微信红包分配算法之Golang版

今天来看一下红包的分配，参考几年前流传的微信红包分配算法，今天用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，没有存储写盘，纯粹是为了验证算法，所以性能是很高的。

完成！

巴特西

研究微信红包分配算法之Golang版

红包核心算法

核心红包随机分配算法

最新文章

热门文章