ランダム加重選択

Question

は、以下のクラスは、ブローカーを表して考えてみましょう：

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よりも多くのヒットを得て、同じ重量を持っています。

もっと正確なアルゴリズムはありますか？

ありがとうございます！

Answer 1

あなたのアルゴリズムはほぼ正しいです。しかし、テストは<の代わり<=する必要があります：

if (randomNumber < broker.Weight) 

totalWeightが排他的である一方、0は乱数で包括的であるためです。言い換えれば、ウェイト0のブローカーはまだ選択されている可能性が低く、あなたが望むものではありません。これは、ブローカーAがブローカーDより多くのヒットを有することを説明しています。

それ以外は、このアルゴリズム以外はこの問題を解決する標準的な方法です。

Answer 2

ブローカのメモリ使用量を選択するときは、速度を優先する方法があります。基本的には、指定された重みとしてブローカインスタンスへの参照数と同じ数の参照を含むリストを作成します。ランダムに重み付けされたインスタンスを選択する

その後

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

Answer 3

あなたはもっとスピードが必要な場合、あなたは見つけることはありません加重貯留サンプリングを考慮しますか前回の総重量（ただし、乱数ジェネレータからより頻繁にサンプリングします）。コードは次のようになります

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としましょう。バイナリ検索を使用してlog（n）ステップでこのブローカー番号jを見つけることができます。コードを簡単な練習として残します。データが頻繁に変更された場合は、重みの変更があるたびにアレイの大部分を更新する必要が生じる可能性があるため、これは良い方法ではない可能性があります。

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

私は、このソリューションのジェネリック版を作ってみた：

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

どのように任意のデータ型に使用することができ、もう少し一般的な何か、どうですか？私はa C# library for randomly selected weighted itemsを作成しました

：これはGoogleで上位の結果であるので

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

Answer 7

で呼び出します。

• すべてのユースケースに対して最高のパフォーマンスを提供するために、ツリー選択とウォークエイリアスの両方のメソッドアルゴリズムを実装しています。
• ユニットテスト済みで最適化されています。
• 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. 

Answer 8

ちょうど私の独自の実装を共有します。あなたはそれが役に立つと思うことを願っています。

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