c++ - 生成随机位 vector 的最快方法是什么？

Question

我有以下问题。假设我想生成一个 std::vector<bool> , 或 std::vector<unsigned int> ，甚至是只包含 0 和 1 的 C 风格数组，均匀分布(即，在每次运行时应该有类似 0110 或 1011 的东西，你明白了)。有两种方法:

1. 使用 std::uniform_int_distribution(0,1) 生成每个元素
2. 生成一个介于0之间的随机整数和 2^n-1 (其中 n 是位数)，然后使用 bitset<n>

我在这里谈论大 vector ，并做了一些计时但没有得到任何清晰的见解。

有谁知道哪种方法效率更高？在我看来，第二种方法应该更好，但我不相信。

Answer 1

如果性能是一个问题并且您的输出集需要很大，我会跳过 vector 。虽然紧凑，但它们访问单个成员的性能较低。

要么使用 std::vector<unsigned int>并调用.resize(N)在它上面以确保它足够大，或者通过 malloc 分配一个 C 风格的数组。如果您使用 [index] 访问，其中任何一个都将具有高性能访问权限。

其次，获得你自己的随机数生成器，许多系统的随机数生成器都很糟糕。例如MSVC 使用 LCG，尽管右移了 16 位。即便如此，http://en.wikipedia.org/wiki/Linear_congruential_generator请注意，如果您真的很在意，应该避免使用它们。我的建议是 Xor-Shift RNG，因为它 (A) 快得令人眼花缭乱，并且 (B) 由 George Marsaglia 设计，他是一位 RNG 专家。

另一个优势是，与 MSVC rand() 相比，您可以让自己的 RNG 每次调用返回一个完整的 32 位无符号整数。可能还有其他每次调用只提供 15 位的。因此，您将调用两倍以上的电话 rand()就像您对自己的发电机一样。

要实际填充数组，您需要执行以下操作:

void fillarray(unsigned int *data, unsigned int count)
{
    unsigned int randomValue;
    for (int index = 0; index < count; index++)
    {
        if ((index & 31) == 0)
        {
            randomValue = nextRandom();
        }
        data[index] = randomValue & 1;
        randomValue >>= 1;
    }
}