从STL范围中获取[伪]随机元素的好方法是什么?
我能想到的最好的方法是执行std::random_shuffle(c.begin(), c.end())
,然后从c.begin()
中提取随机元素。
但是,我可能想要const
容器中的随机元素,或者我可能不希望花费全部费用。
还有更好的方法吗?
我将此解决方案发布在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());
我最终创建了一个gist with a better design following a similar approach。
这里所有使用%
的答案都是错误的,因为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个随机位,但是我们在这里会忘记这一点。
C ++ 17 std::sample
这是一种无需重复即可获取几个随机元素的便捷方法。
main.cpp
std::sample
编译并运行:
#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
中随机抽取3个随机数。
为了提高效率,由于1, 2, 3, 5, 7
是使用的API,因此只能保证O(n)
,但我认为stdlib实现将在可能的情况下专门针对ForwardIterator
(例如O(1)
)。
[已在GCC 7.2,Ubuntu 17.10中测试。 vector
。
只要How to obtain GCC 7 in 16.04远大于容器的大小,此方法就可以正常工作,否则会出现偏差问题RAND_MAX:
cited by Alexandre
如果无法访问大小,我想您需要执行以下操作。它将迭代器返回给random元素。
vector<int>::iterator randIt = myvector.begin();
std::advance(randIt, std::rand() % myvector.size());
获取元素数量#include <algorithm>
#include <iterator>
template <class InputIterator> InputIterator
random_n(InputIterator first, InputIterator last) {
typename std::iterator_traits<InputIterator>::difference_type distance =
std::distance(first, last);
InputIterator result = first;
if (distance > 1) {
// Uses std::rand() naively. Should replace with more uniform solution.
std::advance( result, std::rand() % distance );
}
return result;
}
// Added in case you want to specify the RNG. RNG uses same
// definition as std::random_shuffle
template <class InputIterator, class RandomGenerator> InputIterator
random_n(InputIterator first, InputIterator last, RandomGenerator& rand) {
typename std::iterator_traits<InputIterator>::difference_type distance =
std::distance(first, last);
InputIterator result = first;
if (distance > 1) {
std::advance( result, rand(distance) );
}
return result;
}
,然后获取介于0和c.size()
之间的random_number
,并使用:
c.size()
看看auto it = c.begin();
std::advance(it, random_number)
您可以尝试获取介于0和容器元素数之间的随机数。然后,您可以访问容器的相应元素。例如,您可以这样做:
http://www.cplusplus.com/reference/clibrary/cstdlib/rand/
您可以使用0〜1随机函数为容器中的每个元素生成一个浮点数作为其得分。然后选择得分最高的一个。