Implémentation Opensource de la méthode Alias ??[fermé]
-
02-07-2019 - |
Question
Je suis en train de réaliser un projet en ce moment et, dans l'intérêt de la réutilisation du code, je suis allé à la recherche d'une bibliothèque capable d'exécuter une acceptation / rejet probabiliste d'un élément:
i.e., il y a trois personnes (a, b c) et chacune d’entre elles a une probabilité P {i} d’obtenir un élément, où p {a} désigne la probabilité de a. Ces probabilités sont calculées au moment de l'exécution et ne peuvent pas être codées en dur.
Ce que je voulais faire est de générer un nombre aléatoire (pour un élément) et de calculer qui obtiendra cet élément en fonction de sa probabilité de l'obtenir. La méthode dite des alias books.google.com/books?pg=PA133&dq=alias+method+walker&ei=D4ORR8ncFYuWtgOslpVE&sig=TjEThBUa4odbGJmjyF4daF1AKF4& s'il y a une implémentation prête à l'emploi, je n'aurais donc pas à l'écrire.
La solution
Quelque chose comme ça ferait-il? Mettez tous les p {i} dans le tableau, la fonction retournera un index à la personne qui récupère l'élément. S'exécute en 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;
}
EDIT: Je n'ai pas vraiment testé cela. Mon argument était que la fonction que vous avez décrite n’était pas très compliquée (si j’avais bien compris ce que vous vouliez dire) et que vous n’auriez pas besoin de télécharger une bibliothèque pour résoudre ce problème.
Autres conseils
Voici une implémentation de Ruby: https://github.com/cantino/walker_method
Je viens de tester la méthode ci-dessus - ce n'est pas parfait, mais je suppose que pour mon propos, cela devrait suffire. (code en groovy, collé dans un test unitaire ...)
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