一个人至少拥有一个梦想,有一个理由去坚强

心若没有栖息的地方,到哪里都是在流浪

加权随机算法----java实现

一、今天碰到一个不是很复杂的随机算法问题,需要根据每个URL的权重,从URL随机选取一个返回给客户端,这里需要使用加权随机算法,常用于抽奖以及资源分配。废话不多说,先上代码

1、这里有一个实体类,实体类的元素分别为需要返回的关键字key  和关键字的权重weight

public class Atom {
  private String key;
  private int weight;
  
  
  public Atom() {
    super();
  }
  
  public Atom(String key, int weight) {
    super();
    this.key = key;
    this.weight = weight;
  }
  public String getKey() {
    return key;
  }
  public void setKey(String key) {
    this.key = key;
  }
  public int getWeight() {
    return weight;
  }
  public void setWeight(int weight) {
    this.weight = weight;
  }
  
  
}

2、加权随机的算法,核心思想是在0到权重之和的区间,随机选取一个整数,并且判断它位位于哪个权重管辖区间,然后返回该区间对应的唯一的元素即可

public class WeightedRandom {

    /** 
     * 获取加权随机对象 
     * @param atomList 
     * @return Atom 
     */  
    public static Atom getWeightedRandomAtom(ArrayList<Atom> atomList){  
        if(atomList.isEmpty()){  
            return null;  
        }  
        int weightSum = 0;//总权值  
        for(Atom atom : atomList){  
            weightSum += atom.getWeight();  
        }  
        //获取总权值之间任意一随机数  
        int random = new Random().nextInt(weightSum);  //random in [0, weightSum)   
        //{.},{..},{...},{....}...根据权值概率区间,获得加权随机对象  
        for(Atom atom : atomList){  
            random -= atom.getWeight();  
            if (random < 0) {  
                return atom;  
            }  
        }  
        return null;  
    }  

3、调用实例

  public String getWeightRandomUrl() 
  { ArrayList<Atom> atomList = new ArrayList<Atom>();
    atomList.add(new Atom("baidu.com", 50));
  atomList.add(new Atom("thinkclover.com", 100));
  atomList.add(new Atom("360.com", 30));
  atomList.add(new Atom("taobao.com", 50));
  atomList.add(new Atom("mi.com", 10));


   Atom atomFinal = WeightedRandom.getWeightedRandomAtom(atomList);  
  
  return atomFinal.getKey();
  }

经过多次测试的结果以后,发现确实是符合概率论的!

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注