Java实现按权重随机数
一、问题定义：
问下有一个数组，这些数组中的值都有自己的权重，怎样设计才能高效的优先取出权重高的数？？
例如：
权重:8 2 11 79 权重返回的值:0 1 2 3
二、分析问题：
思路一：创建一个数组数组大小为权重和的大小，如值0的权重是8，则放入8个0值，值1的权重是2，则放入2个1值，依次类推。
然后用用一个权重和大小的随机数，产生随机数，即可。缺点要占用过多的内存。
思路二：
权重和数组w[i]存储的是[0,i]元素的所有元素的权重和 时间复杂度O(n)空间复杂度O(n)
随机[0,W[399]]看随机数落在哪个Wi内就选哪个 时间复杂度O(longn)
所以总的时间复杂度时间复杂度O(n)空间复杂度O(n)
伪代码：
轮盘赌并不是一种特别好的选择算子,但它容易实现。
首先要明白一点,由于交叉、变异等算子,并不能控制进化方向,所以进化的重任落在选择算子上。
如果明白了这一点,就好办了。
轮盘赌,就是积累概率来实现的,通常适应度大的被选择的几率较高。
假如:fit为适应度数组,共m个
fori=1tom'先求和 sum=sum+fit(i) nexti Fori=1Ton‘n-是要生成多少个个体 temp=temp+fit(i) Ifrnd<=temp/sumThen 输出i就是结果 ExitFunction EndIf Nexti
三、解决问题：
packagedatastruct;
importjava.util.HashMap;
importjava.util.Map;
/**
权重随机数：
如 权重:8 2 11 79
权重返回的值:0 1 2 3
@authorajian00579331356@qq.com
2014-2-1621:12
输出结果：{2.0=184128,11.0=348551,79.0=1308100,8.0=159221}
*/
publicclassWeightRandomTest{
privatestaticdouble[]weightArrays={8.0,2.0,11.0,79.0}; //数组下标是要返回的值，数组值为数组下标的权重
publicstaticvoidmain(String[]args){
WeightRandomweightRandom=newWeightRandom();
Map<Double,Integer>stat=newHashMap<Double,Integer>();
for(inti=0;i<2000000;i++){
intweightValue=weightRandom.getWeightRandom(weightArrays);
if(weightValue<0){
continue;
}
System.out.println("按权重返回的随机数："+weightValue);
if(stat.get(weightArrays[weightValue])==null){
stat.put(weightArrays[weightValue],1);
}else{
stat.put(weightArrays[weightValue],stat.get(weightArrays[weightValue])+1);
}
}
System.out.println(stat);
}
}
classWeightRandom{
java.util.Randomr=newjava.util.Random();
privatedoubleweightArraySum(double[]weightArrays){
doubleweightSum=0;
for(doubleweightValue:weightArrays){
weightSum+=weightValue;
}
returnweightSum;
}
publicintgetWeightRandom(double[]weightArrays){
doubleweightSum=weightArraySum(weightArrays);
doublestepWeightSum=0;
for(inti=0;i<weightArrays.length;i++){
stepWeightSum+=weightArrays[i];
if(Math.random()<=stepWeightSum/weightSum){
//System.out.println(i);
returni;
}
}
System.out.println("出错误了");
return-1;
}
}
四、归纳总结：
俄罗斯轮盘赌就是积累概率来实现
按权重负载调度等