elección aleatoria ponderada

Question

en cuenta la clase de abajo 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 al azar a un corredor de una matriz, teniendo en cuenta sus pesos.

¿Qué opinas del código siguiente?

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

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!

Answer 1

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

if (randomNumber < broker.Weight) 

Esto se debe a 0 es incluido en el número al azar, mientras que totalWeight es exclusiva. 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 da cuenta de broker A que tiene más aciertos que corredor de D.

Aparte de eso, el algoritmo está muy bien y, de hecho, la forma canónica de la solución de este problema.

Answer 2

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

Luego, para seleccionar una instancia aleatoria ponderada es un O (1) operación:

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

Answer 3

Si quieres más velocidad se puede considerar ya sea muestreo depósito ponderada en la que no tiene que encontrar el peso total antes de tiempo (pero muestra más a menudo del generador de números aleatorios). El código podría ser algo así como

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 a través de los corredores de la lista. Sin embargo, si la lista de corredores es fijo o no cambia, que a menudo se puede mantener una serie de sumas acumulativas, es decir, A [i] es la suma de los pesos de todos los corredores de 0, .., i-1. Entonces A [n] es el peso total y si tienes que elegir un número entre 1 y A [n-1], digamos x se encuentra el agente j S.T. A [j-1] < = x < A [j]. Para mayor comodidad se deja a [0] = 0. Puede encontrar este número intermediario j en los pasos log (n) mediante la búsqueda binaria, dejaré el código como un ejercicio fácil. Si sus datos cambian con frecuencia, esta podría no ser una buena forma de hacerlo, ya que cada vez que cambie de peso es posible que deba actualizar una gran parte de la matriz.

Answer 4

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

Answer 5

Yo he llegado con una versión genérica de esta solució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; } 
} 

Answer 6

¿Qué tal algo un poco más genérico, que puede ser utilizado 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<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); 

    } 

} 

sólo tiene que llamar 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)); 

Answer 7

Dado que este es el primer resultado en Google:

He creado a C# library for randomly selected weighted items.

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

un código de ejemplo:

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. 

Answer 8

sólo para compartir mi propia aplicación. Espero que lo encuentres ú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(); 
     } 
    } 
} 

Síntesis: https://gist.github.com/MrBogomips/ae6f6c9af8032392e4b93aaa393df447