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

我正在尝试编写一个程序来从 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 行对数据结构产生影响，我将只使用它。

我曾尝试查看有关加权随机性的其他一些问题，但在将理论转化为代码时遇到了一些麻烦。我对数学理论知之甚少，所以我不知道这是否是“有替换或无替换”的随机选择，我希望同一个名字能够出现不止一次，无论是哪个意思。

最佳答案

处理此问题的“最简单”方法是将其保留在列表中。

然后你可以使用:

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

关于c# - 从加权列表中随机选择一个项目，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7366838/