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

Рассмотрим приведенный ниже class, представляющий брокера:

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

Я хотел бы случайным образом выбрать Брокер из массива с учетом их веса.

Что вы думаете о коде ниже?

 class Program { private static Random _rnd = new Random(); public static Broker GetBroker(List 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 brokers = new List(); 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 result = new Dictionary(); 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(); } } } 

Я не уверен. Когда я запускаю это, Broker A всегда получает больше хитов, чем Broker D, и они имеют одинаковый вес.

Есть ли более точный алгоритм?

Благодаря!

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

 if (randomNumber < broker.Weight) 

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

Кроме этого, ваш алгоритм прекрасен и на самом деле является каноническим способом решения этой проблемы.

 class Program { static void Main(string[] args) { var books = new List { 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(List 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; } } 

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

 using System; using System.Linq; using System.Collections; using System.Collections.Generic; public static class IEnumerableExtensions { public static T RandomElementByWeight(this IEnumerable sequence, Func 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); } } 

Просто позвоните

  Dictionary foo = new Dictionary(); 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)); 

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

 List brokers = new List(); 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]; 

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

 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 st A [j-1] <= x

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

 public static class WeightedEx { ///  /// Select an item from the given sequence according to their respective weights. ///  /// Type of item item in the given sequence. /// Given sequence of weighted items. /// Randomly picked item. public static TItem PickWeighted(this IEnumerable 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; } } } } ///  /// IWeighted: Implementation of an item that is weighted. ///  public interface IWeighted { double Weight { get; } } 

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

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

  • Он реализует алгоритмы алгоритма выбора дерева и алгоритма walker alias, чтобы обеспечить максимальную производительность для всех случаев использования.
  • Он тестируется и оптимизирован.
  • Он поддерживает LINQ.
  • Он бесплатный и с открытым исходным кодом, лицензированный по лицензии MIT.

Пример кода:

 IWeightedRandomizer randomizer = new DynamicWeightedRandomizer(); 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. 

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

  // Author: Giovanni Costagliola  using System; using System.Collections.Generic; using System.Linq; namespace Utils { ///  /// Represent a Weighted Item. ///  public interface IWeighted { ///  /// A positive weight. It's up to the implementer ensure this requirement ///  int Weight { get; } } ///  /// Pick up an element reflecting its weight. ///  ///  public class RandomWeightedPicker where T:IWeighted { private readonly IEnumerable items; private readonly int totalWeight; private Random random = new Random(); ///  /// Initiliaze the structure. O(1) or O(n) depending by the options, default O(n). ///  /// The items /// If true will check that the weights are positive. O(N) /// If true will copy the original collection structure (not the items). Keep in mind that items lifecycle is impacted. public RandomWeightedPicker(IEnumerable 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(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); } ///  /// Pick a random item based on its chance. O(n) ///  /// The value returned in case the element has not been found ///  public T PickAnItem() { int rnd = random.Next(totalWeight); return items.First(i => (rnd -= i.Weight) < 0); } ///  /// Resets the internal random generator. O(1) ///  ///  public void ResetRandomGenerator(int? seed) { random = seed.HasValue ? new Random(seed.Value) : new Random(); } } } 

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

  • Почему class System.Random не статичен?
  • Как работают модуль и rand ()?
  • Создание случайных чисел в массиве
  • Не повторяющиеся случайные числа
  • Случайные / шумовые функции для GLSL
  • Почему rand () дает одну и ту же последовательность чисел при каждом запуске?
  • Причины использования функции set.seed
  • Java: случайное длинное число в диапазоне 0 <= x <n
  • Те же случайные числа каждый раз, когда я запускаю программу
  • Создание генератора случайных чисел из броска монеты
  • Порт генератора случайных чисел от C до Java?
  • Interesting Posts

    Падение базы данных postgresql через командную строку

    Что загружает загрузчик classов java?

    Как проверить, существует ли папка

    Что означает «Наибольшее активное время» для активности диска в мониторе ресурсов Windows?

    Исключение «Исключительная привязка к реляционной ссылке» с JSON.Net

    AngularJS – функция перехода к директиве

    BSOD на ноутбуке Vista (работает безопасный режим) – мысли и подходы?

    Иконка уведомления с новой системой обмена облаками Firebase

    Как заставить проверку формы html5 без отправки ее через jQuery

    Отправить встроенное изображение по электронной почте

    Как игнорировать команды xargs, если вход stdin пуст?

    На моем ПК не работает ни средство просмотра событий, ни планировщик заданий

    Как правильно управлять закрытым ключом

    Список привязок к списку

    Aptitude vs. apt-get: Какой из рекомендованных (так называемых «правильных») инструментов использовать?

    Давайте будем гением компьютера.