Seleziona un elemento casuale da un elenco ponderato

Question

Sto cercando di scrivere un programma per selezionare un nome casuale da Elenco cognome del censimento degli Stati Uniti. Il formato dell'elenco è

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 carichi i dati in una struttura come

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

Quale struttura dei dati sarebbe meglio tenere l'elenco dei nomi e quale sarebbe il modo migliore per selezionare un nome casuale dall'elenco ma avere la distribuzione dei nomi uguali al mondo reale.

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

Ho provato a guardare alcune delle altre domande sulla casualità ponderata, ma ho un po 'di difficoltà a trasformare la teoria al codice. Non so molto della teoria matematica, quindi non so se questa sia una selezione casuale "con o senza sostituzione", voglio lo stesso nome in grado di presentarsi più di una volta, il che significa mai.

Answer 1

Il modo "più semplice" per gestirlo sarebbe quello di mantenerlo in un elenco.

Potresti quindi 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 archiviare una serie separata di solo Culmitive i valori. Con questo, potresti usare 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ù efficiente, sarebbe quella di usare qualcosa come uno dei Biblioteca di raccolta generica C5'S Classi di alberi. Potresti quindi usare RangeFrom Per trovare il nome appropriato. Ciò ha il vantaggio di non richiedere una raccolta separata

Answer 2

Ho creato una libreria C# per oggetti ponderati selezionati casualmente.

• Implementa sia gli algoritmi del metodo alias per selezione albero che walker, per offrire le migliori prestazioni per tutti i casi d'uso.
• È testato con unità e ottimizzato.
• Ha il supporto LINQ.
• È gratuito e open-source, concesso in licenza con la licenza del MIT.

Qualche codice di esempio:

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

Direi che un array (vettori se preferisci) sarebbe meglio tenerli. Per quanto riguarda la media ponderata, trova la somma, scegli un numero casuale tra zero e la somma e scegli il cognome il cui valore cumulativo è inferiore. (ad es. Qui, <1.006 = Smith, 1.006-1.816 = Johnson, ecc.

PS È cumulativo.

Answer 4

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