问题描述
设计一套算法，例如奖品1-10号，对应抽中权重就是1-10，再验证算法是否准确。
算法思想
- 封装奖品设置实体对应id和权重字段，用来区别限制某种奖品对应的被抽中的概率。
- 计算总权重。
- 产生一个0-1的double型随机数，把每个奖品权重/总权重，则这个随机数只要落在两个权值中间就知道是哪个奖品了。
例如1，2，3，4奖品，则对应获奖概率0.1、0.2、0.3、0.4。则对应中奖区间0-0.1、0.1-0.3、0.3-0.6、0.6-1.0。
所以假如随机数产生为0.2876282820731174，则依次判断大于0，大于0.1、大于01，小于0.3。所以索引就是第二个区间。
good1 good2 good3 good4
^ ^ ^ ^
|------||------|------||------|------|------||------|------|------|------||
0 1/10 3/10 6/10 10/10
^ ^ ^ ^
0.1 0.3 0.6 1 //权重随机算法
public static Good weightRandom(List<Good> goods) {
//抽中奖品索引
int resultIndex = -1;
//计算权重和
double sumWeight = goods.stream().mapToDouble(Good::getWeight).sum();
//产生索引随机数
double myRandom = Math.random();
//根据随机数在所有奖品分布的区域并确定所抽奖品
double proL = 0;
double proR = 0;
for (int i = 0; i < goods.size(); i++) {
proR += Double.parseDouble(String.valueOf(goods.get(i).getWeight())) / sumWeight;
if (i == 0) proL = 0;
else proL += Double.parseDouble(String.valueOf(goods.get(i - 1).getWeight())) / sumWeight;
if (myRandom >= proL && myRandom <= proR) {
resultIndex = i;
break;
}
}
return goods.get(resultIndex);
}public static class Good {
private Integer id;
private Integer weight;
public Good(Integer id, Integer prizeWeight) {
this.id = id;
this.weight = prizeWeight;
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public Integer getWeight() {
return weight;
}
public void setWeight(Integer prizeWeight) {
this.weight = prizeWeight;
}
}以下是计算10000次，4个奖品依次中奖次数为1014 1970 2990 4026。
public static void main(String[] args) {
List<Good> vos = new ArrayList<>();
vos.add(new Good(1, 1));
vos.add(new Good(2, 2));
vos.add(new Good(3, 3));
vos.add(new Good(4, 4));
//System.out.println(weightRandom(vos).getId());
int[] goodsNum = new int[5];
for (int i = 0; i < 10000; i++) {
int temp = weightRandom(vos).getId();
if (temp == 1) {goodsNum[1] += 1;}
else if (temp == 2) {goodsNum[2] += 1;}
else if (temp == 3) {goodsNum[3] += 1;}
else {goodsNum[4] += 1;}
}
System.out.println(goodsNum[1] + " " + goodsNum[2] + " " + goodsNum[3] + " " + goodsNum[4]);
}Nacos负载均衡
Nacos 提供的客户端负载均衡就是使用了该算法
例如服务1，2，3，权重1，3，2。则总权重6，分布：
server1 (0,1]
server2 (1,4]
server3 (4,6]
取(0,6]之间的随机数，在哪个范围就选择谁。思路大概就是这样，落实到代码上，用一个数组 [1/6=0.16666667, 4/6=0.66666667, 1] 来表示这三个服务的覆盖范围，使用ThreadLocalRandom或者Random获取 [0,1)内的随机数。然后使用二分查找法快速定位随机数处于哪个区间，具体源码在com.alibaba.nacos.client.naming.utils.Chooser。
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicInteger;
public class WeightRandom<T> {
private final List<T> items = new ArrayList<>();
private double[] weights;
public WeightRandom(List<ItemWithWeight<T>> itemsWithWeight) {
this.calWeights(itemsWithWeight);
}
/**
* 计算权重，初始化或者重新定义权重时使用
*
*/
public void calWeights(List<ItemWithWeight<T>> itemsWithWeight) {
items.clear();
// 计算权重总和
double originWeightSum = 0;
for (ItemWithWeight<T> itemWithWeight : itemsWithWeight) {
double weight = itemWithWeight.getWeight();
if (weight <= 0) {
continue;
}
items.add(itemWithWeight.getItem());
if (Double.isInfinite(weight)) {
weight = 10000.0D;
}
if (Double.isNaN(weight)) {
weight = 1.0D;
}
originWeightSum += weight;
}
// 计算每个item的实际权重比例
double[] actualWeightRatios = new double[items.size()];
int index = 0;
for (ItemWithWeight<T> itemWithWeight : itemsWithWeight) {
double weight = itemWithWeight.getWeight();
if (weight <= 0) {
continue;
}
actualWeightRatios[index++] = weight / originWeightSum;
}
// 计算每个item的权重范围
// 权重范围起始位置
weights = new double[items.size()];
double weightRangeStartPos = 0;
for (int i = 0; i < index; i++) {
weights[i] = weightRangeStartPos + actualWeightRatios[i];
weightRangeStartPos += actualWeightRatios[i];
}
}
/**
* 基于权重随机算法选择
*
*/
public T choose() {
double random = ThreadLocalRandom.current().nextDouble();
int index = Arrays.binarySearch(weights, random);
if (index < 0) {
index = -index - 1;
} else {
return items.get(index);
}
if (index < weights.length && random < weights[index]) {
return items.get(index);
}
// 通常不会走到这里，为了保证能得到正确的返回，这里随便返回一个
return items.get(0);
}
public static class ItemWithWeight<T> {
T item;
double weight;
public ItemWithWeight() {
}
public ItemWithWeight(T item, double weight) {
this.item = item;
this.weight = weight;
}
public T getItem() {
return item;
}
public void setItem(T item) {
this.item = item;
}
public double getWeight() {
return weight;
}
public void setWeight(double weight) {
this.weight = weight;
}
}
public static void main(String[] args) {
// for test
int sampleCount = 1_000_000;
ItemWithWeight<String> server1 = new ItemWithWeight<>("server1", 1.0);
ItemWithWeight<String> server2 = new ItemWithWeight<>("server2", 3.0);
ItemWithWeight<String> server3 = new ItemWithWeight<>("server3", 2.0);
WeightRandom<String> weightRandom = new WeightRandom<>(Arrays.asList(server1, server2, server3));
// 统计 (这里用 AtomicInteger 仅仅是因为写起来比较方便，这是一个单线程测试)
Map<String, AtomicInteger> statistics = new HashMap<>();
for (int i = 0; i < sampleCount; i++) {
statistics
.computeIfAbsent(weightRandom.choose(), (k) -> new AtomicInteger())
.incrementAndGet();
}
statistics.forEach((k, v) -> {
double hit = (double) v.get() / sampleCount;
System.out.println(k + ", hit:" + hit);
});
}
}
