Escolha ponderada aleatória
https://stackoverflow.com/questions/56692
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Considere a classe abaixo que representa um 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;
}
}
Gostaria de selecionar aleatoriamente um Broker de um array, levando em consideração seus pesos.
O que você acha do código abaixo?
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();
}
}
}
Não estou tão confiante.Quando executo isso, o Corretor A sempre obtém mais resultados do que o Corretor D, e eles têm o mesmo peso.
Existe um algoritmo mais preciso?
Obrigado!
Solução
Seu algoritmo está quase correto.Contudo, o teste deve ser < em vez de <=:
if (randomNumber < broker.Weight)
Isso ocorre porque 0 é inclusivo no número aleatório enquanto totalWeight é exclusivo.Em outras palavras, uma corretora com peso 0 ainda teria uma pequena chance de ser selecionada – não exatamente o que você deseja.Isso faz com que o corretor A tenha mais acessos do que o corretor D.
Fora isso, seu algoritmo está bom e de fato é a forma canônica de resolver esse problema.
Outras dicas
Que tal algo um pouco mais genérico, que possa ser usado para qualquer tipo de dados?
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);
}
}
Basta ligar por
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; }
}
Um método alternativo favorece a velocidade ao selecionar o corretor em vez do uso de memória.Basicamente criamos a lista contendo o mesmo número de referências a uma instância do corretor que o peso especificado.
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));
Então, para selecionar uma instância ponderada aleatoriamente é uma operação O(1):
int randomNumber = _rnd.Next(0, brokers.length);
selectedBroker = brokers[randomNumber];
Como este é o principal resultado do Google:
eu criei uma biblioteca C# para itens ponderados selecionados aleatoriamente.
- Ele implementa os algoritmos do método de seleção de árvore e de alias do walker, para fornecer o melhor desempenho para todos os casos de uso.
- É testado em unidade e otimizado.
- Possui suporte a LINQ.
- É gratuito e de código aberto, licenciado sob a licença MIT.
Alguns exemplos de código:
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.
Se você quiser mais velocidade, você pode considerar a amostragem ponderada de reservatórios, onde não é necessário encontrar o peso total antecipadamente (mas você amostra com mais frequência no gerador de números aleatórios).O código pode ser algo como
Broker selected = null;
int s = 0;
foreach(Broker broker in brokers) {
s += broker.Weight;
if (broker.Weight <= _rnd.Next(0,s)) {
selected = broker;
}
}
Isso requer passar uma vez pela lista de corretores.No entanto, se a lista de corretores for fixa ou não mudar com tanta frequência, você poderá manter uma série de somas cumulativas, ou seja,A[i] é a soma dos pesos de todas as corretoras 0,..,i-1.Então A[n] é o peso total e se você escolher um número entre 1 e A[n-1], digamos x você encontrará o corretor j s.t.A[j-1] <= x <A[j].Por conveniência, você deixa A[0] = 0.Você pode encontrar esse número de corretor j em etapas de log(n) usando pesquisa binária, deixarei o código como um exercício fácil.Se seus dados mudam com frequência, esse pode não ser um bom caminho, pois sempre que algum peso muda, pode ser necessário atualizar uma grande parte do array.
Eu criei uma versão genérica desta solução:
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; }
}
Apenas para compartilhar minha própria implementação.Espero que você ache útil.
// 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();
}
}
}
Essência: https://gist.github.com/MrBogomips/ae6f6c9af8032392e4b93aaa393df447
A implementação na pergunta original me parece um pouco estranha;
O peso total da lista é 60, então o número aleatório é de 0 a 59.Ele sempre verifica o número aleatório em relação ao peso e depois o diminui.Parece-me que isso favoreceria as coisas da lista com base na sua ordem.
Aqui está uma implementação genérica que estou usando - o ponto crucial está na propriedade 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}");
}
}
}
