开源别名法

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