从加权列表中选择一个随机项

Question

我正在尝试编写一个程序,从美国人口普查姓氏列表中选择一个随机名称.列表格式是

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通用集合库的树类之一.然后,您可以使用它RangeFrom来查找适当的名称.这具有不需要单独收集的优点