logo标签列表

随机加权选择

c#algorithmrandom
66

考虑下面代表经纪人的类：

public class Broker
{
    public string Name = string.Empty;
    public int Weight = 0;

    public Broker(string n, int w)
    {
        this.Name = n;
        this.Weight = w;
    }
}

我希望能从数组中随机选择一个Broker，考虑到他们的权重。您认为下面的代码怎么样？
class Program
    {
        private static Random _rnd = new Random();

        public static Broker GetBroker(List<Broker> brokers, int totalWeight)
        {
            // totalWeight is the sum of all brokers' weight

            int randomNumber = _rnd.Next(0, totalWeight);

            Broker selectedBroker = null;
            foreach (Broker broker in brokers)
            {
                if (randomNumber <= broker.Weight)
                {
                    selectedBroker = broker;
                    break;
                }

                randomNumber = randomNumber - broker.Weight;
            }

            return selectedBroker;
        }


        static void Main(string[] args)
        {
            List<Broker> brokers = new List<Broker>();
            brokers.Add(new Broker("A", 10));
            brokers.Add(new Broker("B", 20));
            brokers.Add(new Broker("C", 20));
            brokers.Add(new Broker("D", 10));

            // total the weigth
            int totalWeight = 0;
            foreach (Broker broker in brokers)
            {
                totalWeight += broker.Weight;
            }

            while (true)
            {
                Dictionary<string, int> result = new Dictionary<string, int>();

                Broker selectedBroker = null;

                for (int i = 0; i < 1000; i++)
                {
                    selectedBroker = GetBroker(brokers, totalWeight);
                    if (selectedBroker != null)
                    {
                        if (result.ContainsKey(selectedBroker.Name))
                        {
                            result[selectedBroker.Name] = result[selectedBroker.Name] + 1;
                        }
                        else
                        {
                            result.Add(selectedBroker.Name, 1);
                        }
                    }
                }


                Console.WriteLine("A\t\t" + result["A"]);
                Console.WriteLine("B\t\t" + result["B"]);
                Console.WriteLine("C\t\t" + result["C"]);
                Console.WriteLine("D\t\t" + result["D"]);

                result.Clear();
                Console.WriteLine();
                Console.ReadLine();
            }
        }
    }

我不太自信。当我运行这个程序时，经纪人A总是比经纪人D获得更多的命中率，而它们的权重是相同的。

是否有更准确的算法呢？

谢谢！

您好，我看到了您的问题，并受到启发，使用您的算法在Java中创建了自己的广告轮换器类。我恳请您解释一下，如果数据库中有一百万个经纪人存储在宽行中，您将如何从中选择经纪人。我是否应该选择前n个经纪人并应用您的算法来随机选择一个经纪人，在下一个请求中选择从n+1开始的下一个n个经纪人，以此类推？ - qualebs
我写了一个非常类似的库...它有一些额外的功能，并且针对大数据集进行了优化：https://github.com/kinetiq/Ether.WeightedSelector - Brian MacKay
你的经纪人需要按权重升序排序吗？ - jjxtra
12个回答
44

你的算法几乎正确。不过，测试应该使用<而不是<=：

if (randomNumber < broker.Weight)
这是因为随机数包含0，而totalWeight不包括0。换句话说，权重为0的代理仍然有被选择的小概率，这绝不是你想要的结果。这就解释了为什么代理A的命中次数比代理D多。
除此之外，你的算法很好，实际上是解决这个问题的规范方法。
这个也适用于双精度权重值吗？ - Jordan
@Jordan，它会精确到double的精度。然而，上述代码使用了_rnd.Next，它只适用于整数范围。要使用双精度范围，您需要使用适当的方法来生成一个来自double范围的数字。 - Konrad Rudolph
我知道。Random有一个NextDouble方法，返回0.0到1.0之间的double类型值。我只需要将这个值乘以总重量即可 :) 谢谢。 - Jordan
23

那么有没有一些更通用的东西，适用于任何数据类型呢？

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

public static class IEnumerableExtensions {
    
    public static T RandomElementByWeight<T>(this IEnumerable<T> sequence, Func<T, float> weightSelector) {
        float totalWeight = sequence.Sum(weightSelector);
        // The weight we are after...
        float itemWeightIndex =  (float)new Random().NextDouble() * totalWeight;
        float currentWeightIndex = 0;

        foreach(var item in from weightedItem in sequence select new { Value = weightedItem, Weight = weightSelector(weightedItem) }) {
            currentWeightIndex += item.Weight;
            
            // If we've hit or passed the weight we are after for this item then it's the one we want....
            if(currentWeightIndex >= itemWeightIndex)
                return item.Value;
            
        }
        
        return default(T);
        
    }
    
}

只需调用

    Dictionary<string, float> foo = new Dictionary<string, float>();
    foo.Add("Item 25% 1", 0.5f);
    foo.Add("Item 25% 2", 0.5f);
    foo.Add("Item 50%", 1f);
    
    for(int i = 0; i < 10; i++)
        Console.WriteLine(this, "Item Chosen {0}", foo.RandomElementByWeight(e => e.Value));
