通过权值来获取渠道的平均算法

package com.mytest;

import java.io.Serializable;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

import org.apache.commons.lang3.StringUtils;

class MsgChannel implements Serializable{
   
   
    private static final long serialVersionUID = 1895082597124213342L;
    private String id;
    private String name;
    private String signName;
    private int status;//状态
    private int priority;//权重

    private Map<String,String> paramMap = new HashMap<>();

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getSignName() {
        return signName;
    }

    public void setSignName(String signName) {
        this.signName = signName;
    }

    public int getStatus() {
        return status;
    }

    public void setStatus(int status) {
        this.status = status;
    }

    public void addParam(String key,String value){
        paramMap.put(key,value);
    }

    public String getParam(String key){
        String s= paramMap.get(key);
        return s==null?"":s;
    }

    public int getParamInt(String key){
        String v = paramMap.get(key);
        if(StringUtils.isBlank(v)){
            return 0;
        }
        try{
            return Integer.parseInt(v);
        }catch(Exception e){
            return 0;
        }
    }

    public Map<String, String> getParamMap() {
        return paramMap;
    }

    public void setParamMap(Map<String, String> paramMap) {
        this.paramMap = paramMap;
    }

    /**
     * @return the priority
     */
    public int getPriority() {
        return priority;
    }

    /**
     * @param priority the priority to set
     */
    public void setPriority(int priority) {
        this.priority = priority;
    }
   
}
/**
* @author coolboyysy [coolboyysy @126.com]
* @since 15-3-6
*/
public class RandomAverageUtil {
   
    /**
     * 通过权值来获取渠道id
     * 算法: 例如权值为1,2,3,5 则总权值为11 ，分为4档，[1][2-3][4-6][7-11]随机抽取11内自然数，落在哪个区间内就只该权值的值,随机命中率为1/11,2/11,3/11,5/11。
     *       即便是权值均等，此方法也一样适用。
     * 特点：时间复杂度为T(n) = O(n)
     *       使用累计方法获取对应的channel,例如：11的总权值，我随机抽到7，则比对，0+1，0+1+2，0+1+2+3，0+1+2+3+5四次，在第四次获取到的即为选中的channel
     * @param channels
     * @return
     */
    public static MsgChannel getSpecialChannel(List<MsgChannel> channels){
        MsgChannel  luckChannel = null;
        if(null!=channels&&channels.size()>0){
            int totalrate = 0;
            for (MsgChannel channel:channels) {
                totalrate = totalrate+channel.getPriority();
            }
            if(totalrate==0){
               int index = (int) (Math.random() * channels.size());
                luckChannel = channels.get(index);
                return   luckChannel;
            }
            int hitnumber = new Random().nextInt(totalrate);
            int tmp_total = 0;
            for (MsgChannel channel:channels) {
                tmp_total += channel.getPriority();
                if (tmp_total >= hitnumber) {
                    luckChannel = channel;
                    break;
                }
             }
        }
        return luckChannel;
    }
   
