专栏首页架构进阶算法思考:红包金额生成

算法思考:红包金额生成

一 背景

最近在整理过去的项目时,回顾了某年红包活动,其中涉及红包金额计算的算法。近些年各家大厂举办的春节红包活动越来越完善,关于活动背后的整体设计介绍、分析、探讨层出不穷。本篇先不关注整体架构,选择红包金额的计算方法作为分析内容。

在当时的项目中,红包金额计算主要是采用了基于一些入参的随机数生成,并且生成的是单个红包金额,并未使用队列方式做预生成。所以再次回顾这个案例,其中其实还有很多可以玩味和深入思考的地方,在这里做一次思考总结。

二 题目描述

要求设计在微信群抢红包的算法,红包总金额为 m 元,分成 n 份,要求返回一个红包金额数组。算法需要满足下面的几条要求:

(1)前 n 个抢红包的人都能抢到钱,第 n 个之后的人直接返回空包,所以这里不做考虑;

(2)每个人能抢到的红包金额是随机的,但随机范围最大化(有机会获得可能的最多金额) ;

(3)抢到红包的每个人,抢到相同金额的概率是一样的。

三 传说中微信红包算法

网上其实可以搜到很多关于红包金额计算方法的解析,例如 微信红包的随机算法是怎样实现的?,给出了一个传说是微信内部人提供的代码:

public static double getRandomMoney(RedPackage _redPackage){
        //remainSize 剩余的红包数量
        //remainMoney 剩余的钱
        if(_redPackage.remainSize == 1){
            _redPackage.remainSize--;
            return (double) Math.round(_redPackage.remainMoney * 100)/100;
        }
        Random r = new Random();
        double min = 0.01;
        double max = _redPackage.remainMoney / _redPackage.remainSize * 2;
        double money = r.nextDouble() * max;
        money = money <= min ? 0.01 : mondy;
        money = Math.floor(money * 100) / 100;
        _redPackage.remainSize--;
        _redPackage.remainMoney -= money;
        return money;
    }

当然,double 类型显然是不靠谱的,楼主也做了补充,商业计算需要使用 java.math.BigDecimal;并且在回答中提供了测试结果,包括金额分布情况。

四 一个朴素且简单的思考实现

4.1 分析

如果我们自己从头思考,那么会考虑怎样来实现呢?一个简单的方法,n 个人,生成 n 次金额数据,当然,我们也要保证 n 次的金额综合=m 元,且每次每人领取到的金额最小值是 0.01 元,也就是一分钱;最大值是当前的剩余金额-剩余人数。例如总金额 1 元,5 个人可抢,那么第一个人可以抽到的最大金额是 0.96 元,之后每个人领取一元,这是最极端的情况。

其次,上面的这种算法是否能够保证绝对随机?如果不能,那么我们是否有修正策略来做个补救?争取让每个人可能获得的金额尽可能的达到随机效果?

当然,如果能从算法上直接解决是最好的。但如果短时间想不到能够最为符合要求的算法,那么就只能考虑这种补救方法,虽然效率上要差一些,但可以符合要求。既然生成的金额数组可能不是绝对平均,那么我们再生成一次随机数组,调整初始金额数组中各元素的顺序,做个随机乱序,那么就可以接近题目要求的效果。

4.2 一个代码实现(未优化)

public int[] createRandomArr(int m, int n) throws Exception{
        int[] ret = new int[n];

        int total = m*100;
        Random random = new Random();
        int cur = 1;
        int curSum = 0;
        while(cur <= n-1){
            int curLeft = total-curSum-(n-cur);
            int curAcount = random.nextInt(curLeft);
            curAcount = 1+curAcount;
            ret[cur-1] = curAcount;
            curSum+=curAcount;
            cur++;
        }
        ret[n-1] = total-curSum;

        int[] newRet = new int[n];
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for(int i=0;i<n;i++){
            int index = random.nextInt(n);
            while(map.containsKey(index)){
                index = random.nextInt(n);
            }
            newRet[i] = ret[index];
            map.put(index, true);
        }
        return newRet;
    }

五 再次思考

当然,上面的算法非常粗糙,不过也勉强能达到题目的大部分要求。影响效率严重的地方就是在生成随机索引数组,也就是第 22 行。上面的示例代码是通过 while 循环来实现的。这里可以考虑通过分段优化的方式来避免 while 循环。事实上,如果 java 中有类似 php 中 shuffle(洗牌,做数组随机乱序)的方法,那么就可以直接使用来做第二步的乱序逻辑了。更多的优化,留给大家来思考了。

随机生成红包金额,初见看起来似乎并不难,但怎样保证真正的随机且平均,并不是一个容易解决的问题。无论那种语言,我们能够调用的函数大多数都是伪随机算法,所以并不能保证这点。因此为了达到正态分布等等符合更高要求的效果,就需要对算法做好设计并进行充分的验证,确保多次实验的结果能够达到预期,这期间也需要多次验证和调优的过程。

本文分享自微信公众号 - 程序员架构进阶(flaming28sky),作者:程序员架构进阶

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何生成微信红包金额?

    一些前提解释 我要讨论的红包是:微信拼手气红包。 拼手机红包的一些的限制条件如下: – 每个红包最小为0.01元,所以每个红包至少要分到0.01元。 输入数...

    wangxl
  • 社交软件红包技术解密(十一):最全解密微信红包随机算法(含代码实现)

    这个系列文章已经整理了10篇,但都没有涉及到具体的红包算法实现,主要有以下两方面原因。

    JackJiang
  • 最全解密微信红包随机算法(含代码实现)

    这个系列文章已经整理了10篇,但都没有涉及到具体的红包算法实现,主要有以下两方面原因。

    JackJiang
  • 一不小心错过的几个亿还可以再回来!解密微信红包算法

    还记得2017年,微信红包收发总量达到460亿个,2019年,除夕到初五,8.23亿人收发微信红包。一觉醒来,微信群里各种红包,顿时觉得错过了几个亿,破解了红包...

    三哥
  • 2016腾讯校园招聘模拟考试(2016.03.25)

    在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同, 则称这种编码为格雷码(Gray Code),请编写一个函数,使用递归的方法生成N位的格雷码。 ...

    Dabelv
  • 数据分析:微信红包金额分配的秘密

    本文首发于 思考者iThink (微信ID:iThink_1),大数据 经授权转载。如需转载,请与首发公众号联系授权事宜。

    华章科技
  • 数据分析:微信红包金额分配的秘密

    “微信红包”是腾讯公司开发的社交软件——微信的一个附加功能。它可以在一对一聊天当中发送,也可以在群聊中发送。在群聊当中,可以一次性发送多于1个的红包,每个群成员...

    华章科技
  • 红包随机算法&微信群红包随机算法

    因疫情影响,部门 2021 年会以线上直播的形式进行,通过微信小程序展开。为活跃年会氛围,年会直播间会有抢红包环节。因产品要求,红包金额要随机生成,所以这里涉及...

    Dabelv
  • 除夕抢红包你准备好了吗?大数据教你怎么抢红包手气最好

    <数据猿导读> 还记得元旦抢红包的空前盛况吗?微信表示也hold不住啦,然而元旦过去了,春节还会远吗,今天小编特意准备了一份抢红包秘籍,让你在除夕晚成为手气第一...

    数据猿

扫码关注云+社区

领取腾讯云代金券