从加权列表中选择一个随机项
我正在尝试编写一个程序，从美国人口普查姓氏列表中选择一个随机名称。 列表格式是
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行。
我已经尝试过关于加权随机性的其他一些问题但我在将理论转化为代码时遇到了一些麻烦。 我对数学理论知之甚少，所以我不知道这是一个“有或没有替代”的随机选择，我希望同名能够不止一次出现，这就是那个意思。
处理此问题的“最简单”方法是将其保留在列表中。
然后你可以使用：
Name GetRandomName(Random random, List 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 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通用集合库的树类之一 。 然后，您可以使用RangeFrom查找适当的名称。 这具有不需要单独收集的优点
我为随机选择的加权项创建了一个C＃库 。
- 它实现了树选择和walker别名方法算法，以便为所有用例提供最佳性能。
- 它经过unit testing和优化。
- 它有LINQ支持。
- 它是免费和开源的，根据MIT许可证授权。
一些示例代码：
IWeightedRandomizer randomizer = new DynamicWeightedRandomizer (); 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.
我会说一个数组（如果你愿意，可以使用矢量）最好保留它们。 对于加权平均值，找到总和，在零和总和之间选择一个随机数，然后选择累计值较小的姓氏。 （例如，<1.006 =史密斯，1.006-1.816 =约翰逊等
PS它是累积的。
只是为了好玩，绝不是最佳选择
List Names = //Load your structure into this List NameBank = new List (); 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)];