C++中的开源随机数生成算法?

7
我需要连续生成1-10000范围内的随机数,且不重复。有什么建议吗?
描述:我们正在为应用程序构建新版本,该版本在Sqlite数据库中维护记录。在我们应用程序的上一个版本中,每个记录没有唯一的键。但是现在,随着新升级版本的推出,我们需要支持从旧版本的数据库中导入数据。因此,我们读取旧数据库中的每条记录并为其生成一个随机数作为唯一键,并将其存储在新数据库中。在这里,我们可能需要连续导入多达10000条记录。

2
为什么不给新数据库的记录分配顺序唯一键呢?我看不出使用随机键有什么好处。 - TimB
为什么不使用顺序键呢?让数字变得随机对于连接键来说毫无意义。它并不能增加安全性或可靠性... - Toybuilder
实际上问题是,先前的应用程序具有MFC(序列化)对象数据库,现在我们正在将其移动到SQLite,因此出于兼容性原因,我们在此版本中提供了两个数据库。此外,我们需要导入旧的数据库(不包含唯一键)和新的数据库文件(包含唯一键)。 - TG.
为什么你要将范围限制在10000以内?如果你将限制提高到20000,那么重复就不是什么大问题了。(我假设你正在检查“随机”ID是否已经被使用--即使没有其他安全措施!) - Captain Segfault
14个回答

6

好的,最终你要么必须停止生成它们,要么就会开始重复它们。

在计算机上,您的选择相当有限,只能使用伪随机数生成器(PRNG),鉴于您的约束条件是它们永远不会重复,因此PRNG是您的最佳选择 - 真正的随机数据偶尔会重复一个数字。

在您的情况下,我建议使用大型PRNG(32位或更大)来洗牌您的10,000个数字,然后按洗牌顺序发送数字。

一旦使用完毕,您可以再次洗牌 - 由于PRNG非常大,您可以在重复一个序列之前多次遍历这10k个数字。

给我们更多关于您正在做什么的信息,我们可能会想出更好的答案。

-Adam


5

Mersenne Twister是当前最好的(虽然可能比一些真正新的发现晚了几周)。 几乎每种语言的源代码都可以在某个地方找到,MT也在Boost 这里提供。


据我所知,Mersenne Twister 被认为是快速和完美 PRNG 之间的一个很好的折衷方案。 - Paul Nathan
3
它只是某些特定应用的“最佳选择”,比如一切非加密(例如原帖提到的用例或模拟)。 - Roel
对于加密来说,Blum Blum Shub 相当流行。 - Mateen Ulhaq

5
如果必须是1到10,0000的范围,且不能重复但非连续,则最好先创建一个包含10000个元素的连续数组,然后再将它们随机打乱。
然而,我同意原问题中的评论。我认为使它们非连续没有任何价值。
或者,如果唯一且非连续很重要,那么1到10,000范围就变得可疑了。最好使用GUID。

3

如果你的编译器支持,TR1具有良好的随机数支持。

否则,可以使用Boost

基本上它就是成为TR1的东西。

至于避免重复 - 你需要一个洗牌。它可能很简单,但如果不正确地执行,就会有一些陷阱。Jeff Atwood在一段时间前写过一个很好的文章:

http://www.codinghorror.com/blog/archives/001015.html


3

Boost可能做了一些保证不重复数字的事情。

但为了有趣,这是我的想法。

注意:我没有尝试在那个方向上生成我的随机数,那会导致疯狂。

#include <iostream>
#include <vector>
#include <algorithm>


class GaranteedNoRepeatRandom
{
    public:
        GaranteedNoRepeatRandom(int limit)
            :data(limit)
            ,index(0)
        {
            for(int loop=0;loop < limit;++loop)
            {   data[loop]  = loop;
            }
            // Note: random_shuffle optionally takes a third parameter
            // as the rand number generator.
            std::random_shuffle(&data[0],&data[0]+limit);
        }

        unsigned int rand()
        {
            unsigned int result = data[index];
            index   = (index+1) % data.size();

            // Add code to re-shuffle after index wraps around
            return result;
        }
    private:
        std::vector<unsigned int>               data;
        std::vector<unsigned int>::size_type    index;
};

int main()
{
    GaranteedNoRepeatRandom     gen(10000);

    for(int loop =0;loop < 10;++loop)
    {
        std::cout << gen.rand() << "\n";
    }
}

2

Boost.Random 是一个不错的选择,并且对我来说运行良好。然而,如果你不需要太多的随机数生成器和分布函数,你可以寻找另一个库而不是安装整个 Boost 包。


2

随机性的程度如何?显然有rand(),此外还有特定于操作系统的内容(例如Windows中的CryptoAPI)。你是在编写某些东西(不建议),还是只是寻找一个现有的函数来使用?


2

2

对于使用随机数作为数据库记录的唯一键是否合适这个想法,您是否可以进行质疑?我不熟悉SQLite,但值得调查它是否支持某种内部唯一列标识符。例如,SQL Server有“identity”列,Oracle有“sequences”,两者都具有相同的目的。


2
生成大量的随机数,比如128位。在10000个数字集合中出现两个相同的概率是极小的(大约是n^2/2^b,其中n为需要的数字数量,b为使用的位数)。如果位数足够多,这个概率会变得比你的ram被宇宙射线损坏从而使你的算法失败的概率还要小。请注意,你所抽取的随机数空间确实具有你所需的位数。很容易误将32位的池子生成128位的数字(即使你正在生成1到2^128的数字,但实际上只有2^32种可能性)。boost库中的随机数生成器可以正确地为您执行此操作。顺便说一下:如果你不喜欢128位,那么使用256位或更多,直到你确定没有实际的哈希冲突机会。如果你只需要做一次,那么就使用之前提到的洗牌方法。这将具有生成完美哈希的优点。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接