Случайный взвешенный выбор

Ваш алгоритм почти верен. Однако тест должен быть < вместо <=:

if (randomNumber < broker.Weight)

Это потому, что 0 включается в случайное число, а totalWeight исключает. Другими словами, брокер с весом 0 все равно будет иметь небольшой шанс быть выбранным - совсем не то, что вы хотите. Это учитывает, что у брокера A больше обращений, чем у брокера D.

В остальном ваш алгоритм хорош и фактически является каноническим способом решения этой проблемы.

Как насчет чего-то более общего, которое можно использовать для любого типа данных?

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

Поскольку это лучший результат в Google:

Я создал библиотеку C # для случайно выбранных взвешенных элементов.

• Он реализует алгоритмы как выбора дерева, так и алгоритмы псевдонима обходчика, чтобы обеспечить наилучшую производительность для всех случаев использования.
• Он протестирован и оптимизирован.
• Имеет поддержку 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.

Альтернативный метод предпочитает скорость при выборе брокера использованию памяти. Обычно мы создаем список, содержащий то же количество ссылок на экземпляр брокера, что и указанный вес.

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

Слишком поздно, но вот пример 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;
    }
}

Если вам нужна более высокая скорость, вы можете рассмотреть выборку взвешенного резервуара, когда вам не нужно заранее определять общий вес (но вы чаще выполняете выборку из генератора случайных чисел). Код может выглядеть примерно так

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 s.t. A [j-1] ‹= x‹ A [j]. Для удобства вы положите A [0] = 0. Вы можете найти этот брокер номер j в log (n) шагах с помощью двоичного поиска, я оставлю код в качестве простого упражнения. Если ваши данные часто меняются, это может быть не лучшим вариантом, поскольку каждый раз при изменении веса вам может потребоваться обновить большую часть массива.

Я придумал общую версию этого решения:

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

Просто чтобы поделиться своей собственной реализацией. Надеюсь, вы найдете это полезным.

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

Суть: https://gist.github.com/MrBogomips/ae6f6c9af8032392e4b93aaa393df447

Реализация в исходном вопросе кажется мне немного странной;

Общий вес списка равен 60, поэтому случайное число - от 0 до 59. Он всегда сравнивает случайное число с весом, а затем уменьшает его. Мне кажется, что он будет отдавать предпочтение вещам в списке в зависимости от их порядка.

Вот общая реализация, которую я использую - суть в свойстве 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}");
        }
    }
}