Java中的随机加权select

我想从一组中select一个随机项目，但select任何项目的机会应该与相关的权重成正比

示例input：

item weight ---- ------ sword of misery 10 shield of happy 5 potion of dying 6 triple-edged sword 1 

所以，如果我有4个可能的项目，没有重量的任何一个项目的机会将是1/4。

在这种情况下，用户比三刃剑更有可能获得悲惨之剑的10倍。

如何在Java中进行加权随机select？

Answer 1

我会使用一个NavigableMap

 public class RandomCollection<E> { private final NavigableMap<Double, E> map = new TreeMap<Double, E>(); private final Random random; private double total = 0; public RandomCollection() { this(new Random()); } public RandomCollection(Random random) { this.random = random; } public RandomCollection<E> add(double weight, E result) { if (weight <= 0) return this; total += weight; map.put(total, result); return this; } public E next() { double value = random.nextDouble() * total; return map.higherEntry(value).getValue(); } } 

说我有一个动物名单，狗，猫，马的概率分别为40％，35％，25％

 RandomCollection<String> rc = new RandomCollection<>() .add(40, "dog").add(35, "cat").add(25, "horse"); for (int i = 0; i < 10; i++) { System.out.println(rc.next()); } 

Answer 2

你不会find这样的问题的框架，因为所要求的function不过是一个简单的function。 做这样的事情：

 interface Item { double getWeight(); } class RandomItemChooser { public Item chooseOnWeight(List<Item> items) { double completeWeight = 0.0; for (Item item : items) completeWeight += item.getWeight(); double r = Math.random() * completeWeight; double countWeight = 0.0; for (Item item : items) { countWeight += item.getWeight(); if (countWeight >= r) return item; } throw new RuntimeException("Should never be shown."); } } 

Answer 3

现在在Apache Commons： EnumeratedDistribution中有一个这样的类

 Item selectedItem = new EnumeratedDistribution(itemWeights).sample(); 

其中itemWeights是一个List<Pair<Item,Double>> ，就像（假设Arne的答案中的Item接口）：

 List<Pair<Item,Double>> itemWeights = Collections.newArrayList(); for (Item i : itemSet) { itemWeights.add(new Pair(i, i.getWeight())); } 

或者在Java 8：

 itemSet.stream().map(i -> new Pair(i, i.getWeight())).collect(toList()); 

注意：这里Pair需要是org.apache.commons.math3.util.Pair ，而不是org.apache.commons.lang3.tuple.Pair 。

Answer 4

使用别名方法

如果你要掷出很多次（如在游戏中），你应该使用别名方法。

下面的代码实际上是相当长的这种别名方法的实现。 但这是因为初始化部分。 元素的检索速度非常快（请参阅next和applyAsInt方法，它们不会循环）。

用法

 Set<Item> items = ... ; ToDoubleFunction<Item> weighter = ... ; Random random = new Random(); RandomSelector<T> selector = RandomSelector.weighted(items, weighter); Item drop = selector.next(random); 

履行

这个实现：

• 使用Java 8 ;
• 被devise得尽可能快 （至less，我试图用微基准来实现）。
• 是完全线程安全的 （在每个线程中保持一个Random以获得最大性能，使用ThreadLocalRandom ？）;
• 获取O（1）中的元素 ，而不像你在互联网上或StackOverflow上find的那样，在O（n）或O（log（n））中运行天真的实现。
• 保持项目与其重量无关 ，因此可以在不同的环境下为项目分配不同的权重。

