权重随机算法的java实现

一、概述

　　平时，经常会遇到权重随机算法，从不同权重的N个元素中随机选择一个，并使得总体选择结果是按照权重分布的。如广告投放、负载均衡等。

　　如有4个元素A、B、C、D，权重分别为1、2、3、4，随机结果中A:B:C:D的比例要为1:2:3:4。

　　总体思路：累加每个元素的权重A(1)-B(3)-C(6)-D(10)，则4个元素的的权重管辖区间分别为[0,1)、[1,3)、[3,6)、[6,10)。然后随机出一个[0,10)之间的随机数。落在哪个区间，则该区间之后的元素即为按权重命中的元素。

　　实现方法：

利用TreeMap，则构造出的一个树为:
　　　　B(3)
　　　 /      \
        /         \
     A(1)     D(10)
               /
             /
         C(6)

然后，利用treemap.tailMap().firstKey()即可找到目标元素。

当然，也可以利用数组+二分查找来实现。

二、源码

​​package​​​ ​​com.xxx.utils;​​
 
​​import​​​ ​​com.google.common.base.Preconditions;​​
​​import​​​ ​​org.apache.commons.math3.util.Pair;​​
​​import​​​ ​​org.slf4j.Logger;​​
​​import​​​ ​​org.slf4j.LoggerFactory;​​
 
​​import​​​ ​​java.util.List;​​
​​import​​​ ​​java.util.SortedMap;​​
​​import​​​ ​​java.util.TreeMap;​​
 
 
​​public​​​ ​​class​​​ ​​WeightRandom<K,V ​​​​extends​​​ ​​Number> {​​
​​private​​​ ​​TreeMap<Double, K> weightMap = ​​​​new​​​ ​​TreeMap<Double, K>();​​
​​private​​​ ​​static​​​ ​​final​​​ ​​Logger logger = LoggerFactory.getLogger(WeightRandom.​​​​class​​​​);​​
 
​​public​​​ ​​WeightRandom(List<Pair<K, V>> list) {​​
​​Preconditions.checkNotNull(list, ​​​​"list can NOT be null!"​​​​);​​
​​for​​​ ​​(Pair<K, V> pair : list) {​​
​​double​​​ ​​lastWeight = ​​​​this​​​​.weightMap.size() == ​​​​0​​​ ​​? ​​​​0​​​ ​​: ​​​​this​​​​.weightMap.lastKey().doubleValue();​​​​//统一转为double​​
​​this​​​​.weightMap.put(pair.getValue().doubleValue() + lastWeight, pair.getKey());​​​​//权重累加​​
​​}​​
​​}​​
 
​​public​​​ ​​K random() {​​
​​double​​​ ​​randomWeight = ​​​​this​​​​.weightMap.lastKey() * Math.random();​​
​​SortedMap<Double, K> tailMap = ​​​​this​​​​.weightMap.tailMap(randomWeight, ​​​​false​​​​);​​
​​return​​​ ​​this​​​​.weightMap.get(tailMap.firstKey());​​
​​}​​
 
​​}​​

三、性能

4个元素A、B、C、D，其权重分别为1、2、3、4，运行1亿次，结果如下：

从结果，可以看出，准确率在99.95%以上。

现在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;
        }
    }
}

二分法的实现

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、将所有匹配广告的权重相加sum， 
3、以相加结果为随机数的种子，生成1~sum之间的随机数rd 
4、.接着遍历所有广告，访问顺序可以随意.将当前节点的权重值加上前面访问的各节点权重值得curWt,判断curWt >=  rd,如果条件成立则返回当前节点,如果不是则继续累加下一节点. 直到符合上面的条件,由于rd<=sum 因此一定存在curWt>=rd。 
特别说明：

此算法和广告的顺序无关 

​​import​​​ ​​java.util.ArrayList;​​
​​import​​​ ​​java.util.Collections;​​
​​import​​​ ​​java.util.Comparator;​​
​​import​​​ ​​java.util.LinkedHashMap;​​
​​import​​​ ​​java.util.List;​​
​​import​​​ ​​java.util.Map;​​
 
