Modèle de codage pour un pourcentage aléatoire de twigment?

EDIT: Voir edit at end pour une solution plus élégante. Je vais laisser ça cependant.

Vous pouvez utiliser une NavigableMap pour stocker ces méthodes mappées à leurs pourcentages.

 NavigableMap runnables = new TreeMap<>(); runnables.put(0.3, this::30PercentMethod); runnables.put(1.0, this::70PercentMethod); public static void runRandomly(Map runnables) { double percentage = Math.random(); for (Map.Entry entry : runnables){ if (entry.getKey() < percentage) { entry.getValue().run(); return; // make sure you only call one method } } throw new RuntimeException("map not filled properly for " + percentage); } // or, because I'm still practicing streams by using them for everything public static void runRandomly(Map runnables) { double percentage = Math.random(); runnables.entrySet().stream() .filter(e -> e.getKey() < percentage) .findFirst().orElseThrow(() -> new RuntimeException("map not filled properly for " + percentage)) .run(); } 

La NavigableMap est sortingée (par exemple, HashMap ne donne aucune garantie sur les entrées) par des clés, vous obtenez donc les entrées classées selon leurs pourcentages. Ceci est pertinent car si vous avez deux éléments (3, r1) , (7, r2) , ils génèrent les entrées suivantes: r1 = 0.3 et r2 = 1.0 et ils doivent être évalués dans cet ordre (par exemple s’ils sont évalués dans l’ordre inverse, le résultat serait toujours r2 ).

En ce qui concerne le fractionnement, il devrait aller quelque chose comme ceci: Avec une classe de Tuple comme ça

 static class Pair { public Pair(X f, Y s) { first = f; second = s; } public final X first; public final Y second; } 

Vous pouvez créer une carte comme celle-ci

 // the parameter contains the (1,m1), (1,m2), (3,m3) pairs private static Map splitToPercentageMap(Collection> runnables) { // this adds all Runnables to lists of same int value, // overall those lists are sorted by that int (so least probable first) double total = 0; Map> byNumber = new TreeMap<>(); for (Pair e : runnables) { total += e.first; List list = byNumber.getOrDefault(e.first, new ArrayList<>()); list.add(e.second); byNumber.put(e.first, list); } Map targetList = new TreeMap<>(); double current = 0; for (Map.Entry> e : byNumber.entrySet()) { for (Runnable r : e.getValue()) { double percentage = (double) e.getKey() / total; current += percentage; targetList.put(current, r); } } return targetList; } 

Et tout cela ajouté à une classe

 class RandomRunner { private List runnables = new ArrayList<>(); public void add(int value, Runnable toRun) { runnables.add(new Pair<>(value, toRun)); } public void remove(Runnable toRemove) { for (Iterator> r = runnables.iterator(); r.hasNext(); ) { if (toRemove == r.next().second) { r.remove(); break; } } } public void runRandomly() { // split list, use code from above } } 

MODIFIER :
En fait, ce qui précède est ce que vous obtenez si vous avez une idée coincée dans votre tête et ne le remettez pas en question correctement. Garder l’interface de la classe RandomRunner , c’est beaucoup plus facile:

 class RandomRunner { List runnables = new ArrayList<>(); public void add(int value, Runnable toRun) { // add the methods as often as their weight indicates. // this should be fine for smaller numbers; // if you get lists with millions of entries, optimize for (int i = 0; i < value; i++) { runnables.add(toRun); } } public void remove(Runnable r) { Iterator myRunnables = runnables.iterator(); while (myRunnables.hasNext()) { if (myRunnables.next() == r) { myRunnables.remove(); } } public void runRandomly() { if (runnables.isEmpty()) return; // roll n-sided die int runIndex = ThreadLocalRandom.current().nextInt(0, runnables.size()); runnables.get(runIndex).run(); } } 

Toutes ces réponses semblent assez compliquées, alors je vais simplement poster l’alternative Keep-it-simple:

 double rnd = Math.random() if((rnd -= 0.6) < 0) 60percentmethod(); else if ((rnd -= 0.3) < 0) 30percentmethod(); else 10percentmethod(); 

N'a pas besoin de changer d'autres lignes et on peut très facilement voir ce qui se passe, sans chercher dans les classes auxiliaires. Un petit inconvénient est qu’il n’impose pas que les pourcentages s’élèvent à 100%.

Je ne sais pas s’il y a un nom commun à cela, mais je pense que j’ai appris cela comme la roue de la fortune à l’université.

Il fonctionne simplement comme vous l’avez décrit: il reçoit une liste de valeurs et de “numéros de fréquence” et l’un est choisi en fonction des probabilités pondérées.

 list = (1,a),(1,b),(2,c),(6,d) total = list.sum() rnd = random(0, total) sum = 0 for i from 0 to list.size(): sum += list[i] if sum >= rnd: return list[i] return list.last() 

La liste peut être un paramètre de fonction si vous souhaitez généraliser cela.

Cela fonctionne également avec les nombres à virgule flottante et les nombres ne doivent pas être normalisés. Si vous normalisez (pour résumer à 1 par exemple), vous pouvez ignorer la partie list.sum() .

MODIFIER:

En raison de la demande, voici une implémentation et un exemple d’utilisation de la compilation Java:

 import java.util.ArrayList; import java.util.Random; public class RandomWheel { private static final class RandomWheelSection { public double weight; public T value; public RandomWheelSection(double weight, T value) { this.weight = weight; this.value = value; } } private ArrayList> sections = new ArrayList<>(); private double totalWeight = 0; private Random random = new Random(); public void addWheelSection(double weight, T value) { sections.add(new RandomWheelSection(weight, value)); totalWeight += weight; } public T draw() { double rnd = totalWeight * random.nextDouble(); double sum = 0; for (int i = 0; i < sections.size(); i++) { sum += sections.get(i).weight; if (sum >= rnd) return sections.get(i).value; } return sections.get(sections.size() - 1).value; } public static void main(Ssortingng[] args) { RandomWheel wheel = new RandomWheel(); wheel.addWheelSection(1, "a"); wheel.addWheelSection(1, "b"); wheel.addWheelSection(2, "c"); wheel.addWheelSection(6, "d"); for (int i = 0; i < 100; i++) System.out.print(wheel.draw()); } } 

Bien que la réponse sélectionnée fonctionne, elle est malheureusement asymptotiquement lente pour votre cas d’utilisation. Au lieu de cela, vous pouvez utiliser quelque chose appelé Alias ​​Sampling . L’échantillonnage par alias (ou méthode par alias) est une technique utilisée pour la sélection d’éléments avec une dissortingbution pondérée. Si le poids de choisir ces éléments ne change pas, vous pouvez faire une sélection dans le temps O (1)! . Si ce n’est pas le cas, vous pouvez toujours obtenir le temps O (1) amorti si le rapport entre le nombre de sélections effectuées et les modifications apscopes à la table d’alias (modification des poids) est élevé. La réponse actuellement sélectionnée suggère un algorithme O (N), la meilleure chose suivante est O (log (N)) étant donné les probabilités sortingées et la recherche binary , mais rien ne va battre le temps O (1) que j’ai suggéré.

Ce site fournit une bonne vue d’ensemble de la méthode Alias ​​qui est principalement agnostique en termes de langage. Essentiellement, vous créez un tableau où chaque entrée représente le résultat de deux probabilités. Il y a un seul seuil pour chaque entrée de la table, en dessous du seuil, vous obtenez une valeur, au-dessus vous obtenez une autre valeur. Vous répartissez des probabilités plus grandes sur plusieurs valeurs de tableau afin de créer un graphique de probabilité avec une zone de un pour toutes les probabilités combinées.

Disons que vous avez les probabilités A, B, C et D, qui ont respectivement les valeurs 0.1, 0.1, 0.1 et 0.7. La méthode Alias ​​étendrait la probabilité de 0,7 à tous les autres. Un index correspondrait à chaque probabilité, où vous auriez les valeurs 0,1 et 0,15 pour ABC et 0,25 pour l’indice D. Avec cela, vous normalisez chaque probabilité de sorte que vous vous retrouviez avec 0.4 chance d’obtenir A et 0.6 chance d’obtenir D dans l’index de A (0.1 / (0.1 + 0.15) et 0.15 / (0.1 + 0.15) respectivement) ainsi que B et C indice, et 100% de chances d’obtenir D dans l’indice de D (0,25 / 0,25 est 1).

Avec un PRNG (Math.Random ()) uniforme et non biaisé pour l’indexation, vous avez la même probabilité de choisir chaque index, mais vous effectuez également un retournement par index qui fournit la probabilité pondérée. Vous avez 25% de chances d’atterrir sur le slot A ou D, mais vous avez seulement 40% de chance de choisir A, et 60% de D. 40 * .25 = 0,1, notre probabilité initiale, et si vous Additionnez toutes les probabilités de D parsemées des autres indices, vous obtiendrez à nouveau 0,70.

Donc, pour faire une sélection aléatoire, il vous suffit de générer un index aléatoire de 0 à N, puis de faire un retournement de pièces, peu importe le nombre d’éléments que vous ajoutez, le coût est très rapide et constant. Faire en sorte qu’une table d’alias ne prenne pas autant de lignes de code non plus, ma version python prend 80 lignes, y compris les instructions d’importation et les sauts de ligne, et la version présentée dans l’article Pandas est similaire (et c’est C ++)

Pour votre implémentation Java, vous pouvez mapper entre les probabilités et les index de liste de tableaux avec vos fonctions que vous devez exécuter, en créant un tableau de fonctions qui s’exécutent à chaque index. Vous pouvez également utiliser des objects de fonction pour passer des parameters à exécuter.

 ArrayList<(YourFunctionObject)> function_list; // add functions AliasSampler aliassampler = new AliasSampler(listOfProbabilities); // somewhere later with some type T and some parameter values. int index = aliassampler.sampleIndex(); T result = function_list[index].apply(parameters); 

MODIFIER:

J’ai créé une version en Java de la méthode AliasSampler, en utilisant des classes, cela utilise la méthode des index et devrait pouvoir être utilisée comme ci-dessus.

 import java.util.ArrayList; import java.util.Collections; import java.util.Random; public class AliasSampler { private ArrayList binaryProbabilityArray; private ArrayList aliasIndexList; AliasSampler(ArrayList probabilities){ // java 8 needed here assert(DoubleStream.of(probabilities).sum() == 1.0); int n = probabilities.size(); // probabilityArray is the list of probabilities, this is the incoming probabilities scaled // by the number of probabilities. This allows us to figure out which probabilities need to be spread // to others since they are too large, ie [0.1 0.1 0.1 0.7] = [0.4 0.4 0.4 2.80] ArrayList probabilityArray; for(Double probability : probabilities){ probabilityArray.add(probability); } binaryProbabilityArray = new ArrayList(Collections.nCopies(n, 0.0)); aliasIndexList = new ArrayList(Collections.nCopies(n, 0)); ArrayList lessThanOneIndexList = new ArrayList(); ArrayList greaterThanOneIndexList = new ArrayList(); for(int index = 0; index < probabilityArray.size(); index++){ double probability = probabilityArray.get(index); if(probability < 1.0){ lessThanOneIndexList.add(index); } else{ greaterThanOneIndexList.add(index); } } // while we still have indices to check for in each list, we attempt to spread the probability of those larger // what this ends up doing in our first example is taking greater than one elements (2.80) and removing 0.6, // and spreading it to different indices, so (((2.80 - 0.6) - 0.6) - 0.6) will equal 1.0, and the rest will // be 0.4 + 0.6 = 1.0 as well. while(lessThanOneIndexList.size() != 0 && greaterThanOneIndexList.size() != 0){ //https://stackoverflow.com/questions/16987727/removing-last-object-of-arraylist-in-java // last element removal is equivalent to pop, java does this in constant time int lessThanOneIndex = lessThanOneIndexList.remove(lessThanOneIndexList.size() - 1); int greaterThanOneIndex = greaterThanOneIndexList.remove(greaterThanOneIndexList.size() - 1); double probabilityLessThanOne = probabilityArray.get(lessThanOneIndex); binaryProbabilityArray.set(lessThanOneIndex, probabilityLessThanOne); aliasIndexList.set(lessThanOneIndex, greaterThanOneIndex); probabilityArray.set(greaterThanOneIndex, probabilityArray.get(greaterThanOneIndex) + probabilityLessThanOne - 1); if(probabilityArray.get(greaterThanOneIndex) < 1){ lessThanOneIndexList.add(greaterThanOneIndex); } else{ greaterThanOneIndexList.add(greaterThanOneIndex); } } //if there are any probabilities left in either index list, they can't be spread across the other //indicies, so they are set with probability 1.0. They still have the probabilities they should at this step, it works out mathematically. while(greaterThanOneIndexList.size() != 0){ int greaterThanOneIndex = greaterThanOneIndexList.remove(greaterThanOneIndexList.size() - 1); binaryProbabilityArray.set(greaterThanOneIndex, 1.0); } while(lessThanOneIndexList.size() != 0){ int lessThanOneIndex = lessThanOneIndexList.remove(lessThanOneIndexList.size() - 1); binaryProbabilityArray.set(lessThanOneIndex, 1.0); } } public int sampleIndex(){ int index = new Random().nextInt(binaryProbabilityArray.size()); double r = Math.random(); if( r < binaryProbabilityArray.get(index)){ return index; } else{ return aliasIndexList.get(index); } } } 

Vous pouvez calculer la probabilité cumulée pour chaque classe, choisir un nombre aléatoire parmi [0; 1) et voir où ce nombre tombe.

 class WeightedRandomPicker { private static Random random = new Random(); public static int choose(double[] probabilties) { double randomVal = random.nextDouble(); double cumulativeProbability = 0; for (int i = 0; i < probabilties.length; ++i) { cumulativeProbability += probabilties[i]; if (randomVal < cumulativeProbability) { return i; } } return probabilties.length - 1; // to account for numerical errors } public static void main (String[] args) { double[] probabilties = new double[]{0.1, 0.1, 0.2, 0.6}; // the final value is optional for (int i = 0; i < 20; ++i) { System.out.printf("%d\n", choose(probabilties)); } } } 

Ce qui suit est un peu comme @daniu, mais utilise les méthodes fournies par TreeMap :

 private final NavigableMap map = new TreeMap<>(); { map.put(0.3d, this::branch30Percent); map.put(1.0d, this::branch70Percent); } private final SecureRandom random = new SecureRandom(); private void branch30Percent() {} private void branch70Percent() {} public void runRandomly() { final Runnable value = map.tailMap(random.nextDouble(), true).firstEntry().getValue(); value.run(); } 

De cette façon, il n’est pas nécessaire d’itérer l’intégralité de la carte jusqu’à ce que l’entrée correspondante soit trouvée, mais les capacités de TreeSet pour trouver une entrée avec une clé comparant spécifiquement à une autre clé sont utilisées. Cela ne fera toutefois une différence que si le nombre d’entrées dans la carte est grand. Cependant, il enregistre quelques lignes de code.

Je ferais quelque chose comme ça:

 class RandomMethod { private final Runnable method; private final int probability; RandomMethod(Runnable method, int probability){ this.method = method; this.probability = probability; } public int getProbability() { return probability; } public void run() { method.run(); } } class MethodChooser { private final List methods; private final int total; MethodChooser(final List methods) { this.methods = methods; this.total = methods.stream().collect( Collectors.summingInt(RandomMethod::getProbability) ); } public void chooseMethod() { final Random random = new Random(); final int choice = random.nextInt(total); int count = 0; for (final RandomMethod method : methods) { count += method.getProbability(); if (choice < count) { method.run(); return; } } } } 

Exemple d'utilisation:

 MethodChooser chooser = new MethodChooser(Arrays.asList( new RandomMethod(Blah::aaa, 1), new RandomMethod(Blah::bbb, 3), new RandomMethod(Blah::ccc, 1) )); IntStream.range(0, 100).forEach( i -> chooser.chooseMethod() ); 

Exécutez-le ici .