服务器之家

服务器之家 > 正文

Java实现按权重随机数

时间:2019-12-17 13:16     来源/作者:junjie

一、问题定义:

问下有一个数组,这些数组中的值都有自己的权重,怎样设计才能高效的优先取出权重高的数??

例如:

复制代码代码如下:

权重: 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<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;  
    }     
}  

 

四、归纳总结:

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

按权重负载调度等

标签:

相关文章

热门资讯

玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分 2019-06-21
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
配置IIS网站web服务器的安全策略配置解决方案
配置IIS网站web服务器的安全策略配置解决方案 2019-05-23
Nginx服务器究竟是怎么执行PHP项目
Nginx服务器究竟是怎么执行PHP项目 2019-05-24
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情 2019-06-22
返回顶部