微信红包随机分配算法加最佳优化方案

作者: LeeHeng 分类: 技术拓展 发布时间: 2017-04-20 18:19

最近公司搞了个小编程比赛,就是红包分配算法,不仅带来点乐趣,还能提高一下技术水平,把平时枯燥乏味的上班气氛打破。

算法要求

1.每个红包需要精确到小数点后2位,即精确到“分”

2.红包分配机制如下:

随机分配,额度在0.01元~(剩余平均值*2)之间。

例如:发100块钱,总共10个红包,那么平均值是10块钱一个,那么发出来的红包的额度在0.01元~20元之间波动。

当前面3个红包总共被领了40块钱时,剩下60块钱,总共7个红包,那么这7个红包的额度在:0.01~(60/7*2)=17.14之间。

注意:这里的算法是每被抢一个后,剩下的会再次执行上面的这样的算法。

倒数第2个红包时,取值范围是0.01元~(剩余金额-0.01元),最后一个红包则把剩余金额全部取走。

3.循环200000次每次分配红包100元30个,将结果输出到文本里

4.文本格式如下:

开始时间:XXX(精确到毫秒)

10.1,2.02,3.33…(30个记录)

10.1,2.02,3.33…(30个记录)

10.1,2.02,3.33…(30个记录)

…(总共1W条记录)

结束时间:XXX(精确到毫秒)

5.编程语言不限

开始之后大家都踊跃参加,各自写各自的代码,噼噼啪啪,很快就实现了,但是呢,其实这个实现过程和算法并没有太大区别,最主要的还是在于优化策略。我个人也在网上找了很多关于php版本的算法,还找到了一个php扩展,zqf 作者只是简单实现了一下随机分配,还是有一点不能满足,因为小数点没有精确到分,在没有精确到分的情况下,执行是可以达到1000ms左右,也就是1秒或者1秒内

下面分享一下个人使用zqf扩展的版本

最后执行脚本总耗时:

对于PHP的性能来说,算快的了,之前还去了解过协程,不过那是异步,算是作弊,为什么这么说呢?因为整体流程是需要写文件,根据文件最后更新时间来算,就算能把脚本执行时间蒙过去,最后能写文件的时间蒙不过去。也想过php多线程,用swoole等完成,只是没时间再去研究了,将就着玩玩吧,参加一下就好

另外还有c++版本、java版本,下面是一个做安卓客户端的童鞋的版本,连优化方案都记录下来,下面看下他的整个笔记

优化方案

  1. 算法优化,减少循环里面的判断(影响第三)
  2. 线程优化(两种优化方案) (影响第四)
  3. 字符串组装优化(逻辑换时间,最重要的环节)(影响最大)
  4. io 优化 (影响第二)

一、算法优化

原始方案(没做优化):

优化后:

优点:

  • 大大减少循环里面 if 的判断
  • 把能提出到方法外的变量都提出方法外,避免每次循环都变量都创建一次

二、线程优化(两种方案)

1. 线程方案1:锁比较少,但不能保证每个线程同一时间内获得 cpu 分配的时间片一样

线程1方案的优缺点:
优点:线程阻塞的几率低(只有2个或以上线程同时运行完成,同时访问 successtime 的时候才会遇到线程阻塞)
缺点:不稳定,原因是:不能保证每个线程获得 cpu 分配的时间片一样,所以造成每个线程运行的时间不一样,那么假如线程1,2,3在1秒内运行完了(循环玩5w 次),而线程4可能只运行了3w 次,还有2w 次需要运行。所以最终程序运行所花费的时间是最后线程运行完所需要的时间。

2.线程方案2:判断锁的次数比较多

线程2方案的优缺点:
优点:稳定,不需要理会 cpu 的时间片分配,线程数达到了 cpu 瓶颈数,那么开再多的线程也会很稳定,的只要每个线程运行完1次分配红包的工作都会对 count 进行+1的操作,只要 count 达到1w 就会完成工作。
缺点:对锁访问比较频繁,多个线程同时访问到 count 以致造成阻塞的几率比较大。

对比图

三、字符串优化(算法+拼接 逻辑代替时间)

  1. 首先对于拼接来说,不要直接对字符串拼接(str += “0.02,”;),因为这样会制造出很多 String 对象,例如产生1个红包的过程:
    第一次:0.02
    第二次:0.02,0.10,
    第三次:0.02,0.10,1.01。
    这样其实静态内存区(专门放字符串的内存区),会产生上面3中字符串,600w 次就会差生600w 个以上字符串,这样会造成内存非常大,造成不停GC(垃圾回收)。(用 stringBuilder 代替,这个是专门拿来做字符串拼接的类,可以避免产生600w 个字符串的问题)
  2. 不要用系统的格式化处理(%.02f)。因为这种格式化系统都会做查找替换的工作,所以600w 次的查找替换也是非常耗时的。
  3. 字符串处理算法

    以上代码 意思就是新建一个[][][.][][][/n或,]的数组,然后每生成一个红包,就会往这个数组上填位,然后往Stringbuilder 后面追加数组。这样循环60w 次最后 builder 就是最后的结果


四、io优化

  1. 利用有缓存区的 io 流来写。(缓存区就是先把程序写到内存中,然后结束的时候一次过把内存区的内容写到文件(调用 io.flush()/io.close()))。
  2. 自定义缓存区大小。因为文件的读写很耗时,所以要减少读写操作。设置35M 的缓存区,这样写一次就可以把所有内容写到文件,减少了很多的读写操作。当然开辟35M 的内存也是要一定时间,但远远少于读写操作。

     

最后总结一下,这位童鞋的逻辑性很强,各个方面考虑得比较周全,整个流程的每一步都梳理清晰

附上源代码:

百度云盘:https://pan.baidu.com/s/1eSeN62A 密码:rikb

C语言部分:https://pan.baidu.com/s/1hrNO0vi 密码:ytjd

发表评论

电子邮件地址不会被公开。 必填项已用*标注