Ağırlıklı bir listeden rastgele bir öğe seçin

Question

US Census last name list'dan rastgele bir ad seçmek için bir program yazmaya çalışıyorum. Liste biçimi

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 

Ben adlarının listesini tutmak için iyi olurdu hangi veri yapısı

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

gibi bir yapıya veri yüklemek varsayarsak ve ne seçmek için en iyi yol olacağını ise listeden rastgele bir isim ama isimlerin dağılımı gerçek dünya ile aynı olsun. veri yapısında bir değişiklik olup olmadığını

Ben sadece ilk 10.000 satır çalışıyor olacağız.

Ben ağırlıklı rastgelelik hakkında diğer sorulardan bazıları bakarak çalıştı ama ben koduna içinde teoriyi dönüm sorun biraz yaşıyorum. Matematik teorisi hakkında pek bir şey bilmiyorum, bu yüzden "Değişim olsun ya da olmasın" rastgele seçim olup olmadığını bilmiyorum, aynı adı bir kereden fazla göstermeyi istiyorum, ki bu hiç bir anlama gelmez.

Answer 1

Bunu işlemenin "en kolay" yolu bunu bir listede tutmak olabilir.

Daha sonra sadece kullanabilirsiniz: Hızlı bir sorun olacaksa

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

, sadece Culmitive değerlerinin ayrı dizi depolayabilir. Bu, hızlı bir şekilde uygun dizin bulmak için Array.BinarySearch kullanabilirsiniz:

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

muhtemelen en verimli Başka bir seçenek, biri gibi bir şey kullanmak olacaktır C5 Generic Collection Library 'ın tree classes. Uygun adı bulmak için RangeFrom'u kullanabilirsiniz. Bu benim bir dizi söyleyebilirim ayrı koleksiyon

Answer 2

gerektirmeyen bir avantaja sahiptir (vektörler isterseniz) onları tutmak için iyi olurdu. Ağırlıklı ortalamaya gelince, toplamı bulun, sıfır ile toplam arasında rastgele bir sayı seçin ve kümülatif değeri daha az olan soyadı seçin. . (Örneğin burada, < 1,006 = smith, 1,006-1,816 = Johnson, vb

PS Sadece eğlence için

Answer 3

Kümülatif, ve

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) 

sonra optimum hiçbir şekilde:

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

Answer 4

Ben a C# library for randomly selected weighted items oluşturduk.

• Tüm kullanım durumları için en iyi performansı vermek için ağaç seçimi ve yürüteç takma ad algoritmaları uygular.
• Birim test edilmiş ve optimize edilmiştir.
• LINQ desteğine sahiptir.
• MIT lisansı kapsamında ücretsiz ve açık kaynaklı, lisanslıdır.

Bazı örnek kod: düğümlerde Adları ile dengeli bir ikili ağaçta

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.