​​public​​​ ​​class​​​ ​​Test {​​
 
​​/**​​
​​* @param args​​
​​*/​​
​​@SuppressWarnings​​​​(​​​​"unchecked"​​​​)​​
​​public​​​ ​​static​​​ ​​void​​​ ​​main(String[] args) {​​
 
​​List<Node> arrNodes = ​​​​new​​​ ​​ArrayList<Node>();​​
​​Node n = ​​​​new​​​ ​​Node(​​​​10​​​​, ​​​​"测试1"​​​​);​​
​​arrNodes.add(n);​​
​​n = ​​​​new​​​ ​​Node(​​​​20​​​​, ​​​​"测试2"​​​​);​​
​​arrNodes.add(n);​​
​​n = ​​​​new​​​ ​​Node(​​​​30​​​​, ​​​​"测试3"​​​​);​​
​​arrNodes.add(n);​​
​​n = ​​​​new​​​ ​​Node(​​​​40​​​​, ​​​​"测试4"​​​​);​​
​​arrNodes.add(n);​​
 
​​//Collections.sort(arrNodes, new Node());​​
​​Map<String, Integer> showMap = ​​​​null​​​​;​​
​​int​​​ ​​sum = getSum(arrNodes);​​
​​int​​​ ​​random = ​​​​0​​​​;​​
​​Node kw = ​​​​null​​​​;​​
​​for​​​​(​​​​int​​​ ​​k = ​​​​0​​​​; k < ​​​​20​​​​; k++) {​​
​​showMap = ​​​​new​​​ ​​LinkedHashMap<String, Integer>();​​
​​for​​​​(​​​​int​​​ ​​i = ​​​​0​​​​; i < ​​​​100​​​​; i++) {​​
​​random = getRandom(sum);​​
​​kw = getKW(arrNodes, random);​​
​​if​​​​(showMap.containsKey(kw.kw)) {​​
​​showMap.put(kw.kw, showMap.get(kw.kw) + ​​​​1​​​​);​​
​​} ​​​​else​​​ ​​{​​
​​showMap.put(kw.kw, ​​​​1​​​​);​​
​​}​​
​​//System.out.println(i + " " +random + " " + getKW(arrNodes, random));​​
​​}​​
​​System.out.print(k + ​​​​" "​​​​);​​
​​System.out.println(showMap);​​
​​}​​
​​}​​
 
​​public​​​ ​​static​​​ ​​Node getKW(List<Node> nodes, ​​​​int​​​ ​​rd) {​​
​​Node ret = ​​​​null​​​​;​​
​​int​​​ ​​curWt = ​​​​0​​​​;​​
​​for​​​​(Node n : nodes){​​
​​curWt += n.weight;​​
​​if​​​​(curWt >= rd) {​​
​​ret = n;​​
​​break​​​​;​​
​​}​​
​​}​​
​​return​​​ ​​ret;​​
​​}​​
​​public​​​ ​​static​​​ ​​int​​​ ​​getSum(List<Node> nodes) {​​
​​int​​​ ​​sum = ​​​​0​​​​;​​
​​for​​​​(Node n : nodes)​​
​​sum += n.weight;​​
​​return​​​ ​​sum;​​
​​}​​
​​public​​​ ​​static​​​ ​​int​​​ ​​getRandom(​​​​int​​​ ​​seed) {​​
​​return​​​ ​​(​​​​int​​​​)Math.round(Math.random() * seed);​​
​​}​​
​​}​​
​​class​​​ ​​Node ​​​​implements​​​ ​​Comparator{​​
​​int​​​ ​​weight = ​​​​0​​​​;​​
​​String kw = ​​​​""​​​​;​​
 
​​public​​​ ​​Node() {}​​
 
​​public​​​ ​​Node(​​​​int​​​ ​​wt, String kw) {​​
​​this​​​​.weight = wt;​​
​​this​​​​.kw = kw;​​
​​}​​
​​public​​​ ​​String toString(){​​
​​StringBuilder sbBuilder = ​​​​new​​​ ​​StringBuilder();​​
​​sbBuilder.append(​​​​" weight="​​​​).append(weight);​​
​​sbBuilder.append(​​​​" kw"​​​​).append(kw);​​
​​return​​​ ​​sbBuilder.toString();​​
​​}​​
​​public​​​ ​​int​​​ ​​compare(Object o1, Object o2) {​​
​​Node n1 = (Node)o1;​​
​​Node n2 = (Node)o2;​​
​​if​​​​(n1.weight > n2.weight)​​
​​return​​​ ​​1​​​​;​​
​​else​​
​​return​​​ ​​0​​​​;​​
​​}​​
​​}​​

​​http://www.jb51.net/article/65058.htm​​

根据权重进行抽取的算法应用比较广泛，其中抽奖便是主要用途之一。正好这几天也正在进行抽奖模块的开发，整个抽奖模块涉及到的地方大概有三处，分别是后台进行奖品的添加（同时设置权重和数量），前台根据后台配置生成抽奖队列并根据指令开始抽奖活动，最后一部分是后台统计中奖情况并设置物流状态。本文主要针对前台抽奖算法进行介绍如何根据权重设置每个奖品被抽到的概率。

抽奖算法的核心是根据权重设置随机数出现的概率，在此我将它封装成一个生成随机数的随机类，代码如下：

/** 
 * JAVA 返回随机数，并根据概率、比率 
 *  
 */  
