notebook notebook
首页
  • 计算机网络
  • 计算机系统
  • 数据结构与算法
  • 计算机专业课
  • 设计模式
  • 前端 (opens new window)
  • Java 开发
  • Python 开发
  • Golang 开发
  • Git
  • 软件设计与架构
  • 大数据与分布式系统
  • 常见开发工具

    • Nginx
  • 爬虫
  • Python 数据分析
  • 数据仓库
  • 中间件

    • MySQL
    • Redis
    • Elasticsearch
    • Kafka
  • 深度学习
  • 机器学习
  • 知识图谱
  • 图神经网络
  • 应用安全
  • 渗透测试
  • Linux
  • 云原生
面试
  • 收藏
  • paper 好句
GitHub (opens new window)

学习笔记

啦啦啦,向太阳~
首页
  • 计算机网络
  • 计算机系统
  • 数据结构与算法
  • 计算机专业课
  • 设计模式
  • 前端 (opens new window)
  • Java 开发
  • Python 开发
  • Golang 开发
  • Git
  • 软件设计与架构
  • 大数据与分布式系统
  • 常见开发工具

    • Nginx
  • 爬虫
  • Python 数据分析
  • 数据仓库
  • 中间件

    • MySQL
    • Redis
    • Elasticsearch
    • Kafka
  • 深度学习
  • 机器学习
  • 知识图谱
  • 图神经网络
  • 应用安全
  • 渗透测试
  • Linux
  • 云原生
面试
  • 收藏
  • paper 好句
GitHub (opens new window)
  • 面试索引
  • Java 面试

    • 如何设计一个抢红包算法
      • 1. 抢红包的过程
      • 2. 红包金额的算法
        • 2.1 金额随机法(不公平)
        • 2.2 二倍均值法(公平)
    • Autowired 与 Resource 注解的区别
    • 秒杀系统设计方案
    • IO 多路复用
  • 面试
  • Java 面试
yubin
2022-12-28
目录

如何设计一个抢红包算法

参考视频:如何设计一个抢红包算法? (opens new window)

# 1. 抢红包的过程

抢红包的过程可以类比于一个下单秒杀的情况。

当我们在发放一个红包的时候,一般要经历这样一个过程,用户发红包,内容其实是一个下单流程,红包为我们的虚拟商品,生成订单后,用户进行支付,支付成功后返回“红包标识码”用于进行分享。

在生成红包的过程中,我们已经将红包内的金额计算好了,因为如果不提前计算好的话,当用户在大批量抢的时候再去计算就会降低性能。用户抢红包的过程就可以类似我们的秒杀过程。比如 100 块钱 10 个红包,其实就会生成 10 个令牌,先拿到的用户获取到令牌,并获取对应的金额,后到的用户因为没有令牌了,所以自然就是红包已领取完。

接下来讲一下在抢红包时,红包金额的两种算法:

# 2. 红包金额的算法

# 2.1 金额随机法(不公平)

这种方法其实就是纯粹依赖随机数的选取来决定红包金额的划分。

假设 100 块钱发送 10 个红包,最低可以抢到 0.01。那么生成第一个红包令牌的金额的时候,就是 0-99.91。假设第一个人红包的金额是 50,那么生成第二个红包的时候就是 0-49.91。但这样会存在一个大的问题,就是大家抢红包的时候,越往后生成的金额越小,虽然我们最后会把生成的金额进行随机排序打乱,但是生成的过程其实已经是不公平的,那么抢到的红包注定不公平。

# 2.2 二倍均值法(公平)

这种方式每个红包令牌的金额上限计算公式为:

剩余金额剩余数量

也就是说,每个红包令牌的金额下限是 0.01,上限是上面公式的计算结果。2 就是我们固定的平均数区间。

还是假设 100 元红包分给 10 个人,那么第一个红包在计算的时候,就是 100 / 10 * 2 = 20,那第一个红包的金额就在 0.01 和 20 之间随机,期望为 10 块钱;假设第一个红包计算为 8 块钱,然后第二个红包再计算的时候,就是 92 / 9 * 2 = 20,那么期望仍为 10 块钱。依次类推,这个方法可以确保我们生成金额的时候是公平的。

综上,实际生产时应该使用第二种方法。

编辑 (opens new window)
上次更新: 2022/12/28, 16:48:24
面试索引
Autowired 与 Resource 注解的区别

← 面试索引 Autowired 与 Resource 注解的区别→

最近更新
01
Deep Reinforcement Learning
10-03
02
误删数据后怎么办
04-06
03
MySQL 一主多从
03-22
更多文章>
Theme by Vdoing | Copyright © 2021-2024 yubincloud | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式
×