问题 什么是最简洁的方法来在c#中按重量选择随机元素?


让我们假设:

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不是魔法,它比设计良好的循环慢

所以我的问题变成了按重量找到一个随机元素,(尽可能短的东西:)


11788
2018-02-04 14:34


起源

所以你想要短代码,但你不关心它的速度慢吗? - CodesInChaos
Linq将慢于基于循环的代码。如果您想要快速代码,则需要预先计算 O(n) 所以你可以 O(1) 抬头。但是代码相对复杂。 - CodesInChaos
您如何看待Linq(对象)的工作原理?魔法?它只是封装了循环,通常比手写循环慢约2-3倍。 linq的主要优点是更清晰的代码。 - CodesInChaos
LINQ确实比自己编写一个高效的迭代算法慢。 linq的原因是它更易于阅读/使用,并且不太可能导致错误。 - roken
@CodeInChaos - 慢2到3倍是夸张的夸张。 - roken


答案:


如果你想要一个 通用版本 (对于使用(单例)随机化帮助器很有用,请考虑是否需要一个常量种子)

用法:

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
2018-02-04 15:17



我喜欢这个解决方案,看起来非常体面。另外,我会编辑并允许 totalWeight=0,然后随机选择一个(由于它们的权重相同,具有相同的机会)而不抛出异常。 - Eric Yin
我想在这里我发现了一个问题(一个小问题),你应该使用 randomWeightedIndex = _random.Next(totalWeight)+1;,然后比较 if(randomWeightedIndex <= itemWeightedIndex)。否则,被选中的机会与我在问题中的要求略有不同。 - Eric Yin
我相信它没有什么区别。 - doblak
它使。让我们假设 A=0, B=2,A被选中的几率为0%,B为100%。 R=rand.Next(2)将返回0-1。当R = 1时,将选择A,对于A和B变为50%。如果使用+1,R = 1到2,则<= 0 - Eric Yin
在基于零的索引时,它会有所不同,但我认为权重值0为“0%偶然”,所以......这一切都取决于定义。但是很高兴看到你发现它很有用。 - doblak


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

4
2018-02-04 14:42



分解出 list.Max(...)。您当前的代码是 O(n^2)。如果你把它考虑出来,它就是唯一的 O(n*log(n)) - CodesInChaos
如果您需要First(),并且您已经使用Random,为什么要按Random订购?另外,我会缓存list.Max,没有理由计算每次迭代的最大值。 - Abel
无论如何,对@allguys,我想我只是使用循环:( - Eric Yin
@EricYin:他在最大体重上使用随机数,因为你说200应该被选中的机会比50更高。但是,我不确定它是否与你提出的问题中的总和(体重)相匹配。排序似乎确实多余(参见我之前的评论)。 - Abel
该 minWeight 是为了确保随着体重的增加更频繁地选择项目。随机顺序(@Abel)用于选择 一个随机的项目 从结果集中,只选择第一个永远不会产生 Weight=50 示例中的项目,即使 minWeight 将会 < 50 - Nuffin


这是一个预计算的快速解决方案。预计算需要 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
2018-02-04 14:55



问题的LINQ在哪里? ;) - Abel
int total=elements.Sum(e=>e.Weight) :P这是我发现linq在这个问题上有用的唯一地方。我找不到用linq执行搜索的快速而干净的方法。 - CodesInChaos


这可能有效:

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(不在一行......)


2
2018-02-04 15:18



谢谢。我想我会留下linq除了sum部分,因为它在路上创造了太多的新对象 - Eric Yin