Sélection d'une valeur proportionnellement basée sur sa double clé

Question

J'ai une liste de valeurs, avec des doubles entre 0 et 1 qui représentent la probabilité que je pense que c'est utile pour moi. Par exemple, pour obtenir une réponse à une question:

0.5 call your mom 
0.25 go to the library 
0.6 StackOverflow 
0.9 just Google it 

Donc, nous pensons que googler est (environ) deux fois plus susceptibles d'être utiles que demander maman. Lorsque j'essaie de comprendre la prochaine chose à faire, je voudrais que "juste Google" soit retourné deux fois plus souvent que "appelez votre mère".

J'ai cherché des solutions avec peu de succès. La plupart des choses que j'ai trouvées s'appuient sur des clefs entières (comme How to randomly select a key based on its Integer value in a Map with respect to the other values in O(n) time?), que je n'ai pas et que je ne peux pas facilement générer.

Je pense qu'il devrait y avoir un certain type de données Java qui peut le faire pour moi. Aucune suggestion?

Answer 1

Vous pouvez imaginer une solution basée sur l'interface Java NavigableMap, et si vous utilisez l'implémentation TreeMap, vous aurez toujours une complexité O (logn).

Vous pouvez utiliser une des opérations suivantes:

• lowerEntry
• ceilingEntry
• floorEntry
• higherEntry

Maintenant, vous avez juste besoin d'extraire des nombres aléatoires avec la bonne probabilité. Pour que je me réfère à ce poste:

How to generate a random number from specified discrete distribution?

Answer 2

Si je comprends bien, ce que vous cherchez est pondéré au hasard.
Vous devriez additionner tous vos poids, et peut-être normaliser ceci à une valeur entière, ainsi vous serez capable d'utiliser le rand.nextInt comme suggéré par les commentaires.
peut être fait Normalization en multipliant par 100 par exemple, de sorte que vos poids normalisés sont maintenant:
50, 25, 60, 90 - La somme est 225.
Vous devez définir des plages:
0 - 49 est pour " appeler votre maman »
50-74 - est pour « aller à la bibliothèque »

maintenant, vous devez effectuer this.rand.nextInt (somme) - et obtenir une valeur,
et cette valeur doit être mis en correspondance l'une des plages définies.

Answer 3

Si vous garder une trace de ce que la valeur totale des probabilités sont, vous pouvez faire quelque chose comme ceci:

double interval = 100; 
double counter = 0; 
double totalProbabilities = 2.25; 
int randInt = new Random().nextInt((int)interval); 
for (Element e: list) { 
    counter += (interval * e.probability()/totalProbabilities); 
    if (randInt < counter) { 
    return e.activity(); 
    } 
}