रैंडम भारित पसंद

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

मैं इतना आत्मविश्वास नहीं हूं। जब मैं इसे चलाता हूं, ब्रोकर ए को ब्रोकर डी की तुलना में हमेशा अधिक हिट मिलती है, और उनके पास वही वज़न होता है।

वहाँ एक और अधिक सटीक एल्गोरिथ्म है?

धन्यवाद!

Answer 1

आपका एल्गोरिथ्म लगभग सही है। हालांकि, परीक्षण < बजाय <= होना चाहिए:

if (randomNumber < broker.Weight) 

यह जबकि totalWeight विशेष है क्योंकि 0 यादृच्छिक संख्या में समावेशी है। दूसरे शब्दों में, वजन 0 वाले ब्रोकर के पास अभी भी चयन करने का एक छोटा सा मौका होगा - जो भी आप चाहते हैं। यह दलाल एक दलाल डी से अधिक हिट

उसके अलावा होने के लिए खातों, अपने एल्गोरिथ्म ठीक है और वास्तव में इस समस्या के हल के लिए विहित तरीका है। जब स्मृति के उपयोग से अधिक दलाल का चयन

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

फिर, एक बेतरतीब ढंग से भारित उदाहरण चयन करने के लिए एक हे (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; 
    } 
} 

जैसे कुछ दिख सकता है, इसे सूची दलालों के माध्यम से एक बार जाना आवश्यक है। हालांकि यदि दलालों की सूची तय की जाती है या अक्सर बदलती नहीं है तो आप संचयी रकम की एक श्रृंखला रख सकते हैं, यानी ए [i] सभी ब्रोकर 0, .., i-1 के वजन का योग है। फिर ए [एन] कुल वजन है और यदि आप 1 और ए [एन -1] के बीच कोई संख्या चुनते हैं, तो एक्स कहें कि आपको ब्रोकर जे एसटी मिलती है। ए [जे -1] < = एक्स < ए [जे]। सुविधा के लिए आप ए [0] = 0. दें। आप इस ब्रोकर नंबर जे को बाइनरी खोज का उपयोग करके लॉग (एन) चरणों में पा सकते हैं, मैं कोड को एक आसान अभ्यास के रूप में छोड़ दूंगा। यदि आपका डेटा बार-बार बदलता है तो यह हर बार कुछ वज़न बदलने के बाद से जाने का एक अच्छा तरीका नहीं हो सकता है, आपको सरणी के बड़े हिस्से को अपडेट करने की आवश्यकता हो सकती है।

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

कैसे कुछ और भी अधिक सामान्य, कि किसी भी डेटा प्रकार के लिए इस्तेमाल किया जा सकता है?

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

फोन के बाद से इस गूगल पर शीर्ष परिणाम है:

मैं a C# library for randomly selected weighted items बना लिया है।

• यह सभी उपयोग-मामलों के लिए सर्वश्रेष्ठ प्रदर्शन देने के लिए पेड़ चयन और वॉकर उपनाम विधि एल्गोरिदम दोनों लागू करता है।
• यह इकाई परीक्षण और अनुकूलित है।
• इसमें LINQ समर्थन है।
• यह मुफ़्त और ओपन-सोर्स है, जो एमआईटी लाइसेंस के तहत लाइसेंस प्राप्त है।

कुछ उदाहरण कोड:

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