C# 随机加权选择

Random weighted choice

提问by LeoD

Consider the class below that represents a Broker:

考虑下面代表 Broker 的类：

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

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

I'd like to randomly select a Broker from an array, taking into account their weights.

我想从数组中随机选择一个 Broker，同时考虑到它们的权重。

What do you think of the code below?

你觉得下面的代码怎么样？

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

I'm not so confident. When I run this, Broker A always gets more hits than Broker D, and they have the same weight.

我没那么自信。当我运行这个时，Broker A 总是比 Broker D 获得更多的点击，并且它们具有相同的权重。

Is there a more accurate algorithm?

有没有更准确的算法？

Thanks!

谢谢！

采纳答案by Konrad Rudolph

Your algorithm is nearly correct. However, the test should be <instead of <=:

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

if (randomNumber < broker.Weight)

This is because 0 is inclusive in the random number while totalWeightis exclusive. In other words, a broker with weight 0 would still have a small chance of being selected –?not at all what you want. This accounts for broker A having more hits than broker D.

这是因为 0 包含在随机数中，但totalWeight不包含。换句话说，权重为 0 的经纪人仍然有很小的机会被选中——根本不是你想要的。这说明了经纪人 A 的点击次数比经纪人 D 多。

Other than that, your algorithm is fine and in fact the canonical way of solving this problem.

除此之外，您的算法很好，实际上是解决此问题的规范方法。

回答by 1800 INFORMATION

An alternative method favours speed when selecting the broker over memory usage. Basically we create the list containing the same number of references to a broker instance as the specified weight.

在选择代理而不是内存使用时，另一种方法有利于速度。基本上，我们创建的列表包含与指定权重相同数量的代理实例引用。

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

Then, to select a randomly weighted instance is an O(1) operation:

然后，选择一个随机加权的实例是一个 O(1) 操作：

int randomNumber = _rnd.Next(0, brokers.length);
selectedBroker = brokers[randomNumber];

回答by 1800 INFORMATION

If you want more speed you can either consider weighted reservtheitroad sampling where you don't have to find the total weight ahead of time (but you sample more often from the random number generator). The code might look something like

如果您想要更快的速度，您可以考虑加权储层采样，您不必提前找到总重量（但您更频繁地从随机数生成器中采样）。代码可能看起来像

Broker selected = null;
int s = 0;
foreach(Broker broker in brokers) {
    s += broker.Weight;
    if (broker.Weight <= _rnd.Next(0,s)) {
        selected = broker;
    }
}

This requires going once through the list brokers. However if the list of brokers is fixed or doesn't change that often you can keep an array of cumulative sums, i.e. A[i] is the sum of weights of all brokers 0,..,i-1. Then A[n] is the total weight and if you pick a number between 1 and A[n-1], say x you find the broker j s.t. A[j-1] <= x < A[j]. For convenience you let A[0] = 0. You can find this broker number j in log(n) steps using binary search, I'll leave the code as an easy exercise. If your data changes frequently this might not be a good way to go since every time some weight changes you might need to update a large portion of the array.

这需要通过列表经纪人一次。但是，如果经纪人列表是固定的或不经常更改，您可以保留一组累积总和，即 A[i] 是所有经纪人 0,..,i-1 的权重总和。那么 A[n] 是总重量，如果你在 1 和 A[n-1] 之间选择一个数字，假设 x 你找到经纪人 j st A[j-1] <= x < A[j]。为方便起见，您让 A[0] = 0。您可以使用二分搜索在 log(n) 步中找到此代理编号 j，我将代码留作简单练习。如果您的数据频繁更改，这可能不是一个好方法，因为每次权重发生变化时，您可能需要更新数组的很大一部分。

回答by Cagatay

class Program
{
    static void Main(string[] args)
    {
        var books = new List<Book> {
        new Book{Isbn=1,Name="A",Weight=1},
        new Book{Isbn=2,Name="B",Weight=100},
        new Book{Isbn=3,Name="C",Weight=1000},
        new Book{Isbn=4,Name="D",Weight=10000},
        new Book{Isbn=5,Name="E",Weight=100000}};

        Book randomlySelectedBook = WeightedRandomization.Choose(books);
    }
}

public static class WeightedRandomization
{
    public static T Choose<T>(List<T> list) where T : IWeighted
    {
        if (list.Count == 0)
        {
            return default(T);
        }

        int totalweight = list.Sum(c => c.Weight);
        Random rand = new Random();
        int choice = rand.Next(totalweight);
        int sum = 0;

        foreach (var obj in list)
        {
            for (int i = sum; i < obj.Weight + sum; i++)
            {
                if (i >= choice)
                {
                    return obj;
                }
            }
            sum += obj.Weight;
        }

        return list.First();
    }
}

