从特定范围生成确切数量的唯一随机数

Question

考虑我给出一个特定范围(0到5,000,000),我应该从这个范围产生2,500,000个唯一随机数.有效的方法是什么？我知道很难得到真正的随机数.

我试着检查一个数字是否存在,这样我就可以生成一个新的随机数.但是计算需要几个小时.有一个更好的方法吗.

这背后的原因是,我有一个大小为5,000,000的向量.我想把矢量缩小一半.即从矢量中删除随机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;
    }

有什么更好的办法可以做到这一点吗？

Answer 1

你似乎被锁定在一个想法,你必须以某种方式预先生成你的随机数.为什么？你说最终的任务是从向量中删除一些随机元素.对于该特定问题,不必预先预先生成所有随机索引.您可以"动态"生成这些索引.

对于这个特定的任务(即删除向量中50%的元素),Knuth算法可以很好地工作(参见/sf/answers/112600981/).

只是通过原始向量的所有元素从迭代0到N-1做出的随机决定来删除i第元件用的概率N_to_delete / N_to_iterate,其中,N_to_delete是仍然有要被删除的元素的数量,并且N_to_iterate是载体的剩余部分的长度.这种方法一次性完成(如果巧妙地实现),不需要额外的内存,也不需要反复试验.它完全按照您的要求执行:以相同的概率销毁50%的向量元素.

Knuth算法在随机值(M)的数量与range(N)的长度相比相当大的情况下效果最好,因为它的复杂性与之相关N.在你的情况下,在M50%的情况下,N使用Knuth算法是个不错的主意.

当随机值的数量远小于range(M << N)时,Bob Floyd算法(参见上面的链接)更有意义,因为它的复杂性是由M而不是由它定义的N.它需要额外的内存(一组),但在生成随机数时仍然不会进行反复试验.

但是,在您的情况下,您尝试从向量中删除元素.向量元素删除占主导地位N,无论如何都会破坏Bob Floyd算法的好处.