    /**
     * 通过权值来获取渠道id
     * 算法: 例如权值为1,2,3,5 则总权值为11 ，分为11档，填入[0-11)内自然数，随机取值,随机命中率为1/11,2/11,3/11,5/11。
     *       即便是权值均等，此方法也一样适用。
     * 特点：时间复杂度为T(n) = O(n^2)
     * 使用累计方法获取对应的channel,例如：11的总权值，我随机抽到7，则直接取得7对应的channel
     * @param channels
     * @return
     */
    public static MsgChannel getLuckyChannel(List<MsgChannel> channels){
        MsgChannel  luckChannel = null;
        if(null!=channels&&channels.size()>0){
         
            int totalrate = 0;
            Map<Integer,MsgChannel> map = new HashMap<>();
            for (MsgChannel channel:channels) {
                for (int j = totalrate; j < totalrate+channel.getPriority(); j++) {
                    map.put(j, channel);
                }
                totalrate += channel.getPriority();
            }
            if(totalrate==0){
                int index = (int) (Math.random() * channels.size());
                 luckChannel = channels.get(index);
                 return   luckChannel;
             }
            int hitnumber = new Random().nextInt(totalrate);
            luckChannel = map.get(hitnumber);
        }
        return luckChannel;
    }
    /**
     * 通过权值来获取渠道id
    * 算法: 例如权值为1,2,3,5 则总权值为11 ，分为11档，在数组内填入[0-11)内自然数，map 中填入对应id的channel，随机取值,随机命中率为1/11,2/11,3/11,5/11。
     *       即便是权值均等，此方法也一样适用。
     * 特点：时间复杂度为T(n) = O(n^2+1)
     * 使用累计方法获取对应的channel,例如：11的总权值，我随机抽到7，则直接取得index为7对应的map中的channel
     * @param channels
     * @return
     */
    public static MsgChannel getLuckChannel(List<MsgChannel> channels){
        MsgChannel  luckChannel = null;
        if(null!=channels&&channels.size()>0){
            int totalrate = 0;
            int sum = 0;
            for (MsgChannel channel:channels) {
                sum += channel.getPriority();
            }
            if(sum==0){
                int index = (int) (Math.random() * channels.size());
                 luckChannel = channels.get(index);
                 return   luckChannel;
             }
           
            int[] temp = new int[sum];
            Map<Integer,MsgChannel> map = new HashMap<>();
            for (MsgChannel channel:channels) {
                for (int j = totalrate; j < totalrate+channel.getPriority(); j++) {
                    temp[j]=j;
                    map.put(j, channel);
                }
                totalrate += channel.getPriority();
            }
            int index = (int) (Math.random() * temp.length);
            luckChannel = map.get(index);
        }
       
        return luckChannel;
    }
   
   
    /**
     * 通过权值来获取渠道id
     * 算法: 例如权值为1,2,3,5 则总权值为11 ，分为11档，填入[0-11)内自然数为key的map中，随机取值,随机命中率为1/11,2/11,3/11,5/11。
     *       即便是权值均等，此方法也一样适用。
     * 特点：时间复杂度为T(n) = O(n^2)
     *       使用累计方法获取对应的channel,例如：11的总权值，我随机抽到7，则直接取得index为7对应的map中的channel
     *       但随机抽取方法是按时间来做，因此，随着系统时间的不同，会有不同的几率表现，在瞬时大规模时候，偏向其中几个。适合随着时间长度增加而进行的随机平均算法
     * @param channels
     * @return
     */
    public static MsgChannel getTimeLuckChannel(List<MsgChannel> channels){
        MsgChannel  luckChannel = null;
        if(null!=channels&&channels.size()>0){
            int totalrate = 0;
            Map<Integer,MsgChannel> map = new HashMap<>();
            for (MsgChannel channel:channels) {
                for (int j = totalrate; j < totalrate+channel.getPriority(); j++) {
                    map.put(j, channel);
                }
                totalrate += channel.getPriority();
            }
            if(totalrate>0){
                int index =  (int) (System.currentTimeMillis()%totalrate)+1;
                luckChannel = map.get(index);
            }else{
                int index = (int) (Math.random() * channels.size());
                luckChannel = channels.get(index);
            }
        }
        return luckChannel;
    }
   
    /**
     * 算术除法运算
     * @param a
     * @param b
     * @return
     */
    public static String  devideNum(int a,int b){
        if(b==0){
            return String.valueOf(a);
        }
        BigDecimal bda = new BigDecimal(String.valueOf(a));
        BigDecimal bdb = new BigDecimal(String.valueOf(b));
      
        bda.setScale(5,BigDecimal.ROUND_HALF_UP);
        bdb.setScale(5,BigDecimal.ROUND_HALF_UP);
        BigDecimal res = bda.divide(bdb,5,BigDecimal.ROUND_HALF_UP);
        double f =res.setScale(5,BigDecimal.ROUND_HALF_UP).doubleValue();
        return String.format("%.2f", f);
    }
   
   
   