public interface IWeighted
{
    int Weight { get; set; }
}

public class Book : IWeighted
{
    public int Isbn { get; set; }
    public string Name { get; set; }
    public int Weight { get; set; }
}

回答by Jordan

I've come up with a generic version of this solution:

我想出了这个解决方案的通用版本：

public static class WeightedEx
{
    /// <summary>
    /// Select an item from the given sequence according to their respective weights.
    /// </summary>
    /// <typeparam name="TItem">Type of item item in the given sequence.</typeparam>
    /// <param name="a_source">Given sequence of weighted items.</param>
    /// <returns>Randomly picked item.</returns>
    public static TItem PickWeighted<TItem>(this IEnumerable<TItem> a_source)
        where TItem : IWeighted
    {
        if (!a_source.Any())
            return default(TItem);

        var source= a_source.OrderBy(i => i.Weight);

        double dTotalWeight = source.Sum(i => i.Weight);

        Random rand = new Random();

        while (true)
        {
            double dRandom = rand.NextDouble() * dTotalWeight;

            foreach (var item in source)
            {
                if (dRandom < item.Weight)
                    return item;

                dRandom -= item.Weight;
            }
        }
    }
}

/// <summary>
/// IWeighted: Implementation of an item that is weighted.
/// </summary>
public interface IWeighted
{
    double Weight { get; }
}

回答by user1594818

How about something a little more generic, that can be used for any data type?

可以用于任何数据类型的更通用的东西怎么样？

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

    }

}

Simply call by

只需致电

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

回答by BlueRaja - Danny Pflughoeft

Since this is the top result on Google:

由于这是 Google 上的最佳结果：

I've created a C# library for randomly selected weighted items.

我为随机选择的加权项目创建了一个 C# 库。

• It implements both the tree-selection and walker alias method algorithms, to give the best performance for all use-cases.
• It is unit-tested and optimized.
• It has LINQ support.
• It's free and open-source, licensed under the MIT license.

• 它同时实现了树选择和 walker 别名方法算法，以便为所有用例提供最佳性能。
• 它经过单元测试和优化。
• 它具有 LINQ 支持。
• 它是免费和开源的，在 MIT 许可下获得许可。

Some example code:

一些示例代码：

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.

回答by Lord of the Goo

Just to share my own implementation. Hope you'll find it useful.

只是分享我自己的实现。希望你会发现它很有用。

    // Author: Giovanni Costagliola <[email protected]>

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

Gist: https://gist.github.com/MrBogomips/ae6f6c9af8032392e4b93aaa393df447

要点：https: //gist.github.com/MrBogomips/ae6f6c9af8032392e4b93aaa393df447

回答by user2796283

The implementation in the original question seems a little odd to me;

原始问题中的实现对我来说似乎有点奇怪；

The total weight of the list is 60 so the random number is 0-59. It always checks the random number against the weight and then decrements it. It looks to me that it would favour things in the list based on their order.

列表的总权重为 60，因此随机数为 0-59。它总是根据权重检查随机数，然后将其递减。在我看来，它会根据顺序支持列表中的内容。

Here's a generic implementation I'm using - the crux is in the Random property:

这是我正在使用的通用实现 - 症结在 Random 属性中：

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

public class WeightedList<T>
{
    private readonly Dictionary<T,int> _items = new Dictionary<T,int>();

    // Doesn't allow items with zero weight; to remove an item, set its weight to zero
    public void SetWeight(T item, int weight)
    {
        if (_items.ContainsKey(item))
        {
            if (weight != _items[item])
            {
                if (weight > 0)
                {
                    _items[item] = weight;
                }
                else
                {
                    _items.Remove(item);
                }

                _totalWeight = null; // Will recalculate the total weight later
            }
        }
        else if (weight > 0)
        {
            _items.Add(item, weight);

            _totalWeight = null; // Will recalculate the total weight later
        }
    }

    public int GetWeight(T item)
    {
        return _items.ContainsKey(item) ? _items[item] : 0;
    }

    private int? _totalWeight;
    public int totalWeight
    {
        get
        {
            if (!_totalWeight.HasValue) _totalWeight = _items.Sum(x => x.Value);

            return _totalWeight.Value;
        }
    }

    public T Random
    {
        get
        {
            var temp = 0;
            var random = new Random().Next(totalWeight);

            foreach (var item in _items)
            {
                temp += item.Value;

                if (random < temp) return item.Key;
            }

            throw new Exception($"unable to determine random {typeof(T)} at {random} in {totalWeight}");
        }
    }
}

回答by zhe

A little bit too late but here's C#7 example. It's pretty small and gives correct distribution.

有点晚了，但这里是 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;
    }
}