1
我认为你应该使用currentWeightIndex > itemWeightIndex而不是>=。如果一个物品的重量为0，那么这个物品就永远不应该被选中。使用>=会使得重量为0的物品被选中的机会非常小。 - M.kazem Akhgary
谢谢，非常有用！我想建议一个修改，即在每次调用RandomElementByWeight时不要创建新的Random实例，而是添加一个私有静态Random变量，在静态构造函数中初始化。否则，像我一样，在循环中调用时，由于种子相同，您几乎会得到所有相似的值。 - nathan raynal
13
class Program
{
    static void Main(string[] args)
    {
        var books = new List<Book> {
        new Book{Isbn=1,Name="A",Popularity=1},
        new Book{Isbn=2,Name="B",Popularity=100},
        new Book{Isbn=3,Name="C",Popularity=1000},
        new Book{Isbn=4,Name="D",Popularity=10000},
        new Book{Isbn=5,Name="E",Popularity=100000}};

        Book randomlySelectedBook = books.WeightedRandomization(b => b.Popularity);
    }
}

public static class EnumerableExtensions
{
    private static readonly Random rand = new Random();

    public static T WeightedRandomization<T>(this IEnumerable<T> source, Func<T, int> weightSelector)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source));
        }

        if (weightSelector == null)
        {
            throw new ArgumentNullException(nameof(weightSelector));
        }

        int count = source.Count();
        if (count == 0)
        {
            throw new InvalidOperationException("Sequence contains no elements");
        }

        int totalWeight = source.Sum(weightSelector);
        int choice = rand.Next(totalWeight);
        int sum = 0;

        foreach (var obj in source)
        {
            sum += weightSelector(obj);
            if (choice < sum)
            {
                return obj;
            }
        }

        return source.First();
    }
}

public class Book
{
    public int Isbn { get; set; }
    public string Name { get; set; }
    public int Popularity { get; set; }
}
3
每次使用new Random()时，它都会使用时钟进行初始化。这意味着在一个紧密的循环中，您会多次获得相同的值。您应该保持单个Random实例并在同一实例上继续使用Next方法。因此，为Random实例进行类级别声明。 - MichielDeRouter
3
为什么需要内部循环？仅仅将权重加到总和中，然后检查是否大于等于选择，这样不就可以了吗？ - Mladen Mihajlovic
根据两个评论修复了代码。 - Cagatay
5

由于这是谷歌的首要结果：

我已经创建了 一个用于随机选择加权项的C#库。

  • 它实现了树选择和Walker Alias方法算法，以在所有用例中提供最佳性能。
  • 它经过单元测试和优化。
  • 它支持LINQ。
  • 它是免费且开源的，遵循MIT许可协议。

一些示例代码：

IWeightedRandomizer<string> randomizer = new DynamicWeightedRandomizer<string>();
randomizer["Joe"] = 1;
randomizer["Ryan"] = 2;
randomizer["Jason"] = 2;

string name1 = randomizer.RandomWithReplacement();
//name1 has a 20% chance of being "Joe", 40% of "Ryan", 40% of "Jason"

string name2 = randomizer.RandomWithRemoval();
//Same as above, except whichever one was chosen has been removed from the list.
嘿，这是线程安全的吗？ - Ben
3

另一种方法优先考虑在选择经纪人时的速度而不是内存使用率。基本上，我们创建包含与指定权重相同数量的经纪人实例引用的列表。

List<Broker> brokers = new List<Broker>();
for (int i=0; i<10; i++)
    brokers.Add(new Broker("A", 10));
for (int i=0; i<20; i++)
    brokers.Add(new Broker("B", 20));
for (int i=0; i<20; i++)
    brokers.Add(new Broker("C", 20));
for (int i=0; i<10; i++)
    brokers.Add(new Broker("D", 10));

然后，选择一个随机加权实例是O(1)的操作：
int randomNumber = _rnd.Next(0, brokers.length);
selectedBroker = brokers[randomNumber];
3
另一个不会占用太多内存的替代方案是使用指向经纪人数组的索引。 - HRJ
3
2022年6月：堆的另一个实现（使用c#）： https://github.com/cdanek/KaimiraWeightedList 具有 O(1) 获取（！），O(n) 内存，O(n) 添加/删除/编辑操作，鲁棒性强（几乎实现了所有 IList 方法），并且极易使用（一个 C# 文件，一行代码进行构造，一行代码添加项，一行代码获取项）。
WeightedList<string> myList = new();
myList.Add("Hello", 1);
myList.Add("World", 2);
Console.WriteLine(myList.Next()); // Hello 33%, World 66%

