权重随机算法的java实现
【摘要】
一、概述
平时，经常会遇到权重随机算法，从不同权重的N个元素中随机选择一个，并使得总体选择结果是按照权重分布的。如广告投放、负载均衡等。
如有4个元素A、B、C、D，权重分别为1、2、3、4，随机结果中A:B:C:D的比例要为1:2:3:4。
总体思路：累加每个元素的权重A(1)-B(3)-C(6)-D(10)，则4个元素的...
一、概述
平时，经常会遇到权重随机算法，从不同权重的N个元素中随机选择一个，并使得总体选择结果是按照权重分布的。如广告投放、负载均衡等。
如有4个元素A、B、C、D，权重分别为1、2、3、4，随机结果中A:B:C:D的比例要为1:2:3:4。
总体思路：累加每个元素的权重A(1)-B(3)-C(6)-D(10)，则4个元素的的权重管辖区间分别为[0,1)、[1,3)、[3,6)、[6,10)。然后随机出一个[0,10)之间的随机数。落在哪个区间，则该区间之后的元素即为按权重命中的元素。
实现方法：
利用TreeMap，则构造出的一个树为:
B(3)
/ \
/ \
A(1) D(10)
/
/
C(6)
然后，利用treemap.tailMap().firstKey()即可找到目标元素。
当然，也可以利用数组+二分查找来实现。
二、源码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
package com.xxx.utils;
import com.google.common.base.Preconditions;
import org.apache.commons.math3.util.Pair;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class WeightRandom<K,V extends Number> {
private TreeMap<Double, K> weightMap = new TreeMap<Double, K>();
private static final Logger logger = LoggerFactory.getLogger(WeightRandom. class );
public WeightRandom(List<Pair<K, V>> list) {
Preconditions.checkNotNull(list, "list can NOT be null!" );
for (Pair<K, V> pair : list) {
double lastWeight = this .weightMap.size() == 0 ? 0 : this .weightMap.lastKey().doubleValue(); //统一转为double
this .weightMap.put(pair.getValue().doubleValue() + lastWeight, pair.getKey()); //权重累加
}
}
public K random() {
double randomWeight = this .weightMap.lastKey() * Math.random();
SortedMap<Double, K> tailMap = this .weightMap.tailMap(randomWeight, false );
return this .weightMap.get(tailMap.firstKey());
}
}
|
三、性能
4个元素A、B、C、D，其权重分别为1、2、3、4，运行1亿次，结果如下：
| 元素 | 命中次数 | 误差率 |
| A | 10004296 | 0.0430% |
| B | 19991132 | 0.0443% |
| C | 30000882 | 0.0029% |
| D | 40003690 | 0.0092% |
从结果，可以看出，准确率在99.95%以上。
四、另一种实现
利用B+树的原理。叶子结点存放元素，非叶子结点用于索引。非叶子结点有两个属性，分别保存左右子树的累加权重。如下图：
看到这个图，聪明的你应该知道怎么随机了吧。
此方法的优点是：更改一个元素，只须修改该元素到根结点那半部分的权值即可。
更多面试题请狠狠的点击 下载
文章来源: aaaedu.blog.csdn.net，作者：tea_year，版权归原作者所有，如需转载，请联系作者。
原文链接：aaaedu.blog.csdn.net/article/details/75653306
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）