Elección ponderada aleatoria

Considere la siguiente clase que representa un 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; } } 

Me gustaría seleccionar aleatoriamente un Broker de una matriz, teniendo en cuenta sus pesos.

¿Qué piensas del código a continuación?

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

No estoy tan seguro. Cuando ejecuto esto, Broker A siempre obtiene más visitas que Broker D, y tienen el mismo peso.

¿Hay un algoritmo más preciso?

¡Gracias!

Tu algoritmo es casi correcto. Sin embargo, la prueba debe ser < lugar de <= :

 if (randomNumber < broker.Weight) 

Esto se debe a que 0 es inclusivo en el número aleatorio mientras que totalWeight es exclusivo. En otras palabras, un corredor con peso 0 aún tendría una pequeña posibilidad de ser seleccionado, no del todo lo que usted desea. Esto explica que el corredor A tenga más visitas que el corredor D.

Aparte de eso, su algoritmo está bien y, de hecho, es la manera canónica de resolver este problema.

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

¿Qué tal algo un poco más genérico, que se puede utilizar para cualquier tipo de datos?

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

Simplemente llame por

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

Un método alternativo favorece la velocidad al seleccionar el agente sobre el uso de la memoria. Básicamente, creamos la lista que contiene el mismo número de referencias a una instancia de agente como el peso especificado.

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

Luego, para seleccionar una instancia ponderada aleatoriamente, se realiza una operación O (1):

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

Si desea más velocidad, puede considerar el muestreo ponderado de yacimientos donde no tiene que encontrar el peso total antes de tiempo (pero toma muestras más a menudo del generador de números aleatorios). El código puede parecerse a algo

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

Esto requiere pasar una vez por la lista de agentes. Sin embargo, si la lista de intermediarios es fija o no cambia con tanta frecuencia, puede mantener un conjunto de sums acumulativas, es decir, A [i] es la sum de los pesos de todos los intermediarios 0, ..., i-1. Entonces A [n] es el peso total y si elige un número entre 1 y A [n-1], digamos x, encuentra el intermediario j st A [j-1] <= x

He encontrado una versión genérica de esta solución:

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

Dado que este es el resultado principal en Google:

Creé una biblioteca C # para elementos ponderados seleccionados al azar .

  • Implementa los algoritmos de método de selección de árbol y alias walker, para ofrecer el mejor rendimiento para todos los casos de uso.
  • Está probado y optimizado por unidades.
  • Tiene soporte LINQ.
  • Es gratis y de código abierto, con licencia bajo la licencia de MIT.

Un código de ejemplo:

 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. 

Solo para compartir mi propia implementación. Espero que lo encuentres útil.

  // 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