Java实现按权重随机数
作者:junjie 时间:2023-11-28 23:15:32
一、问题定义:
问下有一个数组,这些数组中的值都有自己的权重,怎样设计才能高效的优先取出权重高的数??
例如:
权重: 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;
}
}
四、归纳总结:
* 赌就是积累概率来实现
按权重负载调度等
标签:Java,权重,随机数
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
使用idea创建web框架和配置struts的方法详解
2022-11-14 14:21:52
![](https://img.aspxhome.com/file/2023/2/93072_0s.png)
javac -encoding 用法详解
2022-06-28 08:58:08
Java 爬虫服务器被屏蔽的解决方案
2022-11-06 13:23:46
![](https://img.aspxhome.com/file/2023/4/77124_0s.png)
Android热修复及插件化原理示例详解
2023-03-07 01:37:52
![](https://img.aspxhome.com/file/2023/6/137176_0s.jpg)
Springboot 整合 RocketMQ 收发消息的配置过程
2023-01-22 22:49:28
创建Spring Boot项目的几种方式总结(推荐)
2023-07-04 22:32:16
![](https://img.aspxhome.com/file/2023/0/110810_0s.jpg)
创建动态代理对象bean,并动态注入到spring容器中的操作
2021-09-04 01:02:43
![](https://img.aspxhome.com/file/2023/9/71589_0s.jpg)
springboot中使用redis并且执行调试lua脚本
2022-02-15 08:49:52
![](https://img.aspxhome.com/file/2023/1/61031_0s.png)
超详细的Spring Boot入门笔记(总结)
2022-10-26 18:44:21
![](https://img.aspxhome.com/file/2023/4/61254_0s.png)
Android 自定义输入手机号自动添加分隔符
2022-08-15 12:32:27
![](https://img.aspxhome.com/file/2023/4/139254_0s.png)
java实现动态代理示例分享
2023-04-28 15:54:49
![](https://img.aspxhome.com/file/2023/6/80316_0s.jpg)
springmvc4+hibernate4分页查询功能实现
2021-08-16 02:28:08
![](https://img.aspxhome.com/file/2023/3/68733_0s.png)
深入了解Spring中最常用的11个扩展点
2023-07-05 17:46:40
![](https://img.aspxhome.com/file/2023/1/57531_0s.png)
Android开发中的几种网络请求方式详解
2021-06-01 17:45:21
Springboot2.x+ShardingSphere实现分库分表的示例代码
2023-11-26 01:34:07
![](https://img.aspxhome.com/file/2023/1/59591_0s.jpg)
Spring+SpringMVC+MyBatis深入学习及搭建(一)之MyBatis的基础知识
2021-09-27 15:12:59
![](https://img.aspxhome.com/file/2023/3/66503_0s.png)
Java解决约瑟夫问题代码实例
2023-09-20 19:17:02
RocketMQ源码解析broker 启动流程
2022-12-25 10:50:54
详解Spring Bean的配置方式与实例化
2022-01-13 05:47:51
![](https://img.aspxhome.com/file/2023/9/89559_0s.jpg)
JAVA像SQL一样对List对象集合进行排序
2023-11-01 12:36:24
![](https://img.aspxhome.com/file/2023/8/71258_0s.jpg)