Seleccione un elemento aleatorio de una lista ponderada

Question

Estoy intentando escribir un programa para seleccionar un nombre aleatorio del Lista de apellidos del censo de EE. UU..El formato de la 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 que cargo 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 mejor para contener la lista de nombres y cuál sería la mejor manera de seleccionar un nombre aleatorio de la lista pero que la distribución de nombres sea la misma que en el mundo real?

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

Intenté analizar algunas de las otras preguntas sobre la aleatoriedad ponderada, pero tengo algunos problemas para convertir la teoría en código.No sé mucho sobre teoría matemática, así que no sé si se trata de una selección aleatoria "Con o sin reemplazo". Quiero que el mismo nombre pueda aparecer más de una vez, sea lo que sea.

Answer 1

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

Entonces podrías 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 variedad separada de solo el Culmitive valores. Con esto, podrías usar Array.BinarySearch Para 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 la más eficiente, sería usar algo como uno de los Biblioteca de colección genérica C5's clases de árboles. Entonces podrías usar RangeFrom Para encontrar el nombre apropiado. Esto tiene la ventaja de no requerir una colección separada

Answer 2

He creado una biblioteca C# para artículos ponderados seleccionados al azar.

• Implementa los algoritmos de método de alias de selección de árboles y alias de Walker, para dar el mejor rendimiento para todos los casos de uso.
• Está probado y optimizado.
• Tiene soporte LINQ.
• Es gratuito y de código abierto, con licencia bajo la licencia MIT.

Algún 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.

Answer 3

Yo diría que una matriz (vectores si lo prefiere) sería mejor para contenerlos.En cuanto al promedio ponderado, encuentre la suma, elija un número aleatorio entre cero y la suma y elija el apellido cuyo valor acumulado sea menor.(p.ej.aquí, <1.006 = smith, 1.006-1.816 = johnson, etc.

PDes acumulativo.

Answer 4

Solo 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)

después:

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