Open-Source-Implementation der Alias-Methode [geschlossen]

Question

Ich mache ein Projekt im Moment, und im Interesse der Wiederverwendung von Code, ging ich für eine Bibliothek suchen, einig probabilistischen akzeptieren ausführen kann / ablehnen ein Element:

d. Gibt es drei Personen (a, b c), und jeder von ihnen eine Wahrscheinlichkeit P hat {i} einen Artikel erhalten, wobei p {a} die Wahrscheinlichkeit a bezeichnet. Diese Wahrscheinlichkeiten werden zur Laufzeit berechnet, und nicht fest einprogrammiert werden können.

Was ich tun wollte, ist eine Zufallszahl zu erzeugen (für ein Element), und berechnet, die das Element auf ihrer Wahrscheinlichkeit, es basiert wird. Die Alias-Methode ( http: // books.google.com/books?pg=PA133&dq=alias+method+walker&ei=D4ORR8ncFYuWtgOslpVE&sig=TjEThBUa4odbGJmjyF4daF1AKF4&id=ERSSDBDcYOIC&output=html ) skizziert hier erklärt, wie, aber ich wollte sehen, ob es eine fertige Implementierung ist so wouldn I ‚t es schreiben auf.

Answer 1

Würde so etwas tun? Setzen Sie alle p {i} s im Array-Funktion einen Index auf die Person zurückkehren, die das Produkt bekommt. Führt in 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: Ich habe nicht wirklich getestet dies. Mein Punkt war, dass die Funktion, die Sie beschrieben ist nicht sehr kompliziert (wenn ich verstehe, was Sie richtig verstanden, das ist), und Sie sollen nicht um eine Bibliothek zu lösen diese herunterladen.

Answer 2

Hier ist eine Ruby-Implementierung: https://github.com/cantino/walker_method

Answer 3

i nur die oben beschriebene Methode getestet heraus - es ist nicht perfekt, aber ich denke, für meine Zwecke, es sollte genug sein. (Code in groovy, in einen Unit-Test eingefügt ...)

    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