भारित सूची

Question

से एक यादृच्छिक आइटम का चयन करें मैं US Census last name list से यादृच्छिक नाम चुनने के लिए एक प्रोग्राम लिखने की कोशिश कर रहा हूं। सूची प्रारूप

Name   Weight Cumulative line 
-----   ----- -----  - 
SMITH   1.006 1.006  1 
JOHNSON  0.810 1.816  2 
WILLIAMS  0.699 2.515  3 
JONES   0.621 3.136  4 
BROWN   0.621 3.757  5 
DAVIS   0.480 4.237  6 

मान लिया जाये कि मैं की तरह

Class Name 
{ 
    public string Name {get; set;} 
    public decimal Weight {get; set;} 
    public decimal Cumulative {get; set;} 
} 

एक संरचना करने के लिए डेटा लोड क्या डेटा संरचना सबसे अच्छा होगा नामों की सूची धारण करने के लिए, और क्या सबसे अच्छा तरीका चयन करने के लिए होगा सूची से यादृच्छिक नाम है लेकिन नामों का वितरण वास्तविक दुनिया जैसा ही है।

यदि डेटा संरचना में कोई फर्क पड़ता है तो मैं केवल पहली 10,000 पंक्तियों के साथ काम कर रहा हूं।

मैंने भारित यादृच्छिकता के बारे में कुछ अन्य प्रश्नों को देखने का प्रयास किया है, लेकिन मुझे सिद्धांत में कोड को बदलने में कुछ परेशानी हो रही है। मुझे गणित सिद्धांत के बारे में बहुत कुछ नहीं पता है, इसलिए मुझे नहीं पता कि यह "यादृच्छिक चयन के साथ या बिना किसी प्रतिस्थापन" है, मैं चाहता हूं कि वही नाम एक से अधिक बार प्रदर्शित हो सके, जिसका अर्थ है कि इसका मतलब है।

Answer 1

इसे संभालने का सबसे आसान तरीका यह सूची में रखना होगा।

फिर आप सिर्फ इस्तेमाल कर सकते हैं:

Name GetRandomName(Random random, List<Name> names) 
{ 
    double value = random.NextDouble() * names[names.Count-1].Culmitive; 
    return names.Last(name => name.Culmitive <= value); 
} 

गति चिंता का विषय है, तो आप बस Culmitive मूल्यों का एक अलग सरणी स्टोर कर सकते हैं। इस के साथ, आप Array.BinarySearch इस्तेमाल कर सकते हैं जल्दी से उचित सूचकांक को खोजने के लिए:

Name GetRandomName(Random random, List<Name> names, double[] culmitiveValues) 
{ 
    double value = random.NextDouble() * names[names.Count-1].Culmitive; 
    int index = Array.BinarySearch(culmitiveValues, value); 
    if (index >= 0) 
     index = ~index; 

    return names[index]; 
} 

एक अन्य विकल्प है, जो शायद सबसे कारगर है, में से एक की तरह कुछ का उपयोग करने के होगा C5 Generic Collection Library के tree classes। उचित नाम खोजने के लिए आप RangeFrom का उपयोग कर सकते हैं। इसका एक अलग संग्रह की आवश्यकता नहीं है

Answer 2

मैं एक सरणी कहूंगा (वैक्टर यदि आप चाहें तो) उन्हें पकड़ने के लिए सबसे अच्छा होगा। भारित औसत के लिए, राशि पाएं, शून्य और योग के बीच एक यादृच्छिक संख्या चुनें, और अंतिम नाम चुनें जिसका संचयी मान कम है। (यहां जैसे, < 1.006 = स्मिथ, 1.006-1.816 = जॉनसन, आदि

पुनश्च यह संचयी है

Answer 3

बस मस्ती के लिए

, और कोई रास्ता नहीं इष्टतम

List<Name> Names = //Load your structure into this 

List<String> NameBank = new List<String>(); 
foreach(Name name in Names) 
    for(int i = 0; i <= (int)(name.Weight*1000); i++) 
    NameBank.Add(name.Name) 

तो में:।

String output = NameBank[rand(NameBank.Count)]; 

Answer 4

मैं 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.