별칭 방법의 OpenSource 구현 [폐쇄
-
02-07-2019 - |
문제
나는 현재 프로젝트를하고 있으며 코드 재사용을 위해 항목에 대한 확률 론적 수락/거부를 수행 할 수있는 라이브러리를 찾았습니다.
즉, 세 사람 (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) 여기에 설명 된 방법은 어떻게 설명했는지 설명했지만 준비된 구현이 있는지 확인하고 싶었으므로 글을 쓰지 않아도됩니다.
해결책
이런 일이 그렇게 될까요? 모든 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;
}
편집 : 나는 이것을 실제로 테스트하지 않았습니다. 내 요점은 당신이 묘사 한 기능이 그다지 복잡하지 않다는 것입니다 (내가 당신이 올바르게 의미하는 바를 이해한다면),이를 해결하기 위해 라이브러리를 다운로드 할 필요는 없습니다.
다른 팁
루비 구현은 다음과 같습니다. https://github.com/cantino/walker_method
방금 위의 방법을 테스트했습니다. 완벽하지는 않지만 내 목적을 위해 충분해야합니다. (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