Modèle de codage pour le pourcentage de branchement aléatoire?

Question

Donc, disons que nous avons un bloc de code que nous voulons exécuter 70% de fois et un autre 30% de fois.

if(Math.random() < 0.7)
    70percentmethod();
else
    30percentmethod();

Assez Simple. Mais que faire si nous voulons qu'elle soit facilement extensible à-dire 30%/60%/10%, etc.? Ici, il serait nécessaire d'ajouter et de modifier tous les si des instructions sur le changement qui n'est pas vraiment d'une grande utilité, lent et induisant en erreur.

Jusqu'à présent, j'ai trouvé les commutateurs de grande taille pour être décemment utile pour ce cas d'utilisation, par exemple:

switch(rand(0, 10)){
    case 0:
    case 1:
    case 2:
    case 3:
    case 4:
    case 5:
    case 6:
    case 7:70percentmethod();break;
    case 8:
    case 9:
    case 10:30percentmethod();break;
}

Ce qui peut être très facilement modifié pour:

switch(rand(0, 10)){
    case 0:10percentmethod();break;
    case 1:
    case 2:
    case 3:
    case 4:
    case 5:
    case 6:
    case 7:60percentmethod();break;
    case 8:
    case 9:
    case 10:30percentmethod();break;
}

Mais ces derniers ont leur des inconvénients, être encombrant et split sur une quantité prédéterminée de divisions.

Quelque chose d'idéal serait basée sur une "fréquence" système je suppose que, comme suit:

(1,a),(1,b),(2,c) -> 25% a, 25% b, 50% c

alors si vous avez ajouté un autre:

(1,a),(1,b),(2,c),(6,d) -> 10% a, 10% b, 20% c, 60% d

Donc simplement à additionner les nombres, ce qui rend la somme égale à 100% et puis la diviser.

Je suppose qu'il ne serait pas beaucoup de peine à faire un gestionnaire pour elle avec une ambiance hashmap ou quelque chose, mais je me demandais si il y a quelques établie/pattern ou lambda pour elle avant de m'en aller tous les spaghetti sur cette.

Answer 1

EDIT: Voir modifier à la fin pour une solution plus élégante. Je vais laisser cette tâche à bien.

Vous pouvez utiliser un NavigableMap pour stocker ces méthodes assignés à leurs pourcentages.

NavigableMap<Double, Runnable> runnables = new TreeMap<>();

runnables.put(0.3, this::30PercentMethod);
runnables.put(1.0, this::70PercentMethod);

