Java实现按权重随机数

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 79331356@qq.com

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 stat = new HashMap(); 

        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.outhttp://.println("出错误了"); 

        return -1; 

    }    

}

四、归纳总结：

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

按权重负载调度等

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。