使用walker-vose别名方法。
2
有点晚了，但这是一个关于C#7的例子。它很小，给出了正确的分布。
public static class RandomTools
{
    public static T PickRandomItemWeighted<T>(IList<(T Item, int Weight)> items)
    {
        if ((items?.Count ?? 0) == 0)
        {
            return default;
        }

        int offset = 0;
        (T Item, int RangeTo)[] rangedItems = items
            .OrderBy(item => item.Weight)
            .Select(entry => (entry.Item, RangeTo: offset += entry.Weight))
            .ToArray();

        int randomNumber = new Random().Next(items.Sum(item => item.Weight)) + 1;
        return rangedItems.First(item => randomNumber <= item.RangeTo).Item;
    }
}
1
如果你想要更快的速度，可以考虑使用加权蓄水池抽样，这样你就不需要提前找到总体权重（但你需要更频繁地从随机数生成器中进行抽样）。代码可能会类似于：
Broker selected = null;
int s = 0;
foreach(Broker broker in brokers) {
    s += broker.Weight;
    if (broker.Weight <= _rnd.Next(0,s)) {
        selected = broker;
    }
}

这需要遍历经纪人列表一次。但是，如果经纪人列表是固定的或者不经常更改，您可以保留一个累积和数组，即A[i]是所有经纪人0,..,i-1的权重之和。然后，A[n]是总权重，如果您选择1到A[n-1]之间的数字，比如x，您会找到经纪人j，使得A[j-1] <= x < A[j]。为了方便起见，您可以让A[0] = 0。您可以使用二分查找在log(n)步骤中找到经纪人编号j，我将把代码留作简单的练习。如果您的数据经常更改，这可能不是一个好方法，因为每次某个权重发生变化时，您可能需要更新数组的大部分内容。

这是只有我这样还是那个循环总是在第一次迭代中选择第一个项目？ - Epirocks
1
@Epirocks 这样做可能会暂时解决问题，但在后续迭代中有可能被覆盖。 - Solomon Ucko
@Solomon 当然，你是对的。我写那篇文章的时候可能有些盲目。 - Epirocks
1
@Epirocks 我主要是为了那些容易混淆的人指出来的。（我一开始也很困惑！） - Solomon Ucko
0

分享一下我的实现方式。希望你会觉得有用。

    // Author: Giovanni Costagliola <giovanni.costagliola@gmail.com>

    using System;
    using System.Collections.Generic;
    using System.Linq;

    namespace Utils
    {
    /// <summary>
    /// Represent a Weighted Item.
    /// </summary>
    public interface IWeighted
    {
        /// <summary>
        /// A positive weight. It's up to the implementer ensure this requirement
        /// </summary>
        int Weight { get; }
    }

    /// <summary>
    /// Pick up an element reflecting its weight.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class RandomWeightedPicker<T> where T:IWeighted
    {
        private readonly IEnumerable<T> items;
        private readonly int totalWeight;
        private Random random = new Random();

        /// <summary>
        /// Initiliaze the structure. O(1) or O(n) depending by the options, default O(n).
        /// </summary>
        /// <param name="items">The items</param>
        /// <param name="checkWeights">If <c>true</c> will check that the weights are positive. O(N)</param>
        /// <param name="shallowCopy">If <c>true</c> will copy the original collection structure (not the items). Keep in mind that items lifecycle is impacted.</param>
        public RandomWeightedPicker(IEnumerable<T> items, bool checkWeights = true, bool shallowCopy = true)
        {
            if (items == null) throw new ArgumentNullException("items");
            if (!items.Any()) throw new ArgumentException("items cannot be empty");
            if (shallowCopy)
                this.items = new List<T>(items);
            else
                this.items = items;
            if (checkWeights && this.items.Any(i => i.Weight <= 0))
            {
                throw new ArgumentException("There exists some items with a non positive weight");
            }
            totalWeight = this.items.Sum(i => i.Weight);
        }
        /// <summary>
        /// Pick a random item based on its chance. O(n)
        /// </summary>
        /// <param name="defaultValue">The value returned in case the element has not been found</param>
        /// <returns></returns>
        public T PickAnItem()
        {
            int rnd = random.Next(totalWeight);
            return items.First(i => (rnd -= i.Weight) < 0);
        }

        /// <summary>
        /// Resets the internal random generator. O(1)
        /// </summary>
        /// <param name="seed"></param>
        public void ResetRandomGenerator(int? seed)
        {
            random = seed.HasValue ? new Random(seed.Value) : new Random();
        }
    }
}

要点：https://gist.github.com/MrBogomips/ae6f6c9af8032392e4b93aaa393df447
也许我读错了这段代码，但如果你有两个重量相同的物品，我认为它不会正常工作。 - Anthony Nichols
0

另一个选项是这样的

private static Random _Rng = new Random();
public static Broker GetBroker(List<Broker> brokers){
    List<Broker> weightedBrokerList = new List<Broker>();
    foreach(Broker broker in brokers) {
        for(int i=0;i<broker.Weight;i++) {
            weightedBrokerList.Add(broker);
        }
    }
    return weightedBrokerList[_Rng.Next(weightedBrokerList.Count)];
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接