arrays - 给定一个 bool 数组，选择随机 TRUE 值的索引的最有效方法是什么？

Question

给定一个大小为 n 的数组，其中包含任意 bool 值。

返回随机 TRUE 值索引的最快方法是什么。

该算法应随机返回包含 TRUE 的任何一个索引。

Answer 1

像这样:

int count = 0;
int index = -1;
for (int i = 0; i != n; ++i)
{
    if (values[i])
    {
        ++count;
        if (unit_random <= 1.0f / count)
        {
            index = i;
        }
    }
}

因此，例如，对于 4 个值，您会得到它们的索引的以下概率:

1: (1 / 1) * (1 / 2) * (2 / 3) * (3 / 4) = 1 / 4 
2: (1 / 2) * (2 / 3) * (3 / 4) = 1 / 4
3: (1 / 3) * (3 / 4) = 1 / 4
4: 1 / 4 = 1 / 4

编辑: 正如 Steve Jessop 指出的那样， float 比较最终将导致非常不统一的选择。假设 unit_random 定义为 rand()/RAND_MAX 比较可以更改为:

typedef unsigned long long u64;
u64 product = u64(count) * rand();
if (product <= u64(RAND_MAX))

由于 rand 的离散性质，这不会给出完美的分布，但它会更好。