给定一系列布尔值,选择随机TRUE值的索引的最有效方法是什么？

Question

你得到一个大小为n的数组,包含任意的布尔值.

返回随机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指出的那样,浮点比较最终将导致非常不均匀的选择.假设unit_random定义为rand() / RAND_MAX比较可以改为:

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

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