权重抽奖Util

r囧r小猫 2022-05-22 00:22 156阅读 0赞

情景：数据库中存在权重表，输入参数Map，Map包含key为activityId （一次活动的id  value为String类型）；userLeverl 用户等级（value为Integer类型，区分抽奖是否区分对待）

方式一：耦合度很高

return：权重表中查询List根据权重随机到的元素Map

注：TODO地方需要读者自由修改，文中未包含建表语句与连接数据库代码，请自由添加

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Random;
    
    
    public class LotteryWeightUtils {
    	
    	private List activityWeightList;	// 数据库权重表中根据activityId查询权重List
    	private List<ContinuousElement> lotteryList = new ArrayList<ContinuousElement>();// 概率连续集合
    	private int max; 					// 这里只需要最大值，最小值默认为0
    	
    	/**
    	 * 定义一个 权重连续集合中 元素
    	 * @author cheng_xy
    	 */
    	public class ContinuousElement {
    		private int min;
    		private int max;
    		public ContinuousElement(int min, int max) {
    			if (min > max) {
    				System.out.println("区间不合理，min不能大于max！");
    				throw new IllegalArgumentException("区间不合理，min不能大于max！");
    			}
    			this.min = min;
    			this.max = max;
    		}
    		
    		//判断当前集合是否包含特定元素
    		public boolean isContainKey(int element) {
    			boolean flag = false;
    			if (element > min && element <= max) {
    				flag = true;
    			}
    			return flag;
    		}
    	
    	}
    	
    	/**
    	 * 奖品种类为一种时不建议调用该方法
    	 * 
    	 * @param reqMap	map中包含下面两个key
    	 * 					activityId	一次活动的id（value为String类型）
    	 *					userLeverl	用户等级（value为Integer类型，区分抽奖是否区分对待）
    	 * @return
    	 */
    	public Map lotteryWeightRandom(Map reqMap) {
    		
    		//1.到数据库权重表中根据activityId查询权重
    		queryActivityWeightList(reqMap);
    		
    		//2.构造抽奖集合
    		createLuckDrawList();
    		
    		//3.随机生成奖品，返回抽奖activityWeightList中Map
    		return (Map) activityWeightList.get(randomColunmIndex());
    		
    	}
    	
    	/**
    	 * 数据库权重表中包含字段：id,活动名,发放的奖品,if_valid(该数据是否有效,1有效 0无效),权重,活动id,奖品数量,可用奖品数量,用户等级,等等
    	 * 根据实际开发需要增减
    	 * 
    	 * @param reqMap	map中包含下面两个key
    	 * 					activityId	到数据库权重表中根据activityId查询权重List
    	 * 					userLeverl	用户等级（区分抽奖是否区分对待，如：表中字段大于0，传0不区分对待，传1只查询出>1的权重，传2只查询出>1的权重...）
    	 * @return
    	 */
    	private void queryActivityWeightList(Map reqMap) {
    		// TODO 读取数据库中数据，下面是测试
    		// select * from 权重表 where if_valid = '1' and 用户等级 > userleverl 活动id = activityId;
    		activityWeightList = new ArrayList();
    		Map map = new HashMap();
    		map.put("发放的奖品", "直接给1元");
    		map.put("权重", 1);
    		
    		Map map1 = new HashMap();
    		map1.put("发放的奖品", "直接给2元");
    		map1.put("权重", 4);
    		
    		activityWeightList.add(map);
    		activityWeightList.add(map1);
    	}
    
    	/**
    	 * 构造抽奖集合
    	 * 
    	 * TODO ((Map) activityWeightList.get(i)).get("权重").toString()
    	 * 需根据实际情况修改字段名称
    	 */
    	private void createLuckDrawList() {
    		int min = 0;
    		int sortNo;// 权重
    		if (activityWeightList == null || activityWeightList.size() == 0) {
    			System.out.println("权重表中查询抽奖集合为空！");
    			throw new IllegalArgumentException("权重表中查询抽奖集合为空！");
    		}
    		
    		ContinuousElement continuousElement = null;
    		
    		for (int i = 0; i < activityWeightList.size(); i++) {
    			sortNo = Integer.valueOf(((Map) activityWeightList.get(i)).get("权重").toString());
    			min = max;
    			max = max + sortNo;
    			
    			System.out.println("min=" + min + ",max=" + max);
    			continuousElement = new ContinuousElement(min, max);
    			lotteryList.add(continuousElement);
    		}
    	}
    	
    	/**
    	 * 进行抽奖操作，返回：奖品权重lotteryList集合中的下标
    	 * @return
    	 */
    	private int randomColunmIndex() {
    		int randomNum;// 生成0——max+1间的随机数
    		int index = -1;// 抽奖获得的 数据库权重表中根据activityId查询权重List 的下标
    		Random r = new Random();
    		randomNum = r.nextInt(max) + 1;
    		int size = lotteryList.size();
    		for (int i = 0; i < size; i++) {
    			ContinuousElement ce = lotteryList.get(i);
    			if (ce.isContainKey(randomNum)) {
    				index = i;
    				break;
    			}
    		}
    		if (index == -1) {
    			System.out.println("概率集合设置不合理！");
    			throw new IllegalArgumentException("概率集合设置不合理！");
    		}
    		return index;
    	}
    	
    	public double getmax() {
    		return max;
    	}
    	
    	public List<ContinuousElement> getLotteryList() {
    		return lotteryList;
    	}
    	
    }

