Selezionare un elemento casuale da un elenco ponderato

Question

Sto provando a scrivere un programma per selezionare un nome casuale dallo US Census last name list. Il formato lista è

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 

supponendo che caricare i dati per una struttura come

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

Quale struttura di dati sarebbe meglio per tenere l'elenco dei nomi, e quale sarebbe il modo migliore per selezionare un nome casuale dalla lista ma la distribuzione dei nomi è la stessa del mondo reale.

Lavorerò solo con le prime 10.000 righe se fa la differenza nella struttura dei dati.

Ho provato a guardare alcune delle altre domande sulla casualità ponderata, ma ho un po 'di problemi nel trasformare la teoria in codice. Non so molto sulla teoria matematica, quindi non so se si tratta di una selezione casuale "Con o senza sostituzione", voglio che lo stesso nome sia in grado di mostrarsi più di una volta, il che significa sempre quello.

Answer 1

Il modo "più semplice" per gestirlo sarebbe quello di tenerlo in una lista.

Si potrebbe poi basta usare:

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

Se la velocità è un problema, è possibile memorizzare un array separato di soli i valori Culmitive. Con questo, è possibile utilizzare Array.BinarySearch per trovare rapidamente l'indice appropriato:

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

Un'altra opzione, che è probabilmente la più efficace, sarebbe quella di usare qualcosa come uno dei 's tree classes il C5 Generic Collection Library. È quindi possibile utilizzare RangeFrom per trovare il nome appropriato. Questo ha il vantaggio di non richiedere una raccolta separata

Answer 2

Direi che un array (i vettori se si preferisce) sarebbe meglio tenerli. Per quanto riguarda la media ponderata, trova la somma, scegli un numero casuale compreso tra zero e la somma e scegli il cognome il cui valore cumulativo è inferiore. (Ad esempio qui, < 1.006 = Smith, 1,006-1,816 = johnson, ecc

PS E 'cumulativo

Answer 3

Solo per divertimento, e in nessun modo ottimale

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) 

poi:.

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

Answer 4

ho creato a C# library for randomly selected weighted items.

• Implementa entrambi gli algoritmi del metodo di alias e walker alias, per fornire le migliori prestazioni per tutti i casi di utilizzo.
• È testato e ottimizzato per unità.
• Ha il supporto LINQ.
• È gratuito e open source, con licenza MIT.

qualche esempio di codice:

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.