Implémentation Opensource de la méthode Alias ??[fermé]

Question

Je suis en train de réaliser un projet en ce moment et, dans l'intérêt de la réutilisation du code, je suis allé à la recherche d'une bibliothèque capable d'exécuter une acceptation / rejet probabiliste d'un élément:

i.e., il y a trois personnes (a, b c) et chacune d’entre elles a une probabilité P {i} d’obtenir un élément, où p {a} désigne la probabilité de a. Ces probabilités sont calculées au moment de l'exécution et ne peuvent pas être codées en dur.

Ce que je voulais faire est de générer un nombre aléatoire (pour un élément) et de calculer qui obtiendra cet élément en fonction de sa probabilité de l'obtenir. La méthode dite des alias books.google.com/books?pg=PA133&dq=alias+method+walker&ei=D4ORR8ncFYuWtgOslpVE&sig=TjEThBUa4odbGJmjyF4daF1AKF4& s'il y a une implémentation prête à l'emploi, je n'aurais donc pas à l'écrire.

Answer 1

Quelque chose comme ça ferait-il? Mettez tous les p {i} dans le tableau, la fonction retournera un index à la personne qui récupère l'élément. S'exécute en O (n).

public int selectPerson(float[] probabilies, Random r) {
    float t = r.nextFloat();
    float p = 0.0f;

    for (int i = 0; i < probabilies.length; i++) {
        p += probabilies[i];
        if (t < p) {
            return i;
        }
    }

    // We should not end up here if probabilities are normalized properly (sum up to one)
    return probabilies.length - 1;      
}

EDIT: Je n'ai pas vraiment testé cela. Mon argument était que la fonction que vous avez décrite n’était pas très compliquée (si j’avais bien compris ce que vous vouliez dire) et que vous n’auriez pas besoin de télécharger une bibliothèque pour résoudre ce problème.

Answer 2

Voici une implémentation de Ruby: https://github.com/cantino/walker_method

Answer 3

Je viens de tester la méthode ci-dessus - ce n'est pas parfait, mais je suppose que pour mon propos, cela devrait suffire. (code en groovy, collé dans un test unitaire ...)

    void test() {
        for (int i = 0; i < 10; i++) {
            once()
        }
    }
    private def once() {
        def double[] probs = [1 / 11, 2 / 11, 3 / 11, 1 / 11, 2 / 11, 2 / 11]
        def int[] whoCounts = new int[probs.length]
        def Random r = new Random()
        def int who
        int TIMES = 1000000
        for (int i = 0; i < TIMES; i++) {
            who = selectPerson(probs, r.nextDouble())
            whoCounts[who]++
        }
        for (int j = 0; j < probs.length; j++) {
            System.out.printf(" %10f ", (probs[j] - (whoCounts[j] / TIMES)))
        }
        println ""
    }
    public int selectPerson(double[] probabilies, double r) {
        double t = r
        double p = 0.0f;
        for (int i = 0; i < probabilies.length; i++) {
            p += probabilies[i];
            if (t < p) {
                return i;
            }
        }
        return probabilies.length - 1;
    }

outputs: the difference betweenn the probability, and the actual count/total 
obtained over ten 1,000,000 runs:
  -0.000009    0.000027    0.000149   -0.000125    0.000371   -0.000414 
  -0.000212   -0.000346   -0.000396    0.000013    0.000808    0.000132 
   0.000326    0.000231   -0.000113    0.000040   -0.000071   -0.000414 
   0.000236    0.000390   -0.000733   -0.000368    0.000086    0.000388 
  -0.000202   -0.000473   -0.000250    0.000101   -0.000140    0.000963 
   0.000076    0.000487   -0.000106   -0.000044    0.000095   -0.000509 
   0.000295    0.000117   -0.000545   -0.000112   -0.000062    0.000306 
  -0.000584    0.000651    0.000191    0.000280   -0.000358   -0.000181 
  -0.000334   -0.000043    0.000484   -0.000156    0.000420   -0.000372