用于随机选择std :: vector的所有元素的有效方法,无需重新洗牌

Question

我正在寻找一种有效的方法来选择对std::vector<T>随机顺序中a的每个元素的访问,而不需要重新洗牌或复制它们,即不使用std::random_shuffle并确保每个元素只被选择一次.

我不想复制或重新洗牌,因为a)每个实例T都可能是一个非常大的对象,b)对于我将对矢量元素进行的其他操作,它们更容易保持相同订购.

此外,我真的不想走在不断挑选和拒绝重复的街道上.很可能我会在向量中存储大量这些大对象,效率很关键,因为我希望每秒多次调用这种随机选择方法.

Answer 1

创建一个与现有向量相同的向量,该向量使用指向向量中元素的指针.随机地改变指针向量并从那里读取 - 它的成本很低.

Answer 2

您没有告诉我们是否要随机迭代整个数组，或者是否只需要随机的一些元素。

我假设第一种情况。您需要额外的存储空间来记账，并且无论如何您都需要线性时间来进行洗牌。因此，创建一个排列，并保留其内存，以便您可以根据需要重新排列它。使用 C++11：

#include <algorithm>
#include <random>
#include <numeric>

struct permutation
{
    permutation(size_t n) 
        : perm(n), g(std::random_device())
    {
        std::iota(perm.begin(), perm.end(), size_t(0));
    }

    void shuffle() { std::shuffle(perm.begin(), perm.end(), g); }

    size_t operator[](size_t n) const { return perm[n]; }

private:
    std::vector<size_t> perm;
    std::mt19937 g;
};

用法：

std::vector<huge_t> v;
...

permutation sigma(v.size());
sigma.shuffle();

const huge_t& x = v[sigma[0]];

...
sigma.shuffle(); // No extra allocation
const huge_t& y = v[sigma[0]];

您可以调整代码以使用 C++03 std::random_shuffle，但请注意，随机数生成器的保证很少。