带权重的随机数算法的实现

迷南。 2022-01-30 12:39 195阅读 0赞

在做一个银行的网页游戏的时候，涉及到一个随机抽奖的模块。具体的需求是：当用户的积分可以抽奖的时候，点击抽奖则消耗指定的积分随机抽取奖品，各种奖品的概率如下：笔记本（10%），手机（20%），充值卡（30%），积分（40%）。因为，奖品的概率是可以设置的，因此考虑Java容器中的TreeMap集合实现该算法。  
**核心逻辑：**

> 累加每个物品的权重笔记本(10%)-手机(30%)-充值卡(60%)-积分(100%)，则4个物品的的权重有效长度区间分别为（0,10\]、(10,30\]、(30,60\]、(60,100\]。然后随机出一个\[0,10)之间的随机数。落在哪个区间，则该区间之后的元素即为按权重命中的元素。

**为什么用TreeMap？**

> 因为TreeMap底层用红黑树实现，TreeMap中的key是唯一且有序的，因此TreeMap提供了如下方法：

NavigableMap<K,V>	tailMap(K fromKey, boolean inclusive) 
    			 返回此映射的部分视图，其键大于（或等于，如果 inclusive 为 true）fromKey。
    
    K	lastKey() 
    			返回映射中当前最后一个（最高）键。
    
    K	firstKey() 
              返回此映射中当前第一个（最低）键。

> 试想，当我们用普通的不可动态扩展的方法如if/switch方法实现时，必然是产生一个随机数，然后判断该随机数在哪个概率区间。TreeMap因为有序，因此刚好提供了两个方法tailMap，firstKey用于实现落点区间判断的逻辑，简洁又高效，并且方便动态扩展。  
> 具体的代码实现：

package icerno.com.weightRandom;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.SortedMap;
    import java.util.TreeMap;
    
    import org.apache.commons.math3.util.Pair;
    
    import com.cookingfox.guava_preconditions.Preconditions;
    
    public class WeightRandom<K,V extends Number> {
        private TreeMap<Double, K> weightMap = new TreeMap<Double, K>();
        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());//权重累加
            }
            
            System.out.println("------Tree init OK!--------");
        }
     
        public K random() {
            double randomWeight = this.weightMap.lastKey() * Math.random();
            SortedMap<Double, K> tailMap = this.weightMap.tailMap(randomWeight, true);
            return this.weightMap.get(tailMap.firstKey());
        }
        
        @SuppressWarnings({ "rawtypes", "unchecked" })
    	public static void main(String[] args)
    	{
        	List<Pair<String,Double>> list = new ArrayList<Pair<String,Double>>();
        	list.add(new Pair<String,Double>("A",0.20));
        	list.add(new Pair<String,Double>("C",0.50));
        	list.add(new Pair<String,Double>("B",0.30));
        	
        	WeightRandom weightRandom = new WeightRandom(list);
        	Object random = weightRandom.random();
        	System.out.println("----Key----"+random);
        	
    	}
    }

注意：TreeMap为异步的非线程安全的，因此在并发要求高时，可以使用如下代码加锁。

public static Map<Double, K> treemap = Collections.synchronizedMap(new TreeMap<Double, K>());

参考文章：  
[权重随机算法的java实现][java]  
[Java TreeMap 介绍和使用][Java TreeMap]

[java]: https://www.cnblogs.com/waterystone/p/5708063.html
[Java TreeMap]: https://blog.csdn.net/x_i_y_u_e/article/details/46372023