方式二：优化方式一，降低耦合度

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Random;
     
    public class LotteryWeightUtils {
    
    	public static void main(String[] args){
    		//第一步：查询数据库配置的权重信息，可放到缓存
    		// select * from 权重表 where if_valid = '1' and 用户等级 > userleverl 活动id = activityId;
    		List activityWeightList = new ArrayList();// 数据库权重表中根据activityId查询权重List
    		Map map = new HashMap();
    		map.put("发放的奖品", "直接给1元");
    		map.put("权重", 1);
    		
    		Map map1 = new HashMap();
    		map1.put("发放的奖品", "直接给2元");
    		map1.put("权重", 4);
    		
    		activityWeightList.add(map);
    		activityWeightList.add(map1);
    		
    		//第二步：new抽奖工具类
    		LotteryWeightUtils lottery = new LotteryWeightUtils(activityWeightList);
    		
    		//第三步：抽奖 随机生成奖品
    		Object object = activityWeightList.get(lottery.randomColunmIndex());
    	}
    	
    	
    	private List<ContinuousElement> lotteryList = new ArrayList<ContinuousElement>();// 概率连续集合
    	private int max; 					// 这里只需要最大值，最小值默认为0
    	
    	/**
    	 * 定义一个 权重连续集合中 元素
    	 * @author cheng_xy
    	 */
    	public class ContinuousElement {
    		private int min;
    		private int max;
    		public ContinuousElement(int min, int max) {
    			if (min > max) {
    				System.out.println("区间不合理，min不能大于max！");
    				throw new IllegalArgumentException("区间不合理，min不能大于max！");
    			}
    			this.min = min;
    			this.max = max;
    		}
    		
    		//判断当前集合是否包含特定元素
    		public boolean isContainKey(int element) {
    			boolean flag = false;
    			if (element > min && element <= max) {
    				flag = true;
    			}
    			return flag;
    		}
    	
    	}
    	
    	public LotteryWeightUtils() {}
    
    	/**
    	 * 构造抽奖集合
    	 * 
    	 * TODO ((Map) activityWeightList.get(i)).get("权重").toString()
    	 * 需根据实际情况修改字段名称
    	 */
    	public LotteryWeightUtils(List activityWeightList) {
    		int min = 0;
    		int sortNo;// 权重
    		if (activityWeightList == null || activityWeightList.size() == 0) {
    			System.out.println("权重表中查询抽奖集合为空！");
    			throw new IllegalArgumentException("权重表中查询抽奖集合为空！");
    		}
    		
    		ContinuousElement continuousElement = null;
    		
    		for (int i = 0; i < activityWeightList.size(); i++) {
    			sortNo = Integer.valueOf(((Map) activityWeightList.get(i)).get("权重").toString());
    			min = max;
    			max = max + sortNo;
    			
    			System.out.println("min=" + min + ",max=" + max);
    			continuousElement = new ContinuousElement(min, max);
    			lotteryList.add(continuousElement);
    		}
    	}
    	
    	/**
    	 * 进行抽奖操作，返回：奖品权重lotteryList集合中的下标
    	 * @return
    	 */
    	private int randomColunmIndex() {
    		int randomNum;// 生成0——max+1间的随机数
    		int index = -1;// 抽奖获得的 数据库权重表中根据activityId查询权重List 的下标
    		Random r = new Random();
    		randomNum = r.nextInt(max) + 1;
    		int size = lotteryList.size();
    		for (int i = 0; i < size; i++) {
    			ContinuousElement ce = lotteryList.get(i);
    			if (ce.isContainKey(randomNum)) {
    				index = i;
    				break;
    			}
    		}
    		if (index == -1) {
    			System.out.println("概率集合设置不合理！");
    			throw new IllegalArgumentException("概率集合设置不合理！");
    		}
    		return index;
    	}
    	public double getmax() {
    		return max;
    	}
    	public List<ContinuousElement> getLotteryList() {
    		return lotteryList;
    	}
    }

