Случайный взвешенный выбор
https://stackoverflow.com/questions/56692
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Рассмотрим приведенный ниже класс, представляющий Брокера:
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<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, и они имеют одинаковый вес.
Есть ли более точный алгоритм?
Спасибо!
Решение
Ваш алгоритм почти верен.Однако тест должен быть < вместо того, чтобы <=:
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 = 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));
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; }
}
Альтернативный метод отдает предпочтение скорости при выборе брокера, а не использованию памяти.По сути, мы создаем список, содержащий такое же количество ссылок на экземпляр брокера, как и указанный вес.
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];
Поскольку это лучший результат в Google:
Я создал библиотека C # для случайно выбранных взвешенных элементов.
- Он реализует как алгоритмы выбора дерева, так и метод псевдонимов walker, чтобы обеспечить наилучшую производительность для всех вариантов использования.
- Он прошел модульное тестирование и оптимизирован.
- Он имеет поддержку 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.
Если вы хотите увеличить скорость, вы можете либо рассмотреть возможность взвешенного отбора проб из резервуара, где вам не нужно заранее определять общий вес (но вы чаще проводите отбор проб с помощью генератора случайных чисел).Код может выглядеть примерно так
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 за лог (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 <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
Реализация в исходном вопросе кажется мне немного странной;
Общий вес списка равен 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}");
}
}
}
