权重抽奖算法
   一些代码   0 评论   296 浏览

权重抽奖算法

   一些代码   0 评论   296 浏览

问题描述

设计一套算法,例如奖品1-10号,对应抽中权重就是1-10,再验证算法是否准确。

算法思想

  1. 封装奖品设置实体对应id和权重字段,用来区别限制某种奖品对应的被抽中的概率。
  2. 计算总权重。
  3. 产生一个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);
        });
    }
}

Nacos源码参考:https://github.com/alibaba/nacos/blob/develop/client/src/main/java/com/alibaba/nacos/client/naming/utils/Chooser.java

本文由 RawChen 发表, 最后编辑时间为:2022-03-23 18:20
如果你觉得我的文章不错,不妨鼓励我继续写作。

发表评论
选择表情
Top