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) 伪代码: 轮盘赌 并不是一种特别好的选择算子,但它容易实现。 轮盘赌,就是积累概率来实现的,通常适应度大的被选择的几率较高。 复制代码 代码如下: 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<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; } } 四、归纳总结: 俄罗斯轮盘赌就是积累概率来实现 按权重负载调度等 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |