c# - 从数组中随机选择特定数量的索引？

Question

我有一个 bool 值数组，需要为 true 的值随机选择特定数量的索引。

生成索引数组的最有效方法是什么？

例如，

BitArray mask = GenerateSomeMask(length: 100000);
int[] randomIndices = RandomIndicesForTrue(mask, quantity: 10);

在这种情况下，randomIndices 的长度将为 10。

Answer 1

有一种更快的方法可以做到这一点，只需要对列表进行一次扫描。

当您不知道文件中有多少行并且文件太大而无法放入内存时，请考虑从文本文件中随机选择一行。显而易见的解决方案是读取文件一次以计算行数，在 0 到 Count-1 范围内选择一个随机数，然后再次读取文件直到选择的行数。这可行，但需要您读取文件两次。

更快的解决方案是读取第一行并将其保存为选定行。您以 1/2 的概率用下一行替换所选行。当您阅读第三行时，您以 1/3 的概率替换，等等。当您阅读整个文件时，您随机选择了一行，并且每一行被选中的概率均等。代码看起来像这样:

string selectedLine = null;
int numLines = 0;
Random rnd = new Random();
foreach (var line in File.ReadLines(filename))
{
    ++numLines;
    double prob = 1.0/numLines;
    if (rnd.Next() >= prob)
        selectedLine = line;
}

现在，如果你想选择 2 行怎么办？你选择前两个。然后，当读取每一行时，它将替换两行之一的概率是 2/n，其中 n 是已读取的行数。如果确定需要替换一条线，则随机选择要替换的线。您可以按照相同的基本思路随机选择任意数量的行。例如:

string[] selectedLines = new int[M];
int numLines = 0;
Random rnd = new Random();
foreach (var line in File.ReadLines(filename))
{
    ++numLines;
    if (numLines <= M)
    {
        selectedLines[numLines-1] = line;
    }
    else
    {
        double prob = (double)M/numLines;
        if (rnd.Next() >= prob)
        {
            int ix = rnd.Next(M);
            selectedLines[ix] = line;
        }
    }
}

您可以很容易地将其应用于您的 BitArray:

int[] selected = new int[quantity];
int num = 0;  // number of True items seen
Random rnd = new Random();
for (int i = 0; i < items.Length; ++i)
{
    if (items[i])
    {
        ++num;
        if (num <= quantity)
        {
            selected[num-1] = i;
        }
        else
        {
            double prob = (double)quantity/num;
            if (rnd.Next() > prob)
            {
                int ix = rnd.Next(quantity);
                selected[ix] = i;
            }
        }
    }
}

最后您需要一些特殊情况代码来处理数组中没有 quantity set 位的情况，但您需要使用任何解决方案。

这对 BitArray 进行了一次传递，它使用的唯一额外内存是用于选定索引的列表。如果它没有明显快于 LINQ 版本，我会感到惊讶。

请注意，我使用概率计算来说明数学。您可以将第一个示例中的内部循环代码更改为:

if (rnd.Next(numLines+1) == numLines)
{
    selectedLine = line;
}
++numLines;

您可以对其他示例进行类似的更改。这与概率计算的作用相同，并且应该执行得更快一些，因为它消除了每个项目的浮点除法。