带权重的随机算法_权重算法

前言

现在app就是雨后春笋，嗖嗖的往外冒啊，有经验的、没经验的、有资历的、没资历的都想着创业，创业的90%以上都要做一个app出来，好像成了创业的标配。

做了app就得推广啊，怎么推，发券送钱是最多用的被不可少的了，现在好多产品或者运营都要求能够随机出优惠券的金额，但是呢又不能过于随机，送出去的券都是钱吗，投资人的钱，是吧。

所以，在随机生成的金额中就要求，小额度的几率要大，大额度的几率要小，比如说3元的70%，5块的25%，10块的5%，这个样子的概率去生成优惠券，这个怎么办呢？

对于上述的问题，直接用我们的Random.next(Integer range);就不够了。因为这个伪随机不带权重，3，5，10出现的概率都是一样的。

实现思路

还是拿上述的例子，3出现的概率是70%，我们给他的权重赋值为70，5出现的概率为25%，我们给他的权重赋值为25，10出现的概率为5%，我们给他的权重赋值为5.

我们按照顺序计算出权重的加和，把当前数字出现的权重加和前的值作为其权重范围的起点值，把加和后的值作为其权重范围的终点值。

这样的话，我们就可以使用Random.next(100)来做随机数，然后判断随机数落在的范围，然后映射到对应的优惠券数值即可。

java实现

package com.nggirl.test.weight.random;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

public class WeightRandom {
    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).intValue()+1);
        }

        System.out.println("");
    }

    private List<WeightElement> weightElements;

    public void initWeight(String[] keys, Integer[] weights){
        if(keys == null || weights == null || keys.length != weights.length){
            return;
        }

        weightElements = new ArrayList<WeightElement>();

        for(int i=0; i< keys.length; i++){
            weightElements.add(new WeightElement(keys[i], weights[i]));
        }

        rangeWeightElemnts();

        printRvs();
    }

    private void rangeWeightElemnts(){
        if(weightElements.size() == 0){
            return;
        }

        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){
        //因为元素权重范围有序递增，所以这里可以改为二分查找

        for(WeightElement e:weightElements){
            if(rv >= e.getThresholdLow() && rv < e.getThresholdHigh()){
                return e;
            }
        }

        return null;
    }

    public Integer getMaxRandomValue(){
        if(weightElements == null || weightElements.size() == 0){
            return null;
        }

        return weightElements.get(weightElements.size() - 1).getThresholdHigh();
    }

    public void printRvs(){
        for(WeightElement e:weightElements){
            System.out.println(e.toString());
        }
    }

    static class WeightElement{
        /**
         * 元素标记
         */
        private String key;
        /**
         * 元素权重
         */
        private Integer weight;
        /**
         * 权重对应随机数范围低线
         */
        private Integer thresholdLow;
        /**
         * 权重对应随机数范围高线
         */
        private Integer thresholdHigh;

        public WeightElement(){
        }

        public WeightElement(Integer weight){
            this.key = weight.toString();
            this.weight = weight;
        }

        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 String toString(){
            return "key:"+this.key + " weight:" + this.weight + " low:"+this.thresholdLow+" heigh:"+this.thresholdHigh;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

二分法的实现

    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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22