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

Question

J'essaye d'écrire un programme pour sélectionner un nom aléatoire dans le recensement américainliste de nom de famille .Le format de la 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 structure de données serait la meilleure pour contenir la liste des noms, et quelle serait la meilleure façon de sélectionner un nom aléatoire dans la liste mais que la distribution des noms soit la même que dans le monde réel.

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

J'ai essayé d'examiner certaines des autres questions sur le caractère aléatoire pondéré, mais j'ai un peu de mal à transformer la théorie en 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, ce que cela signifie.

Answer 1

Le moyen le plus "simple" de gérer cela serait de conserver cela dans une liste.

Vous pouvez alors simplement utiliser:

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é contenant uniquement 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 C5 GenericLes classes d'arbres de la bibliothèque de collections .Vous pouvez ensuite utiliser RangeFrom pour trouver le nom approprié.Cela a l'avantage de ne pas nécessiter de collecte séparée

Answer 2

J'ai créé une bibliothèque C # pour les éléments pondérés sélectionnés au hasard .

• Il implémente à la fois les algorithmes de sélection d'arbre et d'alias de marche, pour donner les meilleures performances pour tous les cas d'utilisation.
• Il est testé et optimisé à l'unité.
• Il prend en charge 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.

Answer 3

Je dirais qu'un tableau (des vecteurs si vous préférez) serait préférable de les contenir.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= smith, 1.006-1.816= johnson, etc.

P.S.c'est cumulatif.

Answer 4

Juste pour le plaisir, et en aucun cas optimal

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)];