Aléatoire pondéré en Java

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]; 

Une méthode élégante consisterait à échantillonner une dissortingbution exponentielle http://en.wikipedia.org/wiki/Exponential_dissortingbution où les poids correspondront au taux de la dissortingbution (lambda). Enfin, vous sélectionnez simplement la plus petite valeur échantillonnée.

En Java, cela ressemble à ceci:

 public static  E getWeightedRandom(Map 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; } 

Je ne suis pas sûr que ce soit plus efficace que les autres approches, mais si le problème n’est pas lié au temps d’exécution, c’est une solution qui a l’air agréable.

Et c'est la même idée avec Java 8 et Streams:

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

Vous pouvez obtenir le stream de poids d'entrée par exemple à partir d'une carte en le convertissant avec .entrySet().stream() .

TreeMap fait déjà tout le travail pour vous.

Créer une TreeMap. Créez des poids en fonction de votre méthode de choix. Ajoutez les poids en commençant par 0.0 en ajoutant le poids du dernier élément à votre compteur de poids en cours d’exécution.

à savoir (Scala):

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

Ensuite, il vous suffit de générer rand = new Random(); num = rand.nextDouble() * count rand = new Random(); num = rand.nextDouble() * count pour obtenir un nombre valide.

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

vous donnera l'élément pondéré au hasard.

Pour les petites quantités de godets également possibles: Créez un tableau de 100 000 Int et dissortingbuez le numéro du godet en fonction du poids dans les champs. Ensuite, vous créez un nombre entier aléatoire compris entre 0 et 100 000-1 et vous récupérez immédiatement le numéro de compartiment.

Si vous voulez que l’efficacité de la sélection de l’exécution prenne un peu plus de temps sur la configuration, ce serait probablement mieux. Voici une solution possible. Il a plus de code mais garantit la sélection de log (n).

WeightedItemSelector Implémente la sélection d’un object aléatoire à partir d’une collection d’objects pondérés. Il est garanti que la sélection s’exécutera dans le temps log (n).

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

Plage Implémente la sélection de plage pour tirer parti de la sélection TreeMap.

 class Range implements Comparable 

WeightedItem encapsule simplement un élément à sélectionner.

 public class WeightedItem{ 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#toSsortingng() */ @Override public Ssortingng toSsortingng() { SsortingngBuilder builder = new SsortingngBuilder(); builder.append("{\"_class\": WeightedItem {\"weight\":\"").append(weight).append("\", \"item\":\"") .append(item).append("}"); return builder.toSsortingng(); } } 

1. Donnez un ordre arbitraire aux éléments … (i1, i2, …, in) … avec les poids w1, w2, …, wn.
2. Choisissez un nombre aléatoire compris entre 0 et 1 (avec une granularité suffisante, en utilisant une fonction de randomisation et une mise à l’échelle appropriée). Appelez ça r0.
3. Soit j = 1
4. Soustrayez wj de votre r (j-1) pour obtenir rj. Si rj <= 0, vous sélectionnez l'élément ij. Sinon, incrémentez j et répétez.

Je pense que je l’ai déjà fait comme ça … mais il y a probablement des moyens plus efficaces de le faire.

Vous trouverez ci-dessous un randomiseur qui maintient également la précision dans les proportions:

 public class WeightedRandomizer { private final Random randomizer; public WeightedRandomizer(Random randomizer) { this.randomizer = randomizer; } public IWeighable getRandomWeighable(List weighables) { double totalWeight = 0.0; long totalSelections = 1; List 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; } } 

Avec une classe Item qui contient une méthode getWeight() (comme dans votre question):

 /** * 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 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 } 

Avec une Map et une méthode plus générique:

 /** * 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 getRandomWeighted(Map 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 : balancedObjects.entrySet()) { weight += e.getValue().doubleValue(); if (value < weight) return e.getKey(); } return null; // Never will reach this point }