方式三：优化方式一、二，将List元素对比转化为TreeMap对比（效率比方式一、二高）

import com.google.common.base.Preconditions;
    /*下载地址为http://commons.apache.org/proper/commons-math/download_math.cgi，在下载页可以看到有多个压缩包可供下载（下载bin.zip就可以*/
    import org.apache.commons.math3.util.Pair;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.SortedMap;
    import java.util.TreeMap;
    
    public class WeightRandom<K,V extends Number> {
    	
    	public static void main(String[] args){
    		
    /*		
    如有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()即可找到目标元素。
    当然，也可以利用数组+二分查找等来实现。*/
    		
    		Pair pair1 = new Pair("a", 11);
    		Pair pair2 = new Pair("b", 22);
    		Pair pair3 = new Pair("c", 33);
    		List<Pair> list = new ArrayList<Pair>();
    		list.add(pair1);
    		list.add(pair2);
    		list.add(pair3);
    		
    		WeightRandom weightRandom = new WeightRandom(list);
    		Object random = weightRandom.random();
    		System.out.println(random);
    	}
    	
        private TreeMap<Double, K> weightMap = new TreeMap<Double, K>();
    
        public WeightRandom(List<Pair<K, V>> list) {
        	//参数检查的工具类--Preconditions类， 该类可以大大地简化我们代码中对于参数的预判断和处理，让我们对方法输入参数的验证实现起来更加简单优雅
            Preconditions.checkNotNull(list, "list can NOT be null!");
            for (Pair<K, V> pair : list) {
                Preconditions.checkArgument(pair.getValue().doubleValue() > 0, String.format("非法权重值：pair=%s", pair));
                double lastWeight = this.weightMap.size() == 0 ? 0 : this.weightMap.lastKey().doubleValue();//统一转为double
                this.weightMap.put(pair.getValue().doubleValue() + lastWeight, pair.getKey());//权重累加
            }
        }
    
        public K random() {
        	//Math.random()是令系统随机选取大于等于 0.0 且小于 1.0 的伪随机 double 值
            double randomWeight = this.weightMap.lastKey() * Math.random();
            //Open Declaration NavigableMap<Double, K> java.util.TreeMap.tailMap(Double fromKey, boolean inclusive)
            SortedMap<Double, K> tailMap = this.weightMap.tailMap(randomWeight, false);
            return this.weightMap.get(tailMap.firstKey());
        }
    
    }

方式四：用算法获取（效率比方法一、二、三高）

[【数学】时间复杂度O(1)的离散采样算法—— Alias method/别名采样方法][O_1_ Alias method]

