Opensource La mise en œuvre de la méthode Alias ​​

Question

que je fais un projet pour le moment, et dans l'intérêt de la réutilisation de code, je suis à la recherche d'une bibliothèque qui peut effectuer une probabiliste d'acceptation/rejet d'un article:

-à-dire, il y a trois personnes (a, bc), et chacune d'elles a une probabilité P {i} d'obtenir un item, où p {a} indique 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 objet), et calculer qui obtient cet élément en fonction de leur probabilité de l'obtenir. La méthode alias (http://books.google.com/books?pg=PA133&dq=alias+method+walker&ei=D4ORR8ncFYuWtgOslpVE&sig=TjEThBUa4odbGJmjyF4daF1AKF4&id=ERSSDBDcYOIC&output=html) décrite ici expliquait comment, mais je voulais voir s'il y avait une implémentation prête à l'emploi, donc je n'aurais pas à l'écrire.

Answer 1

Est-ce que quelque chose comme ça ferait? Mettez tous les p {i} dans le tableau, la fonction retournera un index à la personne qui obtient l'élément. 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. Ce que je voulais dire, c'est que la fonction que vous avez décrite n'est pas très compliquée (si j'ai bien compris ce que vous vouliez dire), et vous ne devriez pas avoir besoin de télécharger une bibliothèque pour résoudre ce problème.

Answer 2

Je viens de tester la méthode ci-dessus - ce n'est pas parfait, mais je suppose que pour mes fins, cela devrait suffire. (Code 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 

Answer 3

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