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个

for i=1 to m '先求和
sum=sum+fit(i)
next i
for i = 1 to n ‘n-是要生成多少个个体
temp = temp + fit(i)
if rnd <= temp / sum then
   输出 i 就是结果
exit function
end if
next i

三、解决问题：

package datastruct; 
 
import java.util.hashmap; 
import java.util.map; 
 
/**
权重随机数：
如              权重:8  2  11  79
        权重返回的值:0  1  2   3
@author ajian005
2014-2-16 21:12
输出结果：{2.0=184128, 11.0=348551, 79.0=1308100, 8.0=159221}
*/ 
 
public class weightrandomtest { 
    private static double[] weightarrays = {8.0,2.0,11.0,79.0};  // 数组下标是要返回的值，数组值为数组下标的权重 
    public static void main(string[] args) { 
        weightrandom weightrandom = new weightrandom(); 
        map<double, integer> stat = new hashmap<double, integer>(); 
        for (int i = 0; i < 2000000; i++) { 
            int weightvalue = 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); 
    } 
} 
 
class weightrandom { 
    java.util.random r = new java.util.random(); 
    private double weightarraysum(double [] weightarrays) { 
        double weightsum = 0; 
        for (double weightvalue : weightarrays) { 
            weightsum += weightvalue; 
        } 
        return weightsum; 
    } 
    public int getweightrandom(double [] weightarrays) { 
        double weightsum = weightarraysum(weightarrays); 
        double stepweightsum = 0; 
        for (int i = 0; i < weightarrays.length; i++) { 
            stepweightsum += weightarrays[i]; 
            if (math.random() <= stepweightsum/weightsum) { 
                //system.out.println(i); 
                return i; 
            } 
        } 
        system.out.println("出错误了"); 
        return -1; 
    }    
} 

四、归纳总结：

俄罗斯轮盘赌就是积累概率来实现

按权重负载调度等