import java.util.*;
    import java.util.concurrent.atomic.AtomicInteger;
    
    public class LotteryUtils {
    	private final Random random;
    	private final int[] alias;
    	private final double[] probability;
    
    	public LotteryUtils(List<Double> probabilities) {
    		this(probabilities, new Random());
    	}
    
    	public LotteryUtils(List<Double> probabilities, Random random) {
    		if (probabilities == null || random == null)
    			throw new NullPointerException();
    		if (probabilities.size() == 0)
    			throw new IllegalArgumentException("Probability vector must be nonempty.");
    		//给成员变量赋值
    		probability = new double[probabilities.size()];
    		alias = new int[probabilities.size()];
    		this.random = random;
    		
    		//取1的平均数
    		final double average = 1.0 / probabilities.size();
    		probabilities = new ArrayList<Double>(probabilities);
    		Deque<Integer> small = new ArrayDeque<Integer>();
    		Deque<Integer> large = new ArrayDeque<Integer>();
    		for (int i = 0; i < probabilities.size(); ++i) {
    			if (probabilities.get(i) >= average)
    				large.add(i);
    			else
    				small.add(i);
    		}
    		while (!small.isEmpty() && !large.isEmpty()) {
    			int less = small.removeLast();
    			int more = large.removeLast();
    			
    			probability[less] = probabilities.get(less) * probabilities.size();
    			alias[less] = more;
    			probabilities.set(more, (probabilities.get(more) + probabilities.get(less)) - average);
    			if (probabilities.get(more) >= 1.0 / probabilities.size())
    				large.add(more);
    			else
    				small.add(more);
    		}
    		
    		while (!small.isEmpty())
    			probability[small.removeLast()] = 1.0;
    		while (!large.isEmpty())
    			probability[large.removeLast()] = 1.0;
    	}
    
    	public int next() {
    		//随机一个数 0 1 2 3
    		int column = random.nextInt(probability.length);
    		/*
    			//本次测试抽奖转化或的数据
    			probability0=0.8
    			probability1=0.8
    			probability2=1.0
    			probability3=0.8
    			
    			alias0=3
    			alias1=3
    			alias2=0
    			alias3=2
    			
    			//本次测试抽奖转化的对应概率
    			1/4*4/5 0 1/4*1/5 3
    			1/4*4/5 1 1/4*1/5 3
    			1/4 2
    			1/4*4/5 3 1/4*1/5 2
    			
    			//本次抽奖转化返回的元素下标
    			0 0.2
    			1 0.2
    			2 0.3
    			3 0.3
    		*/
    		boolean coinToss = random.nextDouble() < probability[column];//随机一个小数
    		return coinToss ? column : alias[column];
    	}
    
    	public static void main(String[] args) {
    		
    		//【数学】时间复杂度O(1)的离散采样算法—— Alias method/别名采样方法
    		
    		//第一步：获取表中或缓存中奖品概率
    		//本方法的所有奖品的概率和等于1，否则不准确
    		
    		TreeMap<String, Double> map = new TreeMap<String, Double>();
    		map.put("奖品1", Double.valueOf(0.2));
    		map.put("奖品2", Double.valueOf(0.2));
    		map.put("奖品3", Double.valueOf(0.3));
    		map.put("奖品4", Double.valueOf(0.3));
    		List<Double> lotteryList = new ArrayList<Double>(map.values());//概率
    		List<String> gifts = new ArrayList<String>(map.keySet());//奖品
    		System.out.println("概率lotteryList=" + lotteryList);
    		System.out.println("奖品gifts=" + gifts);
    
    		//第二步：new抽奖工具类
    		LotteryUtils method = new LotteryUtils(lotteryList);
    
    		//第三步：抽奖
    		//用于输出每种奖品的随机次数
    		Map<String, AtomicInteger> resultMap = new HashMap<String, AtomicInteger>();
    		Long startLong = System.currentTimeMillis();
    		for (int i = 0; i < 100000000; i++) {
    			int index = method.next();
    			String key = gifts.get(index);
    			//用于奖品计数----（对比运行时间时，针对性去掉该代码）-----Start
    			if (!resultMap.containsKey(key)) {
    				resultMap.put(key, new AtomicInteger());
    			}
    			resultMap.get(key).incrementAndGet();
    			//用于奖品计数---------End		
    		}
    		Long endLong = System.currentTimeMillis(); 
    		System.out.println("1运行时间：" + (endLong - startLong) + "/n   " + resultMap);
    	}
    }

**希望对你有帮助，祝你有一个好心情，加油！**

**若有错误、不全、可优化的点，欢迎纠正与补充；转载请注明出处！**

[O_1_ Alias method]: https://blog.csdn.net/haolexiao/article/details/65157026