无论如何，这是代码。 （请注意， 我保持这个类的最新版本 。）

 import static java.util.Objects.requireNonNull; import java.util.*; import java.util.function.*; public final class RandomSelector<T> { public static <T> RandomSelector<T> weighted(Set<T> elements, ToDoubleFunction<? super T> weighter) throws IllegalArgumentException { requireNonNull(elements, "elements must not be null"); requireNonNull(weighter, "weighter must not be null"); if (elements.isEmpty()) { throw new IllegalArgumentException("elements must not be empty"); } // Array is faster than anything. Use that. int size = elements.size(); T[] elementArray = elements.toArray((T[]) new Object[size]); double totalWeight = 0d; double[] discreteProbabilities = new double[size]; // Retrieve the probabilities for (int i = 0; i < size; i++) { double weight = weighter.applyAsDouble(elementArray[i]); if (weight < 0.0d) { throw new IllegalArgumentException("weighter may not return a negative number"); } discreteProbabilities[i] = weight; totalWeight += weight; } if (totalWeight == 0.0d) { throw new IllegalArgumentException("the total weight of elements must be greater than 0"); } // Normalize the probabilities for (int i = 0; i < size; i++) { discreteProbabilities[i] /= totalWeight; } return new RandomSelector<>(elementArray, new RandomWeightedSelection(discreteProbabilities)); } private final T[] elements; private final ToIntFunction<Random> selection; private RandomSelector(T[] elements, ToIntFunction<Random> selection) { this.elements = elements; this.selection = selection; } public T next(Random random) { return elements[selection.applyAsInt(random)]; } private static class RandomWeightedSelection implements ToIntFunction<Random> { // Alias method implementation O(1) // using Vose's algorithm to initialize O(n) private final double[] probabilities; private final int[] alias; RandomWeightedSelection(double[] probabilities) { int size = probabilities.length; double average = 1.0d / size; int[] small = new int[size]; int smallSize = 0; int[] large = new int[size]; int largeSize = 0; // Describe a column as either small (below average) or large (above average). for (int i = 0; i < size; i++) { if (probabilities[i] < average) { small[smallSize++] = i; } else { large[largeSize++] = i; } } // For each column, saturate a small probability to average with a large probability. while (largeSize != 0 && smallSize != 0) { int less = small[--smallSize]; int more = large[--largeSize]; probabilities[less] = probabilities[less] * size; alias[less] = more; probabilities[more] += probabilities[less] - average; if (probabilities[more] < average) { small[smallSize++] = more; } else { large[largeSize++] = more; } } // Flush unused columns. while (smallSize != 0) { probabilities[small[--smallSize]] = 1.0d; } while (largeSize != 0) { probabilities[large[--largeSize]] = 1.0d; } } @Override public int applyAsInt(Random random) { // Call random once to decide which column will be used. int column = random.nextInt(probabilities.length); // Call random a second time to decide which will be used: the column or the alias. if (random.nextDouble() < probabilities[column]) { return column; } else { return alias[column]; } } } } 

Answer 5

 public class RandomCollection<E> { private final NavigableMap<Double, E> map = new TreeMap<Double, E>(); private double total = 0; public void add(double weight, E result) { if (weight <= 0 || map.containsValue(result)) return; total += weight; map.put(total, result); } public E next() { double value = ThreadLocalRandom.current().nextDouble() * total; return map.ceilingEntry(value).getValue(); } } 

Answer 6

如果您select后需要删除元素，则可以使用其他解决scheme。 将所有元素添加到“LinkedList”中，每个元素必须添加多less次，然后使用Collections.shuffle() ，根据JavaDoc

随机地使用默认的随机源对指定的列表进行排列。 所有排列发生的可能性几乎相等。

最后，使用pop()或removeFirst()获取和移除元素

 Map<String, Integer> map = new HashMap<String, Integer>() {{ put("Five", 5); put("Four", 4); put("Three", 3); put("Two", 2); put("One", 1); }}; LinkedList<String> list = new LinkedList<>(); for (Map.Entry<String, Integer> entry : map.entrySet()) { for (int i = 0; i < entry.getValue(); i++) { list.add(entry.getKey()); } } Collections.shuffle(list); int size = list.size(); for (int i = 0; i < size; i++) { System.out.println(list.pop()); }