c# - 从加权列表中选择一个随机项目

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 找到合适的名称。这具有不需要单独收集的优点