별칭 방법의 OpenSource 구현 [폐쇄

Question

나는 현재 프로젝트를하고 있으며 코드 재사용을 위해 항목에 대한 확률 론적 수락/거부를 수행 할 수있는 라이브러리를 찾았습니다.

즉, 세 사람 (A, BC)이 있으며, 각각은 항목을 얻을 확률이 p {i}를 가지고 있으며, 여기서 p {a}는 a의 확률을 나타냅니다. 이러한 확률은 실행 시간에 계산되며 하드 코딩 할 수 없습니다.

내가하고 싶었던 것은 항목의 경우 임의 숫자 하나를 생성하고 그 항목을 얻을 확률에 따라 해당 항목을 얻는 사람을 계산하는 것입니다. 별칭 방법 (http://books.google.com/books?pg=pa133&dq=Alias+Method+Walker&ei=D4ORR8NCFYUWTGOSLPVE&SIG=TJETHBUA4ODBGJMJYF4DAF1AKF4&ID=ERSDBDCYOIC&outputml) 여기에 설명 된 방법은 어떻게 설명했는지 설명했지만 준비된 구현이 있는지 확인하고 싶었으므로 글을 쓰지 않아도됩니다.

Answer 1

이런 일이 그렇게 될까요? 모든 p {i} 's를 배열에 넣으면 함수는 항목을받는 사람에게 인덱스를 반환합니다. 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

루비 구현은 다음과 같습니다. https://github.com/cantino/walker_method

Answer 3

방금 위의 방법을 테스트했습니다. 완벽하지는 않지만 내 목적을 위해 충분해야합니다. (Groovy의 코드, 단위 테스트에 붙여 넣기 ...)

    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