linq 在C#中按权重随机选取元素的最简洁方法是什么?

7cwmlq89  于 2022-12-06  发布在  C#
关注(0)|答案(4)|浏览(209)

让我们假设:
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在一行中(或尽可能短)做这件事的最好方法是什么,谢谢。*
    更新

我在下面找到了我的答案。我学到的第一件事是:Linq不是魔术,它比设计良好的循环要慢
所以我的问题变成了找到一个随机元素的重量,(没有尽可能短的东西:)

utugiqy6

utugiqy61#

如果您想要一个泛型版本(对于与(单一)随机化助手一起使用很有用,请考虑您是否需要一个常量种子)
使用方法:

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");
}
nxagd54h

nxagd54h2#

// 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));
sauutmhj

sauutmhj3#

这是一个带预计算的快速解,预计算需要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;
}
eivnm1vs

eivnm1vs4#

这可能行得通:

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

基本上,对于每个元素,都创建了一个具有最终权重的分区。在您的示例中,元素1将关联到(1--〉100),元素2关联到(101--〉151),依此类推...
然后计算随机权重和,并寻找与之相关的范围。
你也可以在方法组中计算总和,但那会引入另一个副作用...
请注意,我并不是说这是优雅或快速的。但它确实使用了linq(不是在一行中...)

相关问题