用java代码实现简单的概率随机抽奖算法，看完相信你也会
source link: https://zhuanlan.zhihu.com/p/102493935
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
用java代码实现简单的概率随机抽奖算法，看完相信你也会
工作需要，这两天写一个简单的java抽奖算法，因为逻辑简单不复杂，所以代码也很简洁，可以做到不同权重有不用的中奖概率（就类似于nginx集群一样，权重越大，概率越高），在这里将java概率随机抽奖代码抽离出来分享给大家。
具体需求：
给第三方推送数据，每个第三方根据预算会有不同的额度，考虑到服务器压力，所以采取了主动推送的方式，在每次推送的时候，需要根据第三方的配额计算出相应的概率，然后挑选一个第三方来推送。
思路分析：
从形式上看，跟随机抽奖几乎一模一样，都是在N中挑选1，而且还不是公平挑选，是带有概率性的。
由于只分享概率随机抽奖的算法，所以就暂不考虑上限的情况，简单的说一下算法部分的实现思路（重点在于计算概率和区间，我这里是数量固定，所以概率很好算，具体真实的抽奖业务中会很复杂）。
1、需要计算出每个第三方的配额在总配额中的占比情况：自身数量 / 总数量 = 各自占比；
2、用100来做随机区间（1也可以），计算出每个区间的随机数值跨度：比例 * 100 = 区间跨度；
3、根据跨度计算出每个区间的起始数值：从0开始按照每个跨度相加，最终将100拆分成N个区间；
代码实现：
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
/**
* Created by Felix on 2019/07/10.
*/
public class Lottery {
/**
* 计算自身相对于总体的比例
*
* @param self 自身
* @param all 总体
* @return 比例
*/
private static float getPercent(Integer self, Integer all) {
// 比例计算出来会有很多小数，为了看得清晰，要四舍五入一下
return new BigDecimal(self / all.floatValue()).setScale(2, BigDecimal.ROUND_HALF_UP).floatValue();
}
/**
* 根据比例，在100之间计算出区间跨度，进一步来计算中奖区间
*
* @param percent 比例
* @return 跨度
*/
private static int getRandom(float percent) {
// 如果getPercent中没有四舍五入，那么就需要在这里四舍五入
return new BigDecimal(percent * 100).intValue();
}
private void lottery() {
Integer allAmount = 233;// 总配额（抽奖总次数）
List<User> users = new ArrayList<>();
users.add(new User(1, "张三", 11));
users.add(new User(2, "李四", 22));
users.add(new User(3, "王五", 5));
users.add(new User(4, "赵六", 111));
users.add(new User(5, "田七", 66));
users.add(new User(6, "陈八", 18));
Map<Integer, Offset> userOffsetMap = new HashMap<>();
float percent;// 比例
int span;// 跨度
int start = 0;// 区间开始
int end;// 区间结束
for (User user : users) {
percent = getPercent(user.getAmount(), allAmount);
span = getRandom(percent);
// 按照跨度计算offset
end = start + span;
userOffsetMap.put(user.getId(), new Offset(percent, span, start, end, user.getAmount()));
// 因为区间不能超过100，所以每次都需要用新的数值+跨度
start = end;
}
// log
for (Integer userId : userOffsetMap.keySet()) {
Offset offset = userOffsetMap.get(userId);
System.out.println("用户: " + userId + ", 配额: " + offset.getAmount() + ", 占比: " + offset.getPercent() + ", 跨度: " + offset.getSpan() + ", 区间: [" + offset.getStart() + ", " + offset.getEnd() + ")");
}
Map<Integer, Integer> countMap = new HashMap<>();
Integer userId;
Integer num;
for (int i = 0; i < allAmount; i++) {
// 由于这里是递归处理，所以如果最后为null了，说明已经到达了所有人的配额上限（奖品或者抽奖次数用完了）
userId = randomUser(userOffsetMap);
if (userId == null) {
break;
}
// 记录每个用户的中标次数，达到上限了就排除掉
num = countMap.get(userId);
if (num != null) {
countMap.put(userId, num + 1);
} else {
countMap.put(userId, 1);
}
// 次数到了上限，移除用户（可看做：中奖之后移除用户）
if (countMap.get(userId) >= userOffsetMap.get(userId).getAmount()) {
userOffsetMap.remove(userId);
}
}
// log
for (Integer key : countMap.keySet()) {
System.out.println(key + "中奖了" + countMap.get(key) + "次，概率: " + getPercent(countMap.get(key), allAmount));
}
}
/**
* 选中之后，会排除掉部分用户，递归调用，将机会让给别的人
*
* @param userOffsetMap 用户offset信息
* @return 选中的用户
*/
private Integer randomUser(Map<Integer, Offset> userOffsetMap) {
Integer userId = select(userOffsetMap);
if (!userOffsetMap.isEmpty() && userId == null) {
return randomUser(userOffsetMap);
}
return userId;
}
/**
* 按照计算好的区间，随机获取用户（即视为中标了）
*
* @param userOffsetMap 用户offset信息
* @return 选中的用户
*/
private Integer select(Map<Integer, Offset> userOffsetMap) {
// 计算一个随机数值，看他散列在哪个用户的区间
int rnum = new Random().nextInt(100);
Offset offset;
// 由于要兼顾每一个用户，所以需要循环（效率待定？）
for (Integer userId : userOffsetMap.keySet()) {
offset = userOffsetMap.get(userId);
// 100以内随机，所以需要是左侧需要等于，右侧不需要
if (offset.getStart() <= rnum && rnum < offset.getEnd()) {
return userId;
}
}
return null;
}
public static void main(String[] args) {
new Lottery().lottery();
}
class User {
private int id;
private String name;
private int amount;
public User(int id, String name, int amount) {
this.id = id;
this.name = name;
this.amount = amount;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAmount() {
return amount;
}
public void setAmount(int amount) {
this.amount = amount;
}
}
class Offset {
private float percent;
private int span;
private int start;
private int end;
private int amount;
public Offset(float percent, int span, int start, int end, int amount) {
this.percent = percent;
this.span = span;
this.start = start;
this.end = end;
this.amount = amount;
}
public float getPercent() {
return percent;
}
public void setPercent(float percent) {
this.percent = percent;
}
public int getSpan() {
return span;
}
public void setSpan(int span) {
this.span = span;
}
public int getStart() {
return start;
}
public void setStart(int start) {
this.start = start;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
public int getAmount() {
return amount;
}
public void setAmount(int amount) {
this.amount = amount;
}
}
}实现效果：
跟代码中的参数做一下简单比对，总配额是233次（可视作为233次抽奖机会），6个用户按照不同比例分配不同的配额，全部抽奖完成之后看到的概率与配额的比例是一致的，说明按概率随机抽取成功！
最后给大家赠送一本书籍《数据结构与算法经典问题解析》豆瓣评分8.6 需要的朋友可以来私信我领取
本书的目的是使读者知晓数据结构和算法的设计原理和实现，而并非单纯地讲述定理及证明。为此，本书利用不同的复杂度来改善问题的解。对于许多问题，从穷举解法开始，逐步引入问题的最佳解，并给出算法所需的运行时间和空间。
全书包含4个部分，第一部分（第1〜2章）主要描述抽象数据类型，给出算法的基本概念和复杂度分析与评价方法，并讨论几乎每章都要用到的递归和回溯技术
第二部分（第3〜9章）介绍基本数据结构，包括链表、栈、队列、树、优先队列、堆、并査集和图，对于每一种数据结构分别采用多个实例进行具体的演示。
第三部分（第10-15章）介绍数据处理的技术，包括排序、査找、选择、符号表、散列和字符串算法。
第四部分（第16〜21章）重点介绍一些常用的算法设计技术及应用，包括贪婪算法、分治算法、动态规划算法、复杂度类型，并讨论对于面试和考试的一些有用话题。本书强调问题及分析，而不侧重于理论。可以作为从事计算机研究与开发的技术人员的参考书，特别是对正在准备面试、参加选拔性考试以及校园面试的读者尤为有用。
不想把篇幅拉的太长需要的朋友可以来私信领取
书籍免费获取方式：转发文章+关注然后私信“资料”即可获得文档领取方式
同时希望大家领到之后不要做收藏党！而是能够花一些时间认真看完文档，让它真正发挥出价值来。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK