開源別名法

Question

我在做一個項目的那一刻，和代碼重用的興趣，我去尋找，可以執行一些概率接受/拒絕的項目庫的執行情況：

即有三個人（a，bc），並且他們每個人都有一個獲得項目的概率P {i}，其中p {a}表示a的概率。這些概率是在運行時計算的，並且不能被硬編碼。

我想要做的是生成一個隨機數（對於一個物品），並根據它們獲取物品的可能性計算誰獲得物品。這裏列出的別名方法（http://books.google.com/books?pg=PA133&dq=alias+method+walker&ei=D4ORR8ncFYuWtgOslpVE&sig=TjEThBUa4odbGJmjyF4daF1AKF4&id=ERSSDBDcYOIC&output=html）解釋瞭如何，但我想看看是否有一個現成的實現，所以我不必寫出來。

Answer 1

會這樣嗎？將所有p {i}放入數組中，函數將返回索引給獲取該項目的人員。在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;  
} 

編輯：我沒有真正測試過這個。我的觀點是，你所描述的功能不是很複雜（如果我明白你的意思是對的，那就是），你不需要下載一個庫來解決這個問題。

Answer 2

我剛剛測試了上面的方法 - 它不完美，但我想我的目的，它應該是足夠的。 （代碼在常規，粘貼到一個單元測試...）

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

這裏是一個Ruby實現：https://github.com/cantino/walker_method