在c#中，按权重选择随机元素最简洁的方法是什么

本文关键字：元素 简洁 是什么 方法 随机 选择 权重 | 更新日期: 2023-09-27 18:22:23

让我们假设：

List<element>哪个元素是：

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

我想要实现的是，根据权重随机选择一个元素。例如：

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

所以

  • CCD_ 2被选中的几率为100/（100+50+200）=28.57%
  • CCD_ 3被选中的几率为50/（100+50+200）=14.29%
  • CCD_ 4被选中的几率为200/（100+50+200）=57.14%

我知道我可以创建一个循环，计算总数，等等…

我想学习的是，Linq在一行（或尽可能短）中做到这一点的最佳方法是什么，谢谢

更新

我在下面找到了答案。我学到的第一件事是：Linq不是魔术，它比精心设计的循环慢。

所以我的问题变成了按权重找到一个随机元素，（没有尽可能短的东西：）

在c#中，按权重选择随机元素最简洁的方法是什么

如果您想要通用版本（对于与（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");
}

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

这是一个带有预计算的快速解决方案。预计算采用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;
}

这可以工作：

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（不在一行中…）

.Net 6引入了.MaxBy，使此操作更加简单。
现在可以将其简化为以下一行：

list.MaxBy(x => rng.GetNext(x.weight));

如果权重较大或为浮点数，则效果最佳，否则会发生碰撞，可以通过将权重乘以某个因子来防止碰撞。

相关文章：