Java实现根据权重优先返回（速度较快）

不念不忘少年蓝@ 2022-09-25 04:14 210阅读 0赞

下面的实现比我最初写的快了四倍多哟。  
**实现思路**：  
我们知道，在10以内的整数里，0~3出现的概率是0.3，3~6出现的概率是0.3，6~7出现的概率是0.1，7~9出现的概率是0.2，9~10出现的概率是0.1 ；上面对应的权重可对应为3 、3 、1、2 、1 。

所以，当我们需要实现不知道权重到底是多少时，我们只需要将所有权重加起来，假设为100，然后让随机数只出现0到100，接着给每个权重设定一个区间段，权重有多大，该区间段就有多宽，其中总区间就是总权重。

在组装我们的数据上也需要一定的技巧，我们用TreeMap来组装，key是区间段后面一个值，如下面0~4区间段对应的是4，然后将后面的值（如”4444“）放进value里。

生成在总权重范围内的随机数，假设是2；然后我们根据TreeMap的ceilingKey(2) 方法获得大于等于2的最键，这里得到是4。这样就能去TreeMap里取到我们需要的值了

下面数据对应区间段：0~4 ：4444，4~11：7777，11~14：3333，14~18：4242
    public class 权重 { 
        //测试
        public static void main(String[] args) {
            String[] str1 = {
       "4","4444"}; //权重为4
            String[] str2 = {
       "7","7777"}; //权重为7
            String[] str3 = {
       "3","3333"}; //权重为3
            String[] str4 = {
       "4","4242"}; //权重为4
            List<String[]> list = new ArrayList<String[]>();
            list.add(str1);
            list.add(str2);
            list.add(str3);
            list.add(str4);
    
            Long s = System.currentTimeMillis();
            String str = null;
            for(int i=0;i<10000000;i++){
                str = new 权重().getMax(list);
            }
            Long e = System.currentTimeMillis();
            System.out.println("耗时："+(e-s));
            System.out.println(str);
            //String result = new 权重().getMax(list);
        }
    
        /** * 获得给定List集合里权重大的结果 * @param list * @return * @author Peter */
        public String getMax(List<String[]> list){      
            int len = list.size();
            int total = 0;//总权重
            //以权重区间段的后面的值作为key存当前信息
            TreeMap<Integer,String> map = new TreeMap<Integer, String>(); 
            for(int i=0; i<len; i++){
                String[] array = list.get(i);
                total += Integer.parseInt(array[0]);
                map.put(total, array[1]); 
            }
    
            int random = (int)(Math.random()*total);
            Integer key = map.ceilingKey(random);
            return map.get(key);
        }
    
    }

**思考**：  
下面的实现只是说在有10000万人的用户去取的速度快；但如果list里的数据有1千万条，而我们只取一次时的速度就没什么多大的提高，原因是于组成Map的时候耗时太多，如果我们将耗时的过程存为静态，即只在第一次访问时组装。当然，这里机List是不变的，如果List是变化的则只能用上面的方式

public class 权重 { 
    
        private static int total=0;
        private static TreeMap<Integer,String> map = null;
    
        //组装数据
        static{
            System.out.println("静态块只在第一次调用时执行");
            List<String[]> list = new ArrayList<String[]>();
            String[] str1 = {
       "1","5511155"}; 
            String[] str2 = {
       "2","5555555"};
            String[] str3 = {
       "3","55588885"};
            String[] str4 = {
       "2","500000000555"};
            list.add(str1);
            list.add(str2);
            list.add(str3);     
            list.add(str4);
            for(int i=0;i<1000000;i++){
       //1千万条数据
                list.add(str4);
            }
            int len = list.size();
            int total = 0;//总权重
            //以权重区间段的后面的值作为key存当前信息
            /*TreeMap<Integer,String>*/
            map = new TreeMap<Integer, String>(); 
            for(int i=0; i<len; i++){
                String[] array = list.get(i);
                total += Integer.parseInt(array[0]);
                map.put(total, array[1]); 
            }
        }   
    
        /** * 获得给定List集合里权重大的结果 * @param list * @return * @author Peter */
        public String getMax(){     
            int random = (int)(Math.random()*total);
            Integer key = map.ceilingKey(random);
            return map.get(key);
        }
    }