public static void runRandomly(Map<Double, Runnable> runnables) {
    double percentage = Math.random();
    for (Map.Entry<Double, Runnable> 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<Double, Runnable> runnables) {
    double percentage = Math.random();
    runnables.entrySet().stream()
        .filter(e -> e.getKey() < percentage)
        .findFirst().orElseThrow(() -> 
                new RuntimeException("map not filled properly for " + percentage))
        .run();
}

L' NavigableMap est trié (par exemple, HashMap donne aucune garantie des entrées) par touches, de sorte que vous obtenez les entrées commandées par leurs pourcentages. Cela est pertinent, car si vous avez deux éléments (3,r1),(7,r2), il en résulte dans les entrées suivantes: r1 = 0.3 et r2 = 1.0 et ils ont besoin d'être évaluées dans cet ordre (par exemple, si elles sont évaluées dans l'ordre inverse, le résultat serait toujours être r2).

Comme pour la séparation, il faut aller quelque chose comme ceci: Avec un Tuple de la classe comme ceci

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

    public final X first;
    public final Y second;
}

Vous pouvez créer une carte

// the parameter contains the (1,m1), (1,m2), (3,m3) pairs
private static Map<Double,Runnable> splitToPercentageMap(Collection<Pair<Integer,Runnable>> 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<Integer,List<Runnable>> byNumber = new TreeMap<>();
    for (Pair<Integer,Runnable> e : runnables)
    {
        total += e.first;
        List<Runnable> list = byNumber.getOrDefault(e.first, new ArrayList<>());
        list.add(e.second);
        byNumber.put(e.first, list);
    }

    Map<Double,Runnable> targetList = new TreeMap<>();
    double current = 0;
    for (Map.Entry<Integer,List<Runnable>> 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<Integer, Runnable> runnables = new ArrayList<>();
    public void add(int value, Runnable toRun) {
        runnables.add(new Pair<>(value, toRun));
    }
    public void remove(Runnable toRemove) {
        for (Iterator<Pair<Integer, Runnable>> r = runnables.iterator();
            r.hasNext(); ) {
            if (toRemove == r.next().second) {
               r.remove();
               break;
            }
        }
    }
    public void runRandomly() {
        // split list, use code from above
    }
}

EDIT :
En fait, le ci-dessus est ce que vous obtenez si vous avez une idée coincé dans votre tête et ne pas la remettre en question correctement. En gardant l' RandomRunner interface de classe, c'est beaucoup plus facile:

class RandomRunner {
    List<Runnable> 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<Runnable> 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();
    }
}

Answer 2

Toutes ces réponses semblent assez compliquées, je vais donc 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();
 

Il n'est pas nécessaire de changer d'autres lignes et on peut facilement voir ce qui se passe, sans fouiller dans les classes auxiliaires. Un petit inconvénient est qu'il n'impose pas que les pourcentages totalisent 100%.

Answer 3

Je ne suis pas sûr qu'il y en est un nom commun, mais je pense que j'ai appris ce que la roue de la fortune de retour à l'université.

Essentiellement, il fonctionne exactement comme vous l'avez décrit: Il reçoit une liste de valeurs et "la fréquence des nombres" et l'un est choisi en fonction de la pondération des probabilités.

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 voulez généraliser cette.

Cela fonctionne aussi avec des nombres à virgule flottante et les chiffres n'ont pas à être normalisé. Si vous normalize (à la somme des 1 par exemple), vous pouvez sauter l' list.sum() partie.

EDIT:

En raison de la demande ici est une compilation de java mise en œuvre et d'utilisation exemple:

import java.util.ArrayList;
import java.util.Random;

public class RandomWheel<T>
{
  private static final class RandomWheelSection<T>
  {
    public double weight;
    public T value;

    public RandomWheelSection(double weight, T value)
    {
      this.weight = weight;
      this.value = value;
    }
  }

  private ArrayList<RandomWheelSection<T>> sections = new ArrayList<>();
  private double totalWeight = 0;
  private Random random = new Random();

  public void addWheelSection(double weight, T value)
  {
    sections.add(new RandomWheelSection<T>(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(String[] args)
  {
    RandomWheel<String> wheel = new RandomWheel<String>();
    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());
  }
}

Answer 4

Alors que la réponse sélectionnée fonctionne, il est malheureusement asymptotiquement lent pour votre cas d'utilisation. Au lieu de cela, vous pouvez utiliser quelque chose qui s'appelle l'Alias de l'Échantillonnage. Alias échantillonnage (ou l'alias de la méthode) est une technique utilisée pour la sélection d'éléments avec une distribution pondérée. Si le poids de choisir ces éléments ne permet pas de modifier vous pouvez faire la sélection en O(1) le temps!. Si ce n'est pas le cas, vous pouvez toujours obtenir amorti O(1) fois si le rapport entre le nombre de sélections que vous faites et les modifications que vous apportez à la table d'alias (changement de poids) est élevé. Le courant sélectionné réponse suggère un algorithme O(N), la meilleure chose à faire est de O(log(N)), étant donné triés probabilités et de la recherche binaire, mais rien ne se passe de battre le O(1) fois ai-je suggéré.

Ce site fournit un bon aperçu de l'Alias de la méthode qui est la plupart du temps la langue agnostique. Essentiellement, vous créez un tableau, où chaque entrée représente l'aboutissement de deux probabilités. Il y a un seuil unique pour chaque entrée de la table, en dessous du seuil que vous obtenez une valeur, ci-dessus, vous obtenez une autre valeur. Vous étalez les plus grandes probabilités à travers de multiples valeurs de la table afin de créer une probabilité graphique avec une superficie de un pour toutes les probabilités combinées.

Dire que vous avez l'probabilités A, B, C, et D, qui ont les valeurs de 0.1, 0.1, 0.1 et 0.7 respectivement. Alias méthode de propagation de la probabilité de 0,7 à tous les autres. Un index correspondent à chaque probabilité, où vous auriez l'0,1 et 0,15 pour ABC, et de 0,25 pour D index. Avec cela, vous normaliser chaque probabilité de sorte que vous vous retrouvez avec de 0,4 chance d'obtenir Un et 0,6 chance de se D dans Un index (0.1/(0.1 + 0.15) et 0,15/(0.1 + 0.15) respecively) ainsi que B et C de l'index, et 100% de chance de tomber D au D de l'index (de 0,25/0,25 1).

Compte tenu de l'impartialité uniforme PRNG (Math.Random()) pour l'indexation, vous obtenez une probabilité égale de choix de chaque indice, mais vous pouvez également faire une pièce de monnaie par l'index qui fournit le pondérée de la probabilité. Vous avez 25% de chance de se poser sur l'Un ou D de la fente, mais à l'intérieur que vous n'avez 40% de chance de choisir Un, et 60% de D. .40 * .25 = 0.1, a l'origine, notre probabilité, et si vous additionnez tous D probabilités éparpillés à travers les autres indices, vous obtiendrez .70 à nouveau.

Afin de faire la sélection au hasard, vous avez besoin seulement de générer de façon aléatoire un indice de 0 à N, puis faire un pile ou face, peu importe combien d'articles que vous ajoutez, c'est très rapide et à coût constant. Faire une table d'alias ne prend pas beaucoup de lignes de code, ma version de python prend 80 lignes y compris les déclarations d'importation et les sauts de ligne, et la version présentée dans les Pandas de l'article est de la même taille (et C++)

Pour votre java mise en œuvre pourrait correspondre entre probabilités et tableau liste les indices de vos fonctions, vous devez exécuter, la création d'un éventail de fonctions qui sont exécutées comme vous l'index de chaque, vous pouvez également utiliser la fonction des objets (foncteurs) qui ont une méthode qui vous permet de passer des paramètres à 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);

EDIT:

J'ai créé une version en java de la AliasSampler méthode, à l'aide de classes, il utilise l'exemple de l'indice de la méthode et doit pouvoir être utilisé comme ci-dessus.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class AliasSampler {
    private ArrayList<Double> binaryProbabilityArray;
    private ArrayList<Integer> aliasIndexList;
    AliasSampler(ArrayList<Double> 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<Double> probabilityArray;
        for(Double probability : probabilities){
            probabilityArray.add(probability);
        }
        binaryProbabilityArray = new ArrayList<Double>(Collections.nCopies(n, 0.0));
        aliasIndexList = new ArrayList<Integer>(Collections.nCopies(n, 0));
        ArrayList<Integer> lessThanOneIndexList = new ArrayList<Integer>();
        ArrayList<Integer> greaterThanOneIndexList = new ArrayList<Integer>();
        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);
        }
    }

}

Answer 5

Vous pouvez calculer la probabilité cumulée pour chaque classe en choisissant 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));
        }
    }
}