首页 > 代码库 > 权重随机的实现
权重随机的实现
欢迎关注Github:https://github.com/teaey/
权重随机在项目中经常用到,所以我把它抽象到一个工具类中。
一般实现随机权重有两种方式:
1. 使用一个数组存放权重对应的实际目标,比如A的权重是2,B的权重是3,那么数组长度为5, 数组前两个存放A,后三个存放B。
然后随机一个[0-数据长度)的数字,直接取数组对应下标的值就可以了。
优点:数据结构简单,算法高效,实现简单
缺点:当权重值比较大同时数据又比较多的时候,会浪费内存
2. 使用区间算法,从前到后依次叠加权重,然后随机一个[1-权重和]的数字,再用随机的权重依次减去每个元素的权重,当第一个小于等于0的元素就是我们找元素
这里实现可以借用Arrays的binarySearch方法。
源码可参考Github:源码
贴一下代码:
WeightMeta.java
/** * 建议使用RandomUtil类创建RandomMeta对象 * @author wxf on 14-5-5. */ public class WeightMeta<T> { private final Random ran = new Random(); private final T[] nodes; private final int[] weights; private final int maxW; public WeightMeta(T[] nodes, int[] weights) { this.nodes = nodes; this.weights = weights; this.maxW = weights[weights.length - 1]; } /** * 该方法返回权重随机对象 * @return */ public T random() { int index = Arrays.binarySearch(weights, ran.nextInt(maxW) + 1); if (index < 0) { index = -1 - index; } return nodes[index]; } public T random(int ranInt) { if (ranInt > maxW) { ranInt = maxW; } else if(ranInt < 0){ ranInt = 1; } else { ranInt ++; } int index = Arrays.binarySearch(weights, ranInt); if (index < 0) { index = -1 - index; } return nodes[index]; } @Override public String toString() { StringBuilder l1 = new StringBuilder(); StringBuilder l2 = new StringBuilder("[random]\t"); StringBuilder l3 = new StringBuilder("[node]\t\t"); l1.append(this.getClass().getName()).append(":").append(this.hashCode()).append(":\n").append("[index]\t\t"); for (int i = 0; i < weights.length; i++) { l1.append(i).append("\t"); l2.append(weights[i]).append("\t"); l3.append(nodes[i]).append("\t"); } l1.append("\n"); l2.append("\n"); l3.append("\n"); return l1.append(l2).append(l3).toString(); } }
RandomUtil.java
/** * 随机工具类 * * 使用权重的集合Map构建随机元数据对象 * * 比如: * 我们有3个url地址,他们的权重分别为1,2,3现在我们利用RandomUtil来根据权重随机获取url: * * <p><blockquote><pre> * * map.put(url1, 1); * map.put(url2, 2); * map.put(url3, 3); * RandomMeta<String, Integer> md = RandomUtil.buildWeightMeta(map); * String weightRandomUrl = md.random(); * * </pre></blockquote><p> * * @author wxf on 14-5-5. */ public class RandomUtil { public static <T> WeightMeta<T> buildWeightMeta(final Map<T, Integer> weightMap) { final int size = weightMap.size(); Object[] nodes = new Object[size]; int[] weights = new int[size]; int index = 0; int weightAdder = 0; for (Map.Entry<T, Integer> each : weightMap.entrySet()) { nodes[index] = each.getKey(); weights[index++] = (weightAdder = weightAdder + each.getValue()); } return new WeightMeta<T>((T[]) nodes, weights); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。