Реализация метода псевдонима с открытым исходным кодом
В данный момент я работаю над проектом, и в интересах повторного использования кода я искал библиотеку, которая может выполнять некоторые вероятностные приемы / отклонения элемента:
т.е. есть три человека (a, b c), и каждый из них имеет вероятность P {i} получить предмет, где p {a} обозначает вероятность a. Эти вероятности рассчитываются во время выполнения и не могут быть жестко запрограммированы.
Я хотел сгенерировать одно случайное число (для элемента) и вычислить, кто получит этот элемент, исходя из вероятности его получения. Метод псевдонима (http://books.google.com/books?pg=PA133&dq=alias+method+walker&ei=D4ORR8ncFYuWtgOslpVE&sig=TjEThBUa4odbGJmjyF4daF1AKF4&id=ERSSDBDcYOIC&output=html), описанный здесь, объяснил, как это сделать, но я хотел посмотреть, есть ли готовая реализация, чтобы мне не пришлось ее писать.
Ответы 3
Что-нибудь подобное могло бы сделать? Поместите все 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;
}
Обновлено: Я действительно не тестировал это. Я хотел сказать, что описанная вами функция не очень сложна (если я правильно понял, что вы имели в виду), и вам не нужно загружать библиотеку для решения этой проблемы.
Я только что проверил описанный выше метод - он не идеален, но, полагаю, для моих целей этого должно быть достаточно. (код в 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
Вот реализация Ruby: https://github.com/cantino/walker_method
Для записи, это не метод псевдонима. См. stackoverflow.com/a/9958717/1913277 для реализации C#, которая может быть легко перенесена на Java.