如何从C++容器中获取随机元素？

Question

从STL范围获取[伪]随机元素的好方法是什么？

我能想到的最好的就是做std::random_shuffle(c.begin(), c.end()),然后从我的随机元素c.begin().

但是,我可能想要一个const容器中的随机元素,或者我可能不想要完全洗牌的成本.

有没有更好的办法？

Answer 1

我在Google+文章中发布了此解决方案,其他人引用了该文章.在这里发布,因为它比其他人略好,因为它通过使用std :: uniform_int_distribution避免了偏见:

#include  <random>
#include  <iterator>

template<typename Iter, typename RandomGenerator>
Iter select_randomly(Iter start, Iter end, RandomGenerator& g) {
    std::uniform_int_distribution<> dis(0, std::distance(start, end) - 1);
    std::advance(start, dis(g));
    return start;
}

template<typename Iter>
Iter select_randomly(Iter start, Iter end) {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    return select_randomly(start, end, gen);
}

样品使用是:

#include <vector>
using namespace std;

vector<int> foo;
/* .... */
int r = *select_randomly(foo.begin(), foo.end());

最后,我采用类似的方法创造了一个更好的设计要点.

Answer 2

%这里使用的所有答案都是不正确的,因为rand() % n会产生有偏见的结果:想象RAND_MAX == 5和元素的数量是4.然后你会得到两倍于0和1的数字而不是数字2或3.

一个正确的方法是:

template <typename I>
I random_element(I begin, I end)
{
    const unsigned long n = std::distance(begin, end);
    const unsigned long divisor = (RAND_MAX + 1) / n;

    unsigned long k;
    do { k = std::rand() / divisor; } while (k >= n);

    std::advance(begin, k);
    return begin;
}

另一个问题是std::rand假设只有15个随机位,但我们在这里会忘记这一点.

Answer 3

C++ 17 std::sample

这是一种方便的方法来获得几个随机元素而不重复.

main.cpp中

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

int main() {
    const std::vector<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    size_t nelems = 3;
    std::sample(
        in.begin(),
        in.end(),
        std::back_inserter(out),
        nelems,
        std::mt19937{std::random_device{}()}
    );
    for (auto i : out)
        std::cout << i << std::endl;
}

编译并运行:

g++-7 -o main -std=c++17 -Wall -Wextra -pedantic main.cpp
./main

输出:从无1, 2, 3, 5, 7重复中挑选3个随机数.

为了提高效率,只能O(n)保证ForwardIterator使用的API,但我认为stdlib实现将专门针对O(1)可能的(例如vector).

在GCC 7.2中测试,Ubuntu 17.10.如何在16.04获得GCC 7.

Answer 4

只要RAND_MAX远大于容器大小,这就可以正常工作,否则它会受到Alexandre引用的偏差问题的影响:

vector<int>::iterator randIt = myvector.begin();
std::advance(randIt, std::rand() % myvector.size());