Seleccione un elemento aleatorio de una lista ponderada

Question

Estoy intentando escribir un programa para seleccionar un nombre aleatorio del US Census last name list. El formato de lista es

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 

Suponiendo me carga los datos en una estructura como

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

Qué estructura de datos sería lo mejor para mantener la lista de nombres, y cuál sería la mejor manera de seleccionar un nombre aleatorio de la lista pero la distribución de nombres sea la misma que en el mundo real.

Solo trabajaré con las primeras 10.000 filas si hace una diferencia en la estructura de datos.

He intentado ver algunas de las otras preguntas sobre aleatoriedad ponderada, pero estoy teniendo problemas para convertir la teoría en código. No sé mucho acerca de la teoría de las matemáticas, así que no sé si se trata de una selección aleatoria "con o sin reemplazo", quiero que el mismo nombre se muestre más de una vez, lo que sea que eso signifique.

Answer 1

La forma "más fácil" de manejar esto sería mantener esto en una lista.

A continuación, puede simplemente usar:

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 velocidad es una preocupación, podría almacenar una matriz separada de sólo los valores Culmitive. Con esto, se podía utilizar Array.BinarySearch a encontrar rápidamente el índice apropiado:

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

Otra opción, que es probablemente el más eficiente, habría que usar algo como uno de los C5 Generic Collection Library 's tree classes. Luego puede usar RangeFrom para encontrar el nombre apropiado. Esto tiene la ventaja de que no requiere una colección separada

Answer 2

Yo diría que una matriz (vectores si lo prefiere) sería mejor para mantenerlos. En cuanto al promedio ponderado, encuentre la suma, elija un número aleatorio entre cero y la suma, y ​​elija el apellido cuyo valor acumulativo sea menor. (Por ejemplo, aquí, < 1.006 = Smith, 1,006-1,816 = Johnson, etc.

PS Es acumulativo

Answer 3

Sólo por diversión, y de ninguna manera óptima

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) 

a continuación:.

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

Answer 4

he creado a C# library for randomly selected weighted items.

• Implementa los algoritmos de método de selección de árbol y alias walker, para ofrecer el mejor rendimiento para todos los casos de uso.
• Ha sido probado y optimizado.
• Tiene soporte LINQ.
• Es gratis y de código abierto, con licencia bajo la licencia de MIT.

un código de ejemplo:

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.