3

考虑给定一个特定范围（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;
    }

我可以通过什么更好的方法来做到这一点？

4

4 回答 4

5

您似乎被锁定在一个想法上，即您必须以某种方式预先生成随机数。为什么？你说最终的任务是从向量中删除一些随机元素。对于该特定问题，无需预先生成所有随机索引。您可以简单地“即时”生成这些索引。

对于这个特定的任务（即删除向量中 50% 的元素），Knuth 算法会很好地工作（参见https://stackoverflow.com/a/1608585/187690）。

只需遍历原始向量的所有元素 from 0toN-1并随机决定删除i-th 的概率为的元素N_to_delete / N_to_iterate，其中N_to_delete是仍然必须删除的元素的数量，并且N_to_iterate是向量剩余部分的长度. 这种方法一次性完成（如果实施得当），不需要额外的内存，也不需要反复试验。它只是做你想做的事：以相同的概率破坏 50% 的向量元素。

MKnuth 算法在随机值 ( ) 的数量与范围 ( ) 的长度相比相当大的情况下效果最佳N，因为它的复杂性与N. 在您的情况下，M50% 的位置在哪里N，使用 Knuth 算法是一个不错的主意。

当随机值的数量远小于范围M << N（它需要额外的内存（一组），但在生成随机数时仍然不会进行反复试验。MN

但是，在您的情况下，您正在尝试从vector中删除元素。向量元素删除以 为主N，这无论如何都破坏了 Bob Floyd 算法的优势。

于 2012-08-23T18:15:56.920 回答
2

最简单的编码方法：

std::random_shuffle(vectoshrink.begin(), vectoshrink.end());
vectoshrink.resize(vectoshrink.size() / 2);

如果您想保持元素的顺序，请vectoshrink使用 AndreyT 的答案。

如果您确实想提前选择索引：

std::vector<size_t> vec(vectoshrink.size());
// iota is C++11, but easy to do yourself
std::iota(vec.begin(), vec.end(), size_t(0));
std::random_shuffle(vec.begin(), vec.end());
vec.resize(vec.size() / 2);
// optionally
std::sort(vec.begin(), vec.end());

现在，您可以使用这些索引通过将索引处的元素复制vec到新向量中来缩小原始向量，并将结果与​​原始向量交换。

在这两种情况下，random_shuffle都比严格要求的要多，因为它会打乱整个向量，而实际上我们只需要“打乱”它的一半。但是，如果您阅读了 Fisher-Yates shuffle 的工作原理，很容易看出如果您自己编写代码，那么唯一需要的修改就是执行完全 shuffle 的一半的步骤。但是， C++ 没有标准partial_random_shuffle。

最后，请注意默认的随机源可能不是很好，因此您可能需要使用三参数版本的random_shuffle. 您的函数对于和generate_random_number的某些值有很大的偏差，因此您可能需要对随机数生成的一般理论进行更多研究。minmax

于 2012-08-23T18:15:21.313 回答
2

如果您有唯一的数字，而不是手动检查，您可以使用 egstd::unordered_set并继续生成数字，直到集合的大小是您想要的数字数量。

于 2012-08-23T17:48:34.740 回答
0

生成第一个数字<5M，第二个数字<(5M-1)，等等。每次删除元素后，你都会少一个元素，你不在乎它是否是相同的数字。;-) 这并不能回答您关于唯一数字的问题，而是关于将向量减半的问题。

而且您不必生成比您需要的更多的数字。

于 2012-08-23T17:44:30.127 回答