6

我需要在不重复的情况下连续生成 1 - 10000 范围内的随机数。有什么建议吗？

描述：我们正在为我们的应用程序构建一个新版本，它在 Sqlite DB 中维护记录。在我们应用程序的最后一个版本中，我们没有为每条记录设置唯一键。但是现在有了新的升级版本，我们需要支持从上一个版本的数据库中导入工具。所以我们所做的是，我们从旧数据库中读取每条记录，并为唯一键生成一个随机数并将其存储在新数据库中。在这里，我们很多人需要连续导入多达 10000 条记录。

4

14 回答 14

5

如果它确实必须在 1 到 10,0000 的范围内而不重复，但不是连续的，那么最好先创建一个包含 10000 个元素的顺序数组，然后对它们进行洗牌。

但是，我必须同意对原始问题的评论。我认为使它们不连续没有任何价值。

或者，在唯一和非连续很重要的情况下，1 到 10,000 的范围变得有问题。最好只使用 GUID。

于 2008-10-10T20:45:14.133 回答
5

好吧，最终您将不得不停止生成它们，或者您将复制它们。

在计算机上，您的选择仅限于伪随机数生成器 (PRNG)，并且考虑到它们从不重复的限制，那么 PRNG 是您的最佳选择 - 真正的随机数据偶尔会重复一个数字。

在您的情况下，我会考虑使用大型 PRNG（32 位或更大）来洗牌您的 10,000 个数字，然后按洗牌顺序发送数字。

一旦它们用完，你就可以再次洗牌——因为 PRNG 太大了，你可以在复制一个序列之前多次遍历 10k 个数字。

向我们提供有关您在做什么的更多信息，我们可能会提出更好的答案。

-亚当

于 2008-10-10T04:44:06.957 回答
5

Mersenne Twister 是目前最好的（尽管我可能落后于任何真正的新发现几周）。几乎所有语言的源代码都可以在某个地方获得，并且 MT 在 Boost here中也提供

于 2008-10-10T04:44:44.317 回答
3

TR1 有很好的随机数支持——如果你的编译器支持的话。

否则提升

它基本上就是TR1。

至于不重复 - 你想要一个shuffle。这可能很简单，但如果你做得不对，就会有一些陷阱。杰夫阿特伍德不久前写了一篇不错的文章：

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

于 2008-10-10T04:45:44.627 回答
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";
    }
}
于 2008-10-10T05:05:14.667 回答
2

生成大随机数。说 128 位。在一组 10000 中，两个这样的数字相同的几率非常小（大约为 n^2/2^b，其中 n = 所需数字的数量，b = 使用的位数）。给定足够的位，几率将变得小于你的 ram 被宇宙射线破坏的几率，这样你的算法无论如何都会失败。请注意，您从中提取随机数的空间确实具有您正在寻找的位数。很容易从 32 位池中错误地生成 128 位数字（即，即使您生成数字 1 到 2^128，也只有 2^32 种可能性）。boost 库中的随机数生成器可以为您正确执行此操作。顺便说一句：如果你不喜欢 128 位，然后使用 256 位或更多位，直到您确信不存在散列冲突的实际机会。如果您只需要这样做一次，那么只需使用前面答案中已经提到的 shuffle 方法。这将具有生成完美哈希的优势。

于 2008-10-10T17:17:20.073 回答
2

随机数的生成太重要了，不能靠运气。-- Robert R. Coveyou，橡树岭国家实验室

于 2008-10-14T12:01:14.017 回答
2

Boost.Random是一个不错的选择，对我来说效果很好。但是，如果您不需要很多随机数生成器和分发版，您可能会寻找另一个库，而不是安装整个 Boost 包。

于 2008-10-10T04:44:47.297 回答
2

随机性如何？显然有 rand()，还有特定于操作系统的东西（例如，Windows 在 CryptoAPI 中有一些东西）。你是在写东西（不推荐），还是只是在寻找一个预先存在的功能来使用？

于 2008-10-10T04:45:01.913 回答
2

mtrand不错。

于 2008-10-10T04:46:10.977 回答
2

是否可以质疑使用随机数作为数据库记录的唯一键的整个想法？我对 sqlite 不熟悉，但值得研究一下它是否在内部支持某种唯一列标识符。例如，SQL Server 有“identity”列，Oracle 有“sequences”，两者的目的相同。

于 2008-10-10T05:13:13.980 回答
2

虽然您可能需要生成一系列不重复的值，但您不能将结果称为“随机”。真正的随机性与缺乏重复性的关系不如与序列中值的分布有关。

于 2008-10-10T17:51:34.030 回答
0

http://random.org/如果您需要真正的随机数

于 2008-10-10T17:20:08.540 回答
0

C 中的数值食谱有一整章专门介绍随机数的生成。那里有一些实现。从简单直接到具有良好统计特性的复杂。

于 2008-10-10T05:10:15.623 回答