    /**
     * Map排序算法
     * @param map
     */
    public static void sortMap(Map<MsgChannel, Integer> map){
        List<Map.Entry<MsgChannel, Integer>> infoIds = new ArrayList<Map.Entry<MsgChannel, Integer>>(map.entrySet()); 
        // 排序 
        Collections.sort(infoIds, new Comparator<Map.Entry<MsgChannel, Integer>>() { 
            public int compare(Map.Entry<MsgChannel, Integer> o1,Map.Entry<MsgChannel, Integer> o2) {
                return (o1.getValue()-o2.getValue()); 
            } 
        }); 
    }
   
   
    public static void main(String[] args) {
        long startTime =  System.currentTimeMillis();
        int total = 0;
        List<MsgChannel> channels = new ArrayList<MsgChannel>();
        int channelNum = 5;
        for (int i = 1; i <=channelNum; i++) {
            MsgChannel channel = new MsgChannel();
            channel.setId(String.valueOf(i));
            channel.setName("第"+i+"个");
            channel.setSignName("hello"+i);
            channel.setParamMap(new HashMap<String,String>(i));
            channel.setPriority( new Random().nextInt(200));
            channels.add(channel);
        }
        for (MsgChannel channel: channels) {
            total +=channel.getPriority();
            System.out.println("channelid: "+channel.getId()+" 权值: "+channel.getPriority());
        }
      
        int loopnum = 1000;
        Map<MsgChannel,Integer> hitmap1 = new HashMap<MsgChannel,Integer>();
        Map<MsgChannel,Integer> hitmap2 = new HashMap<MsgChannel,Integer>();
        Map<MsgChannel,Integer> hitmap3 = new HashMap<MsgChannel,Integer>();
        Map<MsgChannel,Integer> hitmap4 = new HashMap<MsgChannel,Integer>();
        long start1Time = System.currentTimeMillis();
        for (int i = 0; i < loopnum; i++) {
            MsgChannel channel1 = getSpecialChannel(channels);
            if(null!=hitmap1.get(channel1)){
                int num = hitmap1.get(channel1);
                num =num+1;
                hitmap1.put(channel1, num);
            }else{
                int num =1;
                hitmap1.put(channel1, num);
            }
        }
        System.out.println("第一个方法耗时:"+(System.currentTimeMillis()-start1Time)+"毫秒");
        long start2Time = System.currentTimeMillis();
        for (int i = 0; i < loopnum; i++) {
        MsgChannel channel2 = getLuckyChannel(channels);
        if(null!=hitmap2.get(channel2)){
            int num = hitmap2.get(channel2);
            num =num+1;
            hitmap2.put(channel2, num);
        }else{
            int num =1;
            hitmap2.put(channel2, num);
        }
        }
        System.out.println("第二个方法耗时:"+(System.currentTimeMillis()-start2Time)+"毫秒");
        long start3Time = System.currentTimeMillis();
        for (int i = 0; i < loopnum; i++) {
        MsgChannel channel3 = getLuckChannel(channels);
        if(null!=hitmap3.get(channel3)){
            int num = hitmap3.get(channel3);
            num =num+1;
            hitmap3.put(channel3, num);
        }else{
            int num =1;
            hitmap3.put(channel3, num);
        }
        }
        System.out.println("第三个方法耗时:"+(System.currentTimeMillis()-start3Time)+"毫秒");
        long start4Time = System.currentTimeMillis();
        for (int i = 0; i < loopnum; i++) {
            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        MsgChannel channel4 = getTimeLuckChannel(channels);
        if(null!=hitmap4.get(channel4)){
            int num = hitmap4.get(channel4);
            num =num+1;
            hitmap4.put(channel4, num);
        }else{
            int num =1;
            hitmap4.put(channel4, num);
        }
        }
        System.out.println("第四个方法耗时:"+(System.currentTimeMillis()-start4Time)+"毫秒");
       
           
           
        sortMap(hitmap1);
        sortMap(hitmap2);
        sortMap(hitmap3);
        sortMap(hitmap4);
        long endTime =  System.currentTimeMillis();
        System.out.println("总循环次数"+loopnum+" 总共耗时："+(endTime-startTime)+"毫秒");
        System.out.println("总权值数目:"+total);
      
        for (MsgChannel channel: channels) {
            System.out.println("channelid: "+channel.getId()+" 算术平均几率: "+devideNum(channel.getPriority()*100,total)+"% 权值: "+channel.getPriority());
        }
        for (MsgChannel channel:hitmap1.keySet()) {
            if(null!=channel&&null!=hitmap3.get(channel)){
            System.out.println("第一个方法： channelid: "+channel.getId()+" 几率: "+devideNum(hitmap1.get(channel)*100,loopnum)+"% 权值: "+channel.getPriority());
            }
        }
        for (MsgChannel channel:hitmap2.keySet()) {
            if(null!=channel&&null!=hitmap3.get(channel)){
            System.out.println("第二个方法： channelid: "+channel.getId()+" 几率: "+devideNum(hitmap2.get(channel)*100,loopnum)+"% 权值: "+channel.getPriority());
            }
        }
        for (MsgChannel channel:hitmap3.keySet()) {
            if(null!=channel&&null!=hitmap3.get(channel)){
            System.out.println("第三个方法： channelid: "+channel.getId()+" 几率: "+devideNum(hitmap3.get(channel)*100,loopnum)+"% 权值: "+channel.getPriority());
            }
        }
        for (MsgChannel channel:hitmap4.keySet()) {
            if(null!=channel&&null!=hitmap4.get(channel)){
                System.out.println("第四个方法： channelid: "+channel.getId()+" 几率: "+devideNum(hitmap4.get(channel)*100,loopnum)+"% 权值: "+channel.getPriority());
            }
        }
       
    }
   
  
}