摘要：
一、概述 如果有4个元素A、B、C和D，权重分别为1、2、3和4，随机结果中A:B:C:D的比例应为1:2:3:4。然后随机生成[0,10）之间的随机数。在该间隔中，间隔之后的元素是按权重命中的元素。叶节点存储元素，而非叶节点用于索引。非叶节点具有两个属性，分别存储左子树和右子树的累积权重。
平时，经常会遇到权重随机算法，从不同权重的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+树的原理。叶子结点存放元素，非叶子结点用于索引。非叶子结点有两个属性，分别保存左右子树的累加权重。如下图：
看到这个图，聪明的你应该知道怎么随机了吧。
此方法的优点是：更改一个元素，只须修改该元素到根结点那半部分的权值即可。
end