假设我有一个特定的范围(0 到 5,000,000),我应该从这个范围内生成 2,500,000 个唯一的随机数。执行此操作的有效方法是什么?我知道很难获得真正的随机数。
我尝试检查数字是否存在,以便生成新的随机数。但是计算需要几个小时。有没有更好的方法来做到这一点。
这背后的原因是,我有一个大小为 5,000,000 的 vector 。我想将 vector 正好缩小一半。即从 vector 中随机删除 50% 的元素。
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define NUMBER 2500000
#define RAND_START 0
#define RAND_END 5000000
unsigned int generate_random_number(int min, int max)
{
return min + (rand() % (unsigned int)(max - min + 1));
}
int main(int argc, char* argv[])
{
unsigned int count = 0, random_number;
vector<unsigned int> rand_vector;
do
{
count++;
random_number = generate_random_number(RAND_START,RAND_END);
// Tried to manually add a different number each time. But still not a considerable improvement in performance.
if (std::find(rand_vector.begin(), rand_vector.end(), random_number) != rand_vector.end())
{
if(random_number > count)
random_number = random_number - count;
else
random_number = random_number + count;
}
rand_vector.push_back(random_number);
sort(rand_vector.begin(), rand_vector.end());
rand_vector.erase(unique (rand_vector.begin(), rand_vector.end()), rand_vector.end());
}while (rand_vector.size() != NUMBER);
for (unsigned int i =0; i < rand_vector.size(); i++)
{
cout<<rand_vector.at(i)<<", ";
}
cout<<endl;
return 0;
}
有什么更好的方法可以做到这一点?
最佳答案
您似乎执着于必须以某种方式预先生成您的随机数的想法。为什么?你说最终任务是从 vector 中删除一些随机元素。对于那个特定的问题,没有必要预先生成所有随机索引。您可以简单地“即时”生成这些索引。
对于这个特定任务(即删除 vector 中 50% 的元素),Knuth 算法将工作得很好(参见 https://stackoverflow.com/a/1608585/187690)。
只需遍历来自 0
的原始 vector 的所有元素至 N-1
并随机决定删除 i
- 概率为 N_to_delete / N_to_iterate
的元素, 其中N_to_delete
是仍需删除的元素数,N_to_iterate
是 vector 剩余部分的长度。这种方法一次性完成(如果实现巧妙),不需要额外的内存,也不需要反复试验。它只是完全按照您的意愿行事:以相同的概率销毁 50% 的 vector 元素。
Knuth 算法在随机值的数量 (M
) 与范围的长度 (N
) 相比相当大的情况下效果最好,因为它的复杂性与 N
有关。 .在你的情况下,哪里 M
是 N
的 50% , 使用 Knuth 算法是个不错的主意。
当随机值的数量远小于范围 (M << N
) 时,Bob Floyd 算法(参见上面的链接)更有意义,因为它的复杂性由 M
定义而不是 N
.它需要额外的内存(一组),但在生成随机数时仍然没有反复试验。
但是,在您的情况下,您正试图从 vector 中删除元素。 vector 元素删除以N
为主,这无论如何都抵消了 Bob Floyd 算法的优势。
关于c++ - 从特定范围内生成特定数量的唯一随机数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12097243/