欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Java实现】带权重的随机数算法

程序员文章站 2022-03-07 10:29:30
...

我们按照顺序计算出权重的加和,把当前数字出现的权重加和前的值作为其权重范围的起点值,把加和后的值作为其权重范围的终点值。
这样的话,我们就可以使用Random.next(100)来做随机数,然后判断随机数落在的范围,然后映射到对应的优惠券数值即可。

import java.util.*;
public class WeightRandom {
    private List<WeightElement> weightElements;
    public void initWeight(String[] keys, Integer[] weights){
        if(keys == null || weights == null || keys.length != weights.length){//异常传参情况
            return;
        }
        weightElements = new ArrayList<>();
        for (int i=0; i< keys.length; i++){
            weightElements.add(new WeightElement(keys[i], weights[i]));
        }
        if(weightElements.size() == 0){
            return;
        }
        //初始化后分配各个key中的元素值
        WeightElement ele0 = weightElements.get(0);
        ele0.setThresholdLow(0);
        ele0.setThresholdHigh(ele0.getWeight());
        for (int i = 1; i < weightElements.size(); i++){
            WeightElement curElement = weightElements.get(i);
            WeightElement preElement = weightElements.get(i - 1);
            curElement.setThresholdLow(preElement.getThresholdHigh());
            curElement.setThresholdHigh(curElement.getThresholdLow() + curElement.getWeight());
        }
    }

    //二分查找写法
    public WeightElement getElementByRandomValue(Integer rv){
        if(rv < 0 || rv > getMaxRandomValue()-1){
            return null;
        }
        //此时rv必然在0 - getMaxRandomValue()-1范围内,
        //也就是必然能够命中某一个值
        int start = 0, end = weightElements.size() - 1;
        int index = weightElements.size()/2;
        while(true){
            if(rv < weightElements.get(index).getThresholdLow()){
                end = index - 1;
            }else if(rv >= weightElements.get(index).getThresholdHigh()){
                start = index + 1;
            }else{
                return weightElements.get(index);
            }
            index = (start + end)/2;
        }
    }

    /**非二分查找的写法
    public WeightElement getElementByRandomValue(Integer rv){
        //因为元素权重范围有序递增,所以这里可以改为二分查找
        for (WeightElement e:weightElements){
            if(rv >= e.getThresholdLow() && rv < e.getThresholdHigh()){
                return e;
            }
        }
        return null;
    }**/
    public int getMaxRandomValue(){
        if(weightElements == null || weightElements.size() == 0){
            return 0;
        }
        return weightElements.get(weightElements.size() - 1).getThresholdHigh();
    }
    static class WeightElement{
        //元素标记
        private String key;
        //元素权重
        private Integer weight;
        //权重对应随机数范围下限和上限
        private Integer thresholdLow;
        private Integer thresholdHigh;
        public WeightElement(String key, Integer weight){
            this.key = key;
            this.weight = weight;
        }
        public String getKey() {
            return key;
        }
        public void setKey(String key) {
            this.key = key;
        }
        public Integer getWeight() {
            return weight;
        }
        public void setWeight(Integer weight) {
            this.weight = weight;
        }
        public Integer getThresholdLow() {
            return thresholdLow;
        }
        public void setThresholdLow(Integer thresholdLow) {
            this.thresholdLow = thresholdLow;
        }
        public Integer getThresholdHigh() {
            return thresholdHigh;
        }
        public void setThresholdHigh(Integer thresholdHigh) {
            this.thresholdHigh = thresholdHigh;
        }
        
        public static void main(String[] args){
            WeightRandom wr = new WeightRandom();
            wr.initWeight(new String[]{"1","2","3","4"}
                    , new Integer[]{100,100,200,600});
            Random r = new Random();
            for (int i = 0; i < 10; i++){
                Integer rv = r.nextInt(wr.getMaxRandomValue());
                System.out.println(rv);
                System.out.println(wr.getElementByRandomValue(rv).getKey() + " " + rv);
            }

            //针对随机到的元素个数做一个简单测试
            HashMap<String, Integer> keyCount = new HashMap<String, Integer>();
            keyCount.put("1", 0);
            keyCount.put("2", 0);
            keyCount.put("3", 0);
            keyCount.put("4", 0);
            for (int i = 0; i < 10000; i++){
                Integer rv = r.nextInt(wr.getMaxRandomValue());
                String key = wr.getElementByRandomValue(rv).getKey();
                keyCount.put(key, keyCount.get(key) +1);
            }
            System.out.println(keyCount);
            System.out.println("");
        }
    }
}
```

结果:{1=1018, 2=1008, 3=2081, 4=5893}