11

仮定しましょう：

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 でこれを 1 行で (またはできるだけ短く) 実行する最善の方法は何ですか、ありがとうございます。

アップデート

以下に私の答えを見つけました。私が最初に学んだことは、Linqは魔法ではなく、適切に設計された loop よりも遅いということです。

したがって、私の質問は、重みでランダムな要素を見つけることになります(できるだけ短いものはありません:)

4

4 に答える 4

5 
// 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));
于 2012-02-04T14:42:59.563 に答える
4

汎用バージョンが必要な場合((シングルトン) ランダム化ヘルパーで使用する場合に便利です。定数シードが必要かどうかを検討してください)

利用方法：

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");
}
于 2012-02-04T15:17:56.363 に答える
3

これは、事前計算による高速なソリューションです。事前計算には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;
}
于 2012-02-04T14:55:50.933 に答える
2

これはうまくいくかもしれません：

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を使用します（1行ではありません...）

于 2012-02-04T15:18:42.893 に答える