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

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

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

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

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

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


random c# distribution weighted
person Scott Chamberlain    schedule 09.09.2011    source источник
comment
Храните совокупные данные в сбалансированном двоичном дереве с именами в узлах. Выберите случайное целое число, меньшее суммы кумулятивных величин, и найдите его (меньше чем) в дереве бинов.   -  person Dr. belisarius    schedule 10.09.2011
comment
@belisarius Существуют ли какие-либо бинарные древовидные структуры, встроенные в .NET, или мне придется их написать?   -  person Scott Chamberlain    schedule 10.09.2011
comment
@Scott: Вы можете просто использовать массив для этого - BinarySearch будет работать нормально, пока он отсортирован ...   -  person Reed Copsey    schedule 10.09.2011
comment
@Scott Я не говорю .Net, но думаю, должно быть ... вот почему я не написал ответ   -  person Dr. belisarius    schedule 10.09.2011
comment
@Scott: встроенных нет, но есть хорошие варианты, например: itu. dk / research / c5   -  person Reed Copsey    schedule 10.09.2011

Ответы (4)


arrow_upward
9
arrow_downward

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

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

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 древовидные классы. Затем вы можете использовать RangeFrom, чтобы найти подходящее имя. Это имеет то преимущество, что не требует отдельного сбора

person Reed Copsey    schedule 09.09.2011
comment
Ваша первая имплантация будет достаточно быстрой для того, что мне нужно, спасибо! - person Scott Chamberlain; 10.09.2011
comment
Мы пришли к такому же решению. Кроме того, мы реализовали эффективную оболочку вокруг NextDouble для распределения информации по нескольким выборкам GetRandomName (не требуется 32-битная информация для выбора из 6 вариантов). - person gap; 19.11.2013
comment
Глядя на это, я чувствую, что ответ двоичного поиска требует другого знака в выражении if. Если индекс равен нулю или больше, используйте этот ответ. Если он меньше нуля, выполните побитовое дополнение (~), чтобы получить первый элемент (если есть), который больше заданного значения поиска (согласно документации Array.BinarySearch). - person jbarz; 29.01.2020

arrow_upward
3
arrow_downward

Я создал библиотеку 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.
person BlueRaja - Danny Pflughoeft    schedule 19.06.2015

arrow_upward
0
arrow_downward

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

P.S. это кумулятивно.

person Kevin    schedule 09.09.2011

arrow_upward
0
arrow_downward

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

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)];
person normanthesquid    schedule 09.09.2011