public class MathRandom {  
      
private static Log logger = LogFactory.getLog(MathRandom.class);  
  
/** 
     * Math.random()产生一个double型的随机数，判断一下 每个奖品出现的概率 
     *  
     * @return int 
     *  
     */  
public int PercentageRandom(List<RewardPrize> prizes) {  
new DecimalFormat("######0.00");    
int random = -2;  
try{  
double sumWeight = 0;  
//计算总权重  
for(RewardPrize rp_1 : prizes){  
                sumWeight += rp_1.getPrize_weight();  
            }  
double randomNumber;  
            randomNumber = Math.random();  
"randomNumber是：" + randomNumber);  
double d1 = 0;  
double d2 = 0;  
              
for(int i=0;i<prizes.size();i++){  
                d2 += Double.parseDouble(String.valueOf(prizes.get(i).getPrize_weight()))/sumWeight;  
if(i==0){  
0;  
else{  
1).getPrize_weight()))/sumWeight;  
                }  
if(randomNumber >= d1 && randomNumber <= d2){  
                    random = i;  
"d1是：" + d1);  
"d2是：" + d2);  
break;  
                }  
            }  
catch(Exception e){  
            System.out.println(e.getMessage());  
"生成抽奖随机数出错，出错原因：" + e.getMessage());  
1;  
        }  
return random;  
    }  
  
/** 
     * 测试主程序 
     *  
     * @param agrs 
     */  
public static void main(String[] agrs) {  
int i = 0;  
new MathRandom();  
new ArrayList();  
for(int m=0;m<100;m++){  
new RewardPrize();  
10);//每个奖品数量设置10个  
1);//每个奖品的权重都设置成1，也就是每个奖品被抽到的概率相同（可根据情况自行设置权重）  
            prizes.add(rp);  
        }  
for (i = 0; i <= 100; i++)// 打印100个测试概率的准确性  
        {  
            System.out.println(a.PercentageRandom(prizes));  
        }  
    }  
}

简单介绍一下上面的代码含义，首先计算出待选奖品的总权重，这样做的目的是可以随意设置奖品权重，不必再考虑权重之和是否等于100。随机规则是首先生成一个随机数randomNumber（生成的随机数位于0到1的左开右闭区间），然后分别计算出当前奖品前前面所有有奖品（不包括当前奖品）的概率和d1和当前奖品后面（包括当前奖品）所有奖品的概率和d2，然后判断生成的随机数randomNumber是否已处于d1和d2之间，如果处于该区间之内则当前奖品将被抽中。

​​http://www.open-open.com/code/view/1455771789339​​

权重随机算法在抽奖，资源调度等系统中应用还是比较广泛的，一个简单的按照权重来随机的实现，权重为几个随机对象(分类)的命中的比例，权重设置越高命中越容易，之和可以不等于100；

简单实现代码如下：

import java.util.ArrayList;  
    import java.util.List;  
    import java.util.Random;  
      
    public class WeightRandom {  
        static List<WeightCategory>  categorys = new ArrayList<WeightCategory>();  
        private static Random random = new Random();  
          
        public static void initData() {  
            WeightCategory wc1 = new WeightCategory("A",60);  
            WeightCategory wc2 = new WeightCategory("B",20);  
            WeightCategory wc3 = new WeightCategory("C",20);  
            categorys.add(wc1);  
            categorys.add(wc2);  
            categorys.add(wc3);  
        }  
      
        public static void main(String[] args) {  
              initData();  
              Integer weightSum = 0;  
              for (WeightCategory wc : categorys) {  
                  weightSum += wc.getWeight();  
              }  
      
              if (weightSum <= 0) {  
               System.err.println("Error: weightSum=" + weightSum.toString());  
               return;  
              }  
              Integer n = random.nextInt(weightSum); // n in [0, weightSum)  
              Integer m = 0;  
              for (WeightCategory wc : categorys) {  
                   if (m <= n && n < m + wc.getWeight()) {  
                     System.out.println("This Random Category is "+wc.getCategory());  
                     break;  
                   }  
                   m += wc.getWeight();  
              }  
      
                
        }  
      
    }  
      
    class WeightCategory {  
        private String category;  
        private Integer weight;  
          
      
        public WeightCategory() {  
            super();  
        }  
      
        public WeightCategory(String category, Integer weight) {  
            super();  
            this.setCategory(category);  
            this.setWeight(weight);  
        }  
      
      
        public Integer getWeight() {  
            return weight;  
        }  
      
        public void setWeight(Integer weight) {  
            this.weight = weight;  
        }  
      
        public String getCategory() {  
            return category;  
        }  
      
        public void setCategory(String category) {  
            this.category = category;  
        }  
    }

​​http://www.open-open.com/code/view/1423987535515​​