Sélectionnez un élément aléatoire dans une liste pondérée

Question

J'essaie d'écrire un programme pour sélectionner un nom aléatoire parmi US Census last name list. Le format de liste est

Name   Weight Cumulative line 
-----   ----- -----  - 
SMITH   1.006 1.006  1 
JOHNSON  0.810 1.816  2 
WILLIAMS  0.699 2.515  3 
JONES   0.621 3.136  4 
BROWN   0.621 3.757  5 
DAVIS   0.480 4.237  6 

En supposant que je charge les données dans une structure comme

Class Name 
{ 
    public string Name {get; set;} 
    public decimal Weight {get; set;} 
    public decimal Cumulative {get; set;} 
} 

Quelle est la structure des données serait préférable de tenir la liste des noms, et quelle serait la meilleure façon de choisir un nom aléatoire de la liste, mais la distribution des noms doit être la même que le monde réel.

Je ne travaillerai qu'avec les 10 000 premières lignes si cela fait une différence dans la structure de données.

J'ai essayé d'examiner d'autres questions concernant le caractère aléatoire pondéré, mais j'ai un peu de mal à faire passer la théorie au code. Je ne connais pas grand-chose à la théorie mathématique, donc je ne sais pas s'il s'agit d'une sélection aléatoire "Avec ou sans remplacement", je veux que le même nom puisse apparaître plus d'une fois, quelle que soit la signification.

Answer 1

La façon la plus simple de gérer cela serait de garder ceci dans une liste.

Vous pouvez alors utilisez simplement:

Name GetRandomName(Random random, List<Name> names) 
{ 
    double value = random.NextDouble() * names[names.Count-1].Culmitive; 
    return names.Last(name => name.Culmitive <= value); 
} 

Si la vitesse est un problème, vous pouvez stocker un tableau séparé seulement les valeurs Culmitive. Avec cela, vous pouvez utiliser Array.BinarySearch pour trouver rapidement l'index approprié:

Name GetRandomName(Random random, List<Name> names, double[] culmitiveValues) 
{ 
    double value = random.NextDouble() * names[names.Count-1].Culmitive; 
    int index = Array.BinarySearch(culmitiveValues, value); 
    if (index >= 0) 
     index = ~index; 

    return names[index]; 
} 

Une autre option, qui est probablement la plus efficace, serait d'utiliser quelque chose comme l'un des de la tree classesC5 Generic Collection Library. Vous pouvez ensuite utiliser RangeFrom pour trouver le nom approprié. Cela a l'avantage de ne pas nécessiter de collection séparée

Answer 2

Je dirais qu'un tableau (vecteurs si vous préférez) serait préférable de les conserver. Quant à la moyenne pondérée, trouvez la somme, choisissez un nombre aléatoire entre zéro et la somme, et choisissez le nom de famille dont la valeur cumulée est inférieure. (Par exemple ici, < 1,006 = forgeron, = 1,006 à 1,816 johnson, etc.

PS il est cumulatif

Answer 3

Juste pour le plaisir, et en aucune façon optimale

List<Name> Names = //Load your structure into this 

List<String> NameBank = new List<String>(); 
foreach(Name name in Names) 
    for(int i = 0; i <= (int)(name.Weight*1000); i++) 
    NameBank.Add(name.Name) 

alors:.

String output = NameBank[rand(NameBank.Count)]; 

Answer 4

J'ai créé a C# library for randomly selected weighted items.

• Il implémente à la fois les algorithmes de sélection d'arbre et de méthode d'alias de déambulateur, pour donner les meilleures performances pour tous les cas d'utilisation.
• Il est testé unitairement et optimisé.
• Il a le support de LINQ.
• C'est gratuit et open-source, sous licence MIT.

Quelques exemples de code:

IWeightedRandomizer<string> randomizer = new DynamicWeightedRandomizer<string>(); 
randomizer["Joe"] = 1; 
randomizer["Ryan"] = 2; 
randomizer["Jason"] = 2; 

string name1 = randomizer.RandomWithReplacement(); 
//name1 has a 20% chance of being "Joe", 40% of "Ryan", 40% of "Jason" 

string name2 = randomizer.RandomWithRemoval(); 
//Same as above, except whichever one was chosen has been removed from the list.