Какой самый краткий способ выбрать случайный элемент по весу в c #? - PullRequest
Новая
       12

Какой самый краткий способ выбрать случайный элемент по весу в c #?

11 голосов
/ 04 февраля 2012

Предположим, что:

List<element> какой элемент: 

public class Element(){
   int Weight {get;set;}
}

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

Element_1.Weight = 100;
Element_2.Weight = 50;
Element_3.Weight = 200;

Итак

  • шанс, что Element_1 будет выбран, равен 100 / (100 + 50 + 200) = 28,57%
  • шанс, что Element_2 будет выбран, равен 50 / (100 + 50 + 200) = 14,29%
  • шанс, что Element_3 будет выбран, равен 200 / (100 + 50 + 200) = 57,14%

Я знаю, что могу создать цикл, вычислить итоги и т. Д. *

Что я хочу узнать, так это лучший способ сделать это с помощью Linq в ОДНОЙ строке (или как можно короче), спасибо.

UPDATE

Я нашел свой ответ ниже. Первое, что я узнал, это: Linq НЕ волшебство, он медленнее, чем хорошо продуманный цикл .

Таким образом, мой вопрос становится найти случайный элемент по весу (без как можно более коротких вещей:)

Ответы [ 4 ]

4 голосов
/ 04 февраля 2012

Если вы хотите универсальную версию (полезно для использования с (singleton) помощником рандомизации, подумайте, нужен ли вам постоянный начальный размер или нет)

использование: 

randomizer.GetRandomItem(items, x => x.Weight)

код: 

public T GetRandomItem<T>(IEnumerable<T> itemsEnumerable, Func<T, int> weightKey)
{
    var items = itemsEnumerable.ToList();

    var totalWeight = items.Sum(x => weightKey(x));
    var randomWeightedIndex = _random.Next(totalWeight);
    var itemWeightedIndex = 0;
    foreach(var item in items)
    {
        itemWeightedIndex += weightKey(item);
        if(randomWeightedIndex < itemWeightedIndex)
            return item;
    }
    throw new ArgumentException("Collection count and weights must be greater than 0");
}
4 голосов
/ 04 февраля 2012 
// assuming rnd is an already instantiated instance of the Random class
var max = list.Sum(y => y.Weight);
var rand = rnd.Next(max);
var res = list
    .FirstOrDefault(x => rand >= (max -= x.Weight));
3 голосов
/ 04 февраля 2012

Это быстрое решение с предварительным вычислением. Предварительный расчет занимает O(n), поиск O(log(n)).

предвычисления: 

int[] lookup=new int[elements.Length];
lookup[0]=elements[0].Weight-1;
for(int i=1;i<lookup.Length;i++)
{
  lookup[i]=lookup[i-1]+elements[i].Weight;
}

Для генерации: 

int total=lookup[lookup.Length-1];
int chosen=random.GetNext(total);
int index=Array.BinarySearch(lookup,chosen);
if(index<0)
  index=~index;
return elements[index];

Но если список меняется между каждым поиском, вы можете вместо этого использовать простой O(n) линейный поиск: 

int total=elements.Sum(e=>e.Weight);
int chosen=random.GetNext(total);
int runningSum=0;
foreach(var element in elements)
{
  runningSum+=element.Weight;
  if(chosen<runningSum)
    return element;
}
2 голосов
/ 04 февраля 2012

Это может сработать: 

int weightsSum = list.Sum(element => element.Weight);
int start = 1;
var partitions = list.Select(element => 
                 { 
                   var oldStart = start;
                   start += element.Weight;
                   return new { Element = element, End = oldStart + element.Weight - 1};
                 });

var randomWeight = random.Next(weightsSum);
var randomElement = partitions.First(partition => (partition.End > randomWeight)).
                               Select(partition => partition.Element);

По сути, для каждого элемента создается раздел с конечным весом. В вашем примере Element1 будет связан с (1 -> 100), Element2 связан с (101 -> 151) и так далее ...

Затем вычисляется случайная весовая сумма, и мы ищем диапазон, связанный с ней.

Вы также можете вычислить сумму в группе методов, но это приведет к другому побочному эффекту ...

Заметьте, я не говорю, что это элегантно или быстро. Но он использует linq (не в одну строку ...)

...