加权随机算法的实现_JAVA_编程开发_程序员俱乐部

加权随机算法，一般用于抽奖，资源调度等场景，话不多说，上代码：

class="java">
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * @author Veiking
 * 加权算法原子对象，具体使用时继承
 */
@Data
@NoArgsConstructor
@AllArgsConstructor
public class Atom {
	/**
	 * 对象标识参数
	 */
	private String id;
	/**
	 * 对象权重参数
	 */
	private int weight;
}

专门剥出来一个基本对象（就连这个属性id都是多余的，纯粹是为了让看起来更清晰）；
这段各属性本来应该有对应的get、set方法、构造方法，这里边使用了一组lombok的标签，让代码看起来要简练不少，感兴趣的可以百度下，不喜欢的请自行删替；

import java.util.ArrayList;
import java.util.Random;

/**
 * 加权随机算法，获取带有权值的随机元素
 * 用于抽奖，资源调度等场景
 * @author Veiking
 */
public class WeightedRandom {
	
	/**
	 * 获取加权随机对象
	 * @param atomList
	 * @return Atom
	 */
	public static Atom getWeightedRandomAtom(ArrayList<Atom> atomList){
		if(atomList.isEmpty()){
			return null;
		}
		int weightSum = 0;//总权值
		for(Atom atom : atomList){
			weightSum += atom.getWeight();
		}
		//获取总权值之间任意一随机数
		int random = new Random().nextInt(weightSum);  //random in [0, weightSum) 
		//{.},{..},{...},{....}...根据权值概率区间，获得加权随机对象
		for(Atom atom : atomList){
			random -= atom.getWeight();
			if (random < 0) {
                return atom;
            }
		}
		return null;
	}
}

算法实现，原理就是那个注释的大括号，随机数散列到不同比重的区间，获取相应比重的对象；

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
/**
 * 测试类
 * @author Veiking
 */
public class WeightedRandomTest {

	public static void main(String[] args) {
		ArrayList<Atom> atomList = new ArrayList<Atom>();
		atomList.add(new Atom("0000001", 10));
		atomList.add(new Atom("0000002", 20));
		atomList.add(new Atom("0000003", 30));
		atomList.add(new Atom("0000004", 40));
		//atomList.add(new Atom("0000005", 50));
		Atom atom;
		atom = WeightedRandom.getWeightedRandomAtom(atomList);
		System.out.println("单个实例：" + atom);
		//累积记录某种对象出现的次数
		Map<String, Integer> countAtom = new HashMap<String, Integer>();
		for (int i = 0; i < 100000; i++) {
			atom = WeightedRandom.getWeightedRandomAtom(atomList);
			if (countAtom.containsKey(atom.getId())) {
				countAtom.put(atom.getId(), countAtom.get(atom.getId()) + 1);
			} else {
				countAtom.put(atom.getId(), 1);
			}
		}
		System.out.println("概率统计：");
		for (String id : countAtom.keySet()) {
			System.out.println(" " + id + " 出现了 " + countAtom.get(id) + " 次");
		}
	}
}

测试类，为了直观体现，把那个比重为50的给注释掉了（这里比重总和没有要求，任意），可以一下看看，效果如下：

单个实例：Atom(id=0000002, weight=20)
概率统计：
 0000004 出现了 39898 次
 0000002 出现了 20191 次
 0000003 出现了 29888 次
 0000001 出现了 10023 次

概率权重这种东西，没有绝对，只有相对。