c++ - 从特定范围内生成特定数量的唯一随机数

Question

假设我有一个特定的范围(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;
    }

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

Answer 1

您似乎执着于必须以某种方式预先生成您的随机数的想法。为什么？你说最终任务是从 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 算法的优势。