java语言实现权重随机算法完整实例

2019-11-26 10:49:36

字体：大中小

来源：转载

供稿：网友

前言

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

结果：

2 1028764 876

二分法的实现

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

下面再分享一则实例，加强对权重随机算法的理解，一次到位！

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

结果：