Je veux choisir un élément au hasard dans un ensemble, mais la possibilité de choisir un article doit être proportionnelle au poids associé
Exemple d’entrées:
item weight ---- ------ sword of misery 10 shield of happy 5 potion of dying 6 sortingple-edged sword 1
Donc, si j’ai 4 objects possibles, la chance d’obtenir un object sans poids serait de 1 sur 4.
Dans ce cas, un utilisateur devrait être 10 fois plus susceptible d’avoir l’épée de la misère que l’épée à trois tranchants.
Comment puis-je faire une sélection aléatoire pondérée en Java?
J’utiliserais une NavigableMap
public class RandomCollection { private final NavigableMap map = new TreeMap(); private final Random random; private double total = 0; public RandomCollection() { this(new Random()); } public RandomCollection(Random random) { this.random = random; } public RandomCollection 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(); } }
Disons que j'ai une liste d'animaux chien, chat, cheval avec des probabilités de 40%, 35%, 25% respectivement
RandomCollection rc = new RandomCollection<>() .add(40, "dog").add(35, "cat").add(25, "horse"); for (int i = 0; i < 10; i++) { System.out.println(rc.next()); }
Vous ne trouverez pas de cadre pour ce type de problème, car la fonctionnalité demandée n’est rien de plus qu’une simple fonction. Faites quelque chose comme ça:
interface Item { double getWeight(); } class RandomItemChooser { public Item chooseOnWeight(List- 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."); } }
Il y a maintenant une classe pour cela dans Apache Commons: EnumeratedDissortingbution
Item selectedItem = new EnumeratedDissortingbution(itemWeights).sample();
où itemWeights
est un List
, comme (en supposant que l’interface Item dans la réponse d’Arne):
List> itemWeights = Collections.newArrayList(); for (Item i : itemSet) { itemWeights.add(new Pair(i, i.getWeight())); }
ou en Java 8:
itemSet.stream().map(i -> new Pair(i, i.getWeight())).collect(toList());
Remarque: la Pair
doit être org.apache.commons.math3.util.Pair
et non org.apache.commons.lang3.tuple.Pair
.
Si vous lancez beaucoup de fois (comme dans un jeu), vous devriez utiliser une méthode d’alias.
Le code ci-dessous est une implémentation assez longue d’une telle méthode, en effet. Mais c’est à cause de la partie d’initialisation. La récupération des éléments est très rapide (voir les méthodes next
et applyAsInt
qu’ils ne bouclent pas).
Set- items = ... ; ToDoubleFunction
- weighter = ... ; Random random = new Random(); RandomSelector
selector = RandomSelector.weighted(items, weighter); Item drop = selector.next(random);
Cette implémentation:
Random
dans chaque thread pour des performances maximales, utilisez ThreadLocalRandom
?); En tout cas, voici le code. (Notez que je maintiens une version à jour de cette classe .)
import static java.util.Objects.requireNonNull; import java.util.*; import java.util.function.*; public final class RandomSelector { public static RandomSelector weighted(Set 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]; // Resortingeve 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 selection; private RandomSelector(T[] elements, ToIntFunction selection) { this.elements = elements; this.selection = selection; } public T next(Random random) { return elements[selection.applyAsInt(random)]; } private static class RandomWeightedSelection implements ToIntFunction { // 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]; } } } }
Si vous devez supprimer des éléments après avoir choisi, vous pouvez utiliser une autre solution. Ajouter tous les éléments dans un ‘LinkedList’, chaque élément doit être ajouté autant de fois que nécessaire, puis utilisez Collections.shuffle()
qui, selon JavaDoc
Permute aléatoirement la liste spécifiée en utilisant une source d’aléa par défaut. Toutes les permutations se produisent avec une probabilité approximativement égale.
Enfin, obtenez et supprimez des éléments en utilisant pop()
ou removeFirst()
Map map = new HashMap() {{ put("Five", 5); put("Four", 4); put("Three", 3); put("Two", 2); put("One", 1); }}; LinkedList list = new LinkedList<>(); for (Map.Entry 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()); }
public class RandomCollection { private final NavigableMap map = new TreeMap(); 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(); } }