Выберите случайный элемент из взвешенного списка

Question

Я пытаюсь написать программу для выбора случайного имени из списка фамилий переписи США . Формат списка

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

Предполагается, что я загружаю данные в структуру типа

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

В какой структуре данных лучше всего хранить список имен и каков наилучший способ выбрать случайное имя из списка, но распределение имен будет таким же, как в реальном мире.

Я буду работать с первыми 10000 строк только в том случае, если это повлияет на структуру данных.

Я пытался рассмотреть некоторые другие вопросы о взвешенной случайности, но у меня возникли некоторые проблемы с превращением теории в код. Я не очень разбираюсь в математической теории, поэтому не знаю, является ли это случайным выбором «с заменой или без него», я хочу, чтобы одно и то же имя могло появляться более одного раза, что когда-либо означало.

Answer 1

Самый простой способ справиться с этим - сохранить это в списке.

Затем вы можете просто использовать:

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

Если скорость имеет значение, вы можете сохранитьотдельный массив только Culmitive значений.При этом вы можете использовать Array.BinarySearch для быстрого поиска подходящего индекса:

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

Другой вариант, который, вероятно, наиболее эффективен, - это использовать что-то вроде одного из C5 Generic CollectionБиблиотека дерево классов .Затем вы можете использовать RangeFrom, чтобы найти подходящее имя.Преимущество в том, что не требуется отдельная коллекция

Answer 2

Я создал библиотеку C # для случайно выбранных взвешенных элементов .

• В нем реализованы алгоритмы выбора дерева и псевдонима метода Уокера, чтобы обеспечить максимальную производительность для всех вариантов использования.
• Он протестирован и оптимизирован.
• Имеет поддержку LINQ.
• Это бесплатно и с открытым исходным кодом, под лицензией MIT.

Пример кода:

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

Просто для удовольствия и ни в коем случае не оптимально

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)

тогда:

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

Answer 4

Я бы сказал, что массив (векторы, если вы предпочитаете) будет лучше всего содержать их. Что касается средневзвешенного значения, найдите сумму, выберите случайное число от нуля до суммы и укажите фамилию, совокупное значение которой меньше. (например, здесь <1,006 = Смит, 1,006-1,816 = Джонсон и т. д. </p>

P.S. это накопительно.