Java中的加权随机性

在Java中，给定n个项目，每个项目的权重都是w ，那么如何从集合中select一个随机的项目，并有机会等于w ？

假定每个权重是从0.0到1.0的两倍，并且集合中的权重总计为1. Item.getWeight（）返回项目的权重。

Answer 1

Item[] items = ...; // Compute the total weight of all items together double totalWeight = 0.0d; for (Item i : items) { totalWeight += i.getWeight(); } // Now choose a random item int randomIndex = -1; double random = Math.random() * totalWeight; for (int i = 0; i < items.length; ++i) { random -= items[i].getWeight(); if (random <= 0.0d) { randomIndex = i; break; } } Item myRandomItem = items[randomIndex]; 

Answer 2

TreeMap已经为你做了所有的工作。

创build一个TreeMap。 根据您select的方法创build权重。 添加从0.0开始的权重，同时将最后一个元素的权重添加到运行中的权重计数器中。

即（斯卡拉）：

 var count = 0.0 for { object <- MyObjectList } { //Just any iterator over all objects map.insert(count, object) count += object.weight } 

那么你只需要生成rand = new Random(); num = rand.nextDouble() * count rand = new Random(); num = rand.nextDouble() * count得到一个有效的数字。

 map.to(num).last // Scala map.floorKey(num) // Java 

会给你随机的加权项目。

对于较小数量的桶也是可能的：创build一个数组，即100000个Int，并基于域上的权重分配桶的数量。 然后你创build一个0到100,000-1的随机整数，然后你立即得到桶号。

Answer 3

一个优雅的方法是采样指数分布http://en.wikipedia.org/wiki/Exponential_distribution其中的权重将是分配率（lambda）。; 最后，你只需select最小的采样值。

在Java中，这看起来像这样：

 public static <E> E getWeightedRandom(Map<E, Double> weights, Random random) { E result = null; double bestValue = Double.MAX_VALUE; for (E element : weights.keySet()) { double value = -Math.log(random.nextDouble()) / weights.get(element); if (value < bestValue) { bestValue = value; result = element; } } return result; } 

我不确定这是否比其他方法更有效，但如果执行时间不是问题，那么这是一个很好的解决scheme。

这和使用Java 8和Streams的想法是一样的：

 public static <E> E getWeightedRandomJava8(Stream<Entry<E, Double>> weights, Random random) { return weights .map(e -> new SimpleEntry<E,Double>(e.getKey(),-Math.log(random.nextDouble()) / e.getValue())) .min((e0,e1)-> e0.getValue().compareTo(e1.getValue())) .orElseThrow(IllegalArgumentException::new).getKey(); } 

您可以通过使用.entrySet().stream()进行转换来获取input权重stream。

Answer 4

1. 给项目…（i1，i2，…，in）中的任意sorting…使用权重w1，w2，…，wn。
2. select一个介于0和1之间的随机数（具有足够的粒度，使用任意随机函数和适当的缩放比例）。 调用这个r0。
3. 令j = 1
4. 从你的r（j-1）中减去wj得到rj。 如果rj <= 0，则select项目ij。 否则，增加j并重复。

我想我以前就是这样做的……但是可能有更有效的方法来做到这一点。

Answer 5

如果您希望运行时select效率，那么在安装时多花一点时间可能是最好的。 这是一个可能的解决scheme。 它有更多的代码，但保证日志（n）的select。

WeightedItemSelector实现从加权对象集合中select一个随机对象。 select保证在log（n）时间运行。

 public class WeightedItemSelector<T> { private final Random rnd = new Random(); private final TreeMap<Object, Range<T>> ranges = new TreeMap<Object, Range<T>>(); private int rangeSize; // Lowest integer higher than the top of the highest range. public WeightedItemSelector(List<WeightedItem<T>> weightedItems) { int bottom = 0; // Increments by size of non zero range added as ranges grows. for(WeightedItem<T> wi : weightedItems) { int weight = wi.getWeight(); if(weight > 0) { int top = bottom + weight - 1; Range<T> r = new Range<T>(bottom, top, wi); if(ranges.containsKey(r)) { Range<T> other = ranges.get(r); throw new IllegalArgumentException(String.format("Range %s conflicts with range %s", r, other)); } ranges.put(r, r); bottom = top + 1; } } rangeSize = bottom; } public WeightedItem<T> select() { Integer key = rnd.nextInt(rangeSize); Range<T> r = ranges.get(key); if(r == null) return null; return r.weightedItem; } } 

范围实现范围select以利用TreeMapselect。

 class Range<T> implements Comparable<Object>{ final int bottom; final int top; final WeightedItem<T> weightedItem; public Range(int bottom, int top, WeightedItem<T> wi) { this.bottom = bottom; this.top = top; this.weightedItem = wi; } public WeightedItem<T> getWeightedItem() { return weightedItem; } @Override public int compareTo(Object arg0) { if(arg0 instanceof Range<?>) { Range<?> other = (Range<?>) arg0; if(this.bottom > other.top) return 1; if(this.top < other.bottom) return -1; return 0; // overlapping ranges are considered equal. } else if (arg0 instanceof Integer) { Integer other = (Integer) arg0; if(this.bottom > other.intValue()) return 1; if(this.top < other.intValue()) return -1; return 0; } throw new IllegalArgumentException(String.format("Cannot compare Range objects to %s objects.", arg0.getClass().getName())); } /* (non-Javadoc) * @see java.lang.Object#toString() */ @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("{\"_class\": Range {\"bottom\":\"").append(bottom).append("\", \"top\":\"").append(top) .append("\", \"weightedItem\":\"").append(weightedItem).append("}"); return builder.toString(); } } 

WeightedItem简单地封装一个项目来select。

 public class WeightedItem<T>{ private final int weight; private final T item; public WeightedItem(int weight, T item) { this.item = item; this.weight = weight; } public T getItem() { return item; } public int getWeight() { return weight; } /* (non-Javadoc) * @see java.lang.Object#toString() */ @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("{\"_class\": WeightedItem {\"weight\":\"").append(weight).append("\", \"item\":\"") .append(item).append("}"); return builder.toString(); } } 

Answer 6

下面是一个保持比例精度的随机函数：

 public class WeightedRandomizer { private final Random randomizer; public WeightedRandomizer(Random randomizer) { this.randomizer = randomizer; } public IWeighable getRandomWeighable(List<IWeighable> weighables) { double totalWeight = 0.0; long totalSelections = 1; List<IWeighable> openWeighables = new ArrayList<>(); for (IWeighable weighable : weighables) { totalWeight += weighable.getAllocation(); totalSelections += weighable.getNumSelections(); } for(IWeighable weighable : weighables) { double allocation = weighable.getAllocation() / totalWeight; long numSelections = weighable.getNumSelections(); double proportion = (double) numSelections / (double) totalSelections; if(proportion < allocation) { openWeighables.add(weighable); } } IWeighable selection = openWeighables.get(this.randomizer.nextInt(openWeighables.size())); selection.setNumSelections(selection.getNumSelections() + 1); return selection; } } 

Answer 7

使用包含getWeight()方法的Item类（如您的问题）：

 /** * Gets a random-weighted object. * @param items list with weighted items * @return a random item from items with a chance equal to its weight. * @assume total weight == 1 */ public static Item getRandomWeighted(List<Item> items) { double value = Math.random(), weight = 0; for (Item item : items) { weight += item.getWeight(); if (value < weight) return item; } return null; // Never will reach this point if assumption is true } 

使用Map和更通用的方法：

 /** * Gets a random-weighted object. * @param balancedObjects the map with objects and their weights. * @return a random key-object from the map with a chance equal to its weight/totalWeight. * @throws IllegalArgumentException if total weight is not positive. */ public static <E> E getRandomWeighted(Map<E, ? extends Number> balancedObjects) throws IllegalArgumentException { double totalWeight = balancedObjects.values().stream().mapToInt(Number::intValue).sum(); // Java 8 if (totalWeight <= 0) throw new IllegalArgumentException("Total weight must be positive."); double value = Math.random()*totalWeight, weight = 0; for (Entry<E, ? extends Number> e : balancedObjects.entrySet()) { weight += e.getValue().doubleValue(); if (value < weight) return e.getKey(); } return null; // Never will reach this point }