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?

我会使用一个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()); } 

你不会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."); } } 

现在在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

使用别名方法

如果你要掷出很多次(如在游戏中),你应该使用别名方法。

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

用法

 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]; } } } } 
 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(); } } 

如果您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()); }