在.NET中生成一个随机且不重复的整数序列

Question

在.NET中生成一个随机且不重复的整数序列

32

在.NET中，有没有一种方法可以以随机顺序、不重复地生成所有32位整数（Int32），并且以节约内存的方式实现？节约内存意味着只使用最多几百兆字节的主内存。理想情况下，该序列应该类似于IEnumerable，它会惰性地返回请求的下一个数字。我进行了一些快速研究，并找到了一些部分解决方案：

使用最大线性反馈移位寄存器 - 如果我理解正确，它只生成递增顺序的数字，而且并没有覆盖整个范围。
使用Fisher-Yates或其他集合洗牌算法 - 鉴于大范围的限制，这将违反内存限制。
维护类似集合的收集，并继续生成随机整数（可能使用Random），直到不重复为止，即不在集合中 - 除了可能无法满足内存要求外，当生成序列中的最后几个数字时，它会变得非常缓慢。
32位随机排列，但我想不出确保不可重复性的方法。

有没有其他方法来看待这个问题 - 也许利用固定值范围的优势 - 以满足内存要求的解决方案？也许.NET类库带有一些有用的东西吗？

更新1

感谢大家对解决方案的见解和创意建议。我将尽快实施和测试这里提出的2或3个最有前途的解决方案（包括正确性和内存效率），并发布结果，然后选择一个“获胜者”。

更新2

我尝试了hvd在下面的评论中提出的建议。我尝试使用.NET中的BitArray和我的自定义实现，因为.NET的限制为int.MaxValue条目，不足以覆盖整个整数范围。

我很喜欢这个想法的简单性，如果它运行良好，我愿意“牺牲”那512 MB的内存。不幸的是，在我的计算机上生成下一个随机数需要花费相当长的时间，甚至多达十几秒钟，我的计算机配备了3.5 GHz的Core i7 CPU。因此，如果您需要生成许多随机数，这是不可接受的。我想这是可以预测的，如果我没有弄错的话，它是O（M x N）算法，其中N是2 ^ 32，M是请求的整数数量，因此所有这些迭代都会付出代价。

理想情况下，我希望在满足内存需求的同时以O（1）时间生成下一个随机数，也许这里建议的下一个算法适合此目的。我会尽快尝试它们。

更新3

我刚刚测试了线性同余生成器，我可以说我对结果感到非常满意。它看起来是本主题中胜者的有力竞争者。

正确性：所有生成的整数仅一次（我使用了位向量来检查这一点）。

随机性：相当不错。

内存使用: 极佳，仅使用了少量字节。

运行时间: 生成下一个随机整数非常快，正如你从O(1)算法所期望的一样。在我的机器上，生成每个整数总共花费了大约11秒钟。

总体而言，如果您不需要高度随机化的序列，我认为这是一种非常适当的技术。

更新4

下面描述的模 multiplicative inverse technique 和 LCG 技术表现非常相似 - 这并不奇怪，因为两者都基于模算术 - 尽管我发现实现起来有点不那么直接，以产生令人满意的随机序列。

我发现有趣的一个区别是，这种技术似乎比LCG更快：生成整个序列大约花费了8秒钟，而LCG则是11秒钟。除此之外，所有关于内存效率、正确性和随机性的评论都是一样的。

更新5

看起来用户TomTom在我指出Mersenne Twister生成重复数字的问题后没有通知地删除了他们的回答。所以我猜这完全排除了Mersenne Twister。

更新6

我测试了另一种被建议的技术Skip32，虽然我真的很喜欢它产生的随机数的质量，但是该算法无法在可接受的时间内生成整个范围的整数。因此，与能够完成该过程的其他技术相比，它不足。顺便说一下，我使用了这里的C#实现——我将代码更改为只进行一轮，但它仍然无法及时完成。

综上所述，根据上述结果，我个人选择的解决方案是模数乘法逆元技术，紧随其后的是线性同余发生器。有些人可能会认为这在某些方面比其他技术劣，但考虑到我的原始限制，我认为它最适合。

- Gabriel S.

5

我认为你的问题中已经有一个非常好的答案，只是你没有看到它。使用比特数组可以维护类似集合的集合。它需要2 ** 32个比特，即512 MB，看起来有些高端，但仍在你几百兆字节的要求范围内。生成不在该集合中的随机数字不需要尝试和错误：如果剩余N个数字，则从0到N-1生成一个随机数字，然后选择第N个剩余数字即可。 - user743382

@hvd：我曾经考虑过使用位数组，知道它所占用的空间比整数数组/集合要少，但我没有想到如何填充该数组，感谢您的见解！至于512 MB的下限，我认为这仍然是有问题的——想想旧PC，比如90年代的那些，当时这样的内存量是奢侈的。 - Gabriel S.

@Bjørn-RogerKringsjå：是的，所有的，在整个范围内。 - Gabriel S.

1

这似乎是这个问题的一个特殊情况：https://dev59.com/Amkw5IYBdhLWcg3wNX73 - usr

我没有实现任何那些东西。如果我没记错的话，我选择了Fisher Yates洗牌算法，并接受了浪费内存的使用，因为这不是生产代码。 - usr

显示剩余14条评论

8个回答

8

.NET中是否有一种方法可以生成所有32位整数（Int32）的序列

是的。

以随机顺序，

在这里，我们需要就术语达成共识，因为“随机”并不是大多数人想象的那样。稍后会详细说明。

无重复地，

是的。

并且在内存使用上要高效吗？

是的。

高效的意思是仅使用最多几百兆字节的主存储器。

好的，那么几乎不使用内存是否可接受？;-)

在提出建议之前，我们需要澄清“随机性”的问题。真正的随机性没有可辨别的模式。因此，连续运行算法数百万次理论上可能会在所有迭代中返回相同的值。如果加入“必须与先前迭代不同”的概念，则不再是随机的。然而，从所有要求中看，似乎真正被要求的只是“整数分布的不同模式”。这是可行的。

那么如何高效地做到这一点？利用模数乘法逆元。我使用它来回答以下类似要求的问题：在特定范围内生成非重复的伪随机样本数据。在给定区间内生成不同的随机时间。

我最初在这里了解到这个概念(在SQL Server中生成看似随机的唯一数字ID)，您可以使用以下任何一个在线计算器来确定您的“整数”和“模乘逆元(MMI)”值：

应用这个概念，您将使用Int32.MaxSize作为模数值。

这将给出一个明确的随机分布外观，没有碰撞的机会，也不需要存储已使用的值的内存。

唯一的初始问题是，在相同的“整数”和“MMI”值下，分布模式总是相同的。因此，您可以通过向起始值添加“随机”生成的Int或预先生成几个“整数”和相应的“MMI”值的组合，并将其存储在配置文件/字典中，并在每次运行开始时使用.NET随机函数选择一个来得到不同的模式。即使存储100个组合，也几乎不会使用任何内存（假设它不在配置文件中）。实际上，如果将两个都存储为Int并且字典使用Int作为索引，则1000个值约为12k？

更新

注：

结果中存在一种模式，但在任何特定时刻只有拥有足够的结果才能看出来。对于大多数用例，这是可以接受的，因为没有一个值的接收者会拥有它们的大量集合，或知道它们是按顺序分配的而没有间隙（需要该知识才能确定是否存在模式）。
在公式的特定运行中，只需要两个变量值之一："整数"和“模乘逆元(MMI)”。因此：
- 每个对给出两个不同的序列
- 如果要在内存中维护一个集合，则只需要一个简单的数组，并且假设数组索引仅是相对于数组基地址的内存偏移量，则所需的内存应该只有4字节*容量（即1024个选项仅为4k，对吧？）

这里有一些测试代码，它是用 T-SQL 编写的，适用于 Microsoft SQL Server，因为那是我主要工作的地方，而且还具有在不需要编译任何内容的情况下轻松测试唯一性、最小值和最大值等优点。该语法适用于 SQL Server 2008 或更新版本。对于 SQL Server 2005，变量的初始化尚未引入，因此每个包含“=”的 DECLARE 只需被分成 DECLARE 和 SET @Variable = ...，以便初始化变量。SET @Index += 1; 需要变成 SET @Index = @Index + 1;。

如果您提供的值产生任何重复项，则测试代码将出错。如果没有重复项，则最终查询指示是否存在间隙，因为可以推断出，如果表变量填充未出现错误（因此没有重复项），并且值的总数是预期数量，则只能存在间隙（即缺少值）IF 实际 MIN 和 MAX 值中的任何一个或两个都在预期值之外。

请注意，此测试代码并不意味着任何值都是预生成的或需要存储。该代码仅存储这些值以测试唯一性和最小/最大值。实际上，只需要简单的公式，而且只需要传入以下内容即可：

容量（虽然在这种情况下也可以硬编码）
MMI / 整数值
当前“索引”

因此，您只需要维护2-3个简单的值。

DECLARE @TotalCapacity INT = 30; -- Modulo; -5 to +4 = 10 OR Int32.MinValue
                                 -- to Int32.MaxValue = (UInt32.MaxValue + 1)
DECLARE @MMI INT = 7; -- Modular Multiplicative Inverse (MMI) or
                      -- Integer (derived from @TotalCapacity)

DECLARE @Offset INT = 0; -- needs to stay at 0 if min and max values are hard-set
-----------
DECLARE @Index INT = (1 + @Offset); -- start

DECLARE @EnsureUnique TABLE ([OrderNum] INT NOT NULL IDENTITY(1, 1),
                             [Value] INT NOT NULL UNIQUE);
SET NOCOUNT ON;

BEGIN TRY
    WHILE (@Index < (@TotalCapacity + 1 + @Offset)) -- range + 1
    BEGIN
        INSERT INTO @EnsureUnique ([Value]) VALUES (
                 ((@Index * @MMI) % @TotalCapacity) - (@TotalCapacity / 2) + @Offset
                                                   );
        SET @Index += 1;
    END;
END TRY
BEGIN CATCH
    DECLARE @Error NVARCHAR(4000) = ERROR_MESSAGE();
    RAISERROR(@Error, 16, 1);
    RETURN;
END CATCH;

SELECT * FROM @EnsureUnique ORDER BY [OrderNum] ASC;
SELECT COUNT(*) AS [TotalValues],
       @TotalCapacity AS [ExpectedCapacity],
       MIN([Value]) AS [MinValue],
       (@TotalCapacity / -2) AS [ExpectedMinValue],
       MAX([Value]) AS [MaxValue],
       (@TotalCapacity / 2) - 1 AS [ExpectedMaxValue]
FROM   @EnsureUnique;

- Solomon Rutzky

1

我可能错了，但这似乎是迄今为止在这个线程中描述的最数学上直接的技术。我会尝试一下并与其他方法进行比较。 - Gabriel S.

@GabrielS。FYI，我刚刚添加了一个更新部分，其中包含一些示例代码，尽管它是用T-SQL编写的;-) - Solomon Rutzky

1

谢谢，这将会很有帮助！ - Gabriel S.

@GabrielS。没问题。我刚刚在示例代码上面添加了一个澄清段落，以明确它测试的是“无间隔”和“无重复项”。 - Solomon Rutzky

1

看看我的更新后的原始帖子。我设法在我所需的范围内实现了这个，结果看起来相当不错，可以与另一个答案中描述的LCG技术相媲美。对于这样的情景来说，绝对是一种方便的技术。不过，为了获得足够随机性的序列，我还需要微调一下数字。 - Gabriel S.

3

在CTR模式下，我认为使用32位PRP似乎是唯一可行的方法（您的第4种方案）。

你可以选择：

使用专用的32位块密码。

Skip32，即Skipjack的32位变体，是一个常见的选择。

为了在质量/安全性和性能之间权衡，可以根据需要调整轮数。轮数越多，速度越慢，但越安全。
长度保持加密（格式保持加密的特殊情况）

FFX模式是典型的推荐方案。但在其典型的实例中（例如使用AES作为底层密码），它会比专用的32位块密码慢得多。

请注意，这些构造中许多都有一个显著的缺陷：它们是偶排列。这意味着一旦你看到2^32-2个输出，你就能确定倒数第二个输出，而不仅仅是50％。我认为Rogaways AEZ论文提到了修复此缺陷的方法。

- CodesInChaos

我不清楚如何为我的目的使用Skip32，你能给我一些提示吗？我应该遍历整个整数范围，并在它们到来时加密它们，从而得到随机序列吗？ - Gabriel S.

1

@GabrielS。使用seed作为密钥，然后加密一个计数器。独特的输入产生独特的输出，而计数器显然是独特的。 - CodesInChaos

请查看我更新的原始帖子。生成的数字在随机性方面看起来非常好，但是即使只进行一轮，生成所有整数也需要超过9分钟的时间。 - Gabriel S.

2

我要先说明一下，有些其他回答可能更加优雅，而且可能比这个回答更适合你的需求。这显然是一种粗暴的解决方案。

如果获取真正随机（或者对于密码学来说足够伪随机）的内容很重要，你可以预先生成一张整数列表，并将它们以随机顺序存储在磁盘上。在程序运行时，你可以从磁盘中读取这些数字。

以下是我提供的算法的基本概述。所有32位整数可以存储在大约16 GiB的磁盘空间中（32位=4字节，4字节/整数*2^32个整数=2^34字节=16 GiB，再加上操作系统/文件系统需要的任何开销），而我认为“几百兆字节”意味着你想一次读入不超过256 MiB的文件。

1. 生成16 GiB / 256 MiB = 64个ASCII文本文件，每个文件都有256 MiB的“null”字符（所有位设置为0）。将每个文本文件命名为“0.txt”到“64.txt” 2. 从Int32.MinValue到Int32.MaxValue连续循环，跳过0。这是你正在存储的整数值。 3. 每次迭代时，从您选择的随机源（硬件真随机生成器、伪随机算法等）中生成0到UInt32.MaxValue的随机整数。这是您当前正在存储的值的索引。 4. 将索引拆分为两个整数：6个最高位和剩余的26个位。使用上位位加载相应的文本文件。 5. 将较低的26位乘以4，并将其用作打开文件中的索引。如果该索引后面的四个字节仍然都是“null”字符，则将当前值编码为四个ASCII字符，并将这些字符存储在该位置。如果它们不都是“null”字符，则返回步骤3。 6. 重复，直到所有整数都被存储。

这会确保数字来自已知的随机源，但仍然是唯一的，而不是有其他提议解决方案的限制。编译时间可能很长（特别是使用相对简单的算法），但它符合运行时效率的要求。

在运行时，你现在可以生成一个随机的起始索引，然后按顺序从文件中读取字节，以获取一个唯一、随机且不重复的整数序列。假设你只同时使用了相对较少的整数，你甚至可以随机索引到文件中，存储你使用过的索引，并确保不重复使用某个数字。

（*我理解任何来源的随机性都会因施加“唯一性”约束而减弱，但这种方法应该产生与原始源相对接近的随机数字）

简而言之，提前打乱整数顺序，在许多较小的文件中将它们全部存储在磁盘上，然后在运行时从文件中读取。

- Mike Lewis

虽然磁盘空间听起来像是主内存的一个不错的“替代品”，但我认为将16 GB 的磁盘空间用于此目的有些夸张。除此之外，它符合要求，如果你愿意为主内存交换任何其他资源，无论多少，这并不是一个坏的解决方案。 - Gabriel S.

1

根据您的定义，由于您的数字应该是随机的，因此按照定义没有其他方法，只能将它们全部存储，因为数字之间没有固有关系。这意味着您必须存储所有使用过的值，以防止它们再次使用。

然而，在计算中，模式只需要不被“注意到”。通常，系统通过使用巨大的预定值和计时器值执行乘法运算来计算随机数，以使它们溢出并因此看起来是随机选择的。因此，您可以使用第三个选项，或者考虑以一种可以重现生成的每个数字序列的方式生成这些伪随机数，并检查是否有重复出现。这显然会非常消耗计算资源，但您要求内存效率。

因此，您可以存储用于种子生成器的数字和生成的元素数量。每次需要新数字时，请重新设置种子生成器并迭代生成的元素数量+1。这就是您的新数字。现在重新播种并再次迭代序列以检查其是否出现过。

所以像这样：

int seed = 123;
Int64 counter = 0;
Random rnd = new Random(seed);

int GetUniqueRandom()
{
    int newNumber = rnd.Next();
    Random rndCheck = new Random(seed);

    counter++;

    for (int j = 0; j < counter; j++)
    {
        int checkNumber = rndCheck.Next();

        if (checkNumber == newNumber)
            return GetUniqueRandom();
    }

    return newNumber;        
}

编辑：有人指出counter会达到一个巨大的值，无法确定在获取所有40亿个值之前是否会发生溢出。

- srandppl

1

考虑到 OP 对问题中的一个想法提出了反对意见，即“它会变得非常慢”，我认为仅仅专注于内存效率是不够的，但我确实喜欢你的创造性方法。 - user743382

此外，rnd.Next() 永远不会返回负数或 int.MaxValue，但通过调用 rnd.Next(65536) 两次并组合结果来修复这个问题应该很容易。 - user743382

当然，我不是在寻求绝对的随机性，伪随机性也可以。我喜欢你的方法，目前我看不到任何缺陷（假定hvd的更正），虽然在考虑计算时间时有点极端。然而，它肯定符合内存要求，我看不到任何比这更低的方法。 - Gabriel S.

1

在计算中，不存在所谓的“真正的随机性”。但是硬件随机数生成是真正的随机，并且现在被许多处理器实现。 - TomTom

我真的不明白这怎么可能会起作用，即使你使用随机数生成器而不是 Random... 你基本上是递归地计算碰撞——这意味着在计算中有如此多的开销，以至于它变得非常缓慢（如果你超过集合的50％，你需要检查一百万个数字，每个新数字需要检查2000次？！）——请看我的答案中的第一个算法：在那种情况下，你已经得到了13个碰撞）。最后一个数字可能永远都无法在我们的有生之年内计算出来... - atlaste

显示剩余2条评论

1

好的谜题。有几个想法：

我们需要存储哪些项目已被使用。如果近似足够好，您可能希望使用布隆过滤器来实现。但是，由于您明确声明要获取所有数字，因此只有一种数据结构可以实现：位向量。
您可能希望使用具有长周期的伪随机生成算法。
解决方案可能涉及使用多个算法。

我的第一次尝试是弄清楚如何使用简单的位向量进行伪随机数生成。我接受碰撞（因此会减慢速度），但绝对不会出现太多碰撞。这个简单的算法可以在有限的时间内为您生成大约一半的数字。

static ulong xorshift64star(ulong x)
{
    x ^= x >> 12; // a
    x ^= x << 25; // b
    x ^= x >> 27; // c

    return x * 2685821657736338717ul;
}

static void Main(string[] args)
{
    byte[] buf = new byte[512 * 1024 * 1024];
    Random rnd = new Random();

    ulong value = (uint)rnd.Next(int.MinValue, int.MaxValue);
    long collisions = 0;

    Stopwatch sw = Stopwatch.StartNew();

    for (long i = 0; i < uint.MaxValue; ++i)
    {
        if ((i % 1000000) == 0)
        {
            Console.WriteLine("{0} random in {1:0.00}s (c={2})", i, sw.Elapsed.TotalSeconds, collisions - 1000000);
            collisions = 0;
        }

        uint randomValue; // result will be stored here
        bool collision;

        do
        {
            value = xorshift64star(value);
            randomValue = (uint)value;

            collision = (buf[randomValue >> 4] & (1 << (int)(randomValue & 7))) != 0;
            ++collisions;
        }
        while (collision);

        buf[randomValue >> 4] |= (byte)(1 << (int)(randomValue & 7));
    }

    Console.ReadLine();
}

大约经过19亿个随机数之后，该算法将开始变得非常缓慢。

1953000000个随机数用时283.74秒（c = 10005932） [...] 2108000000个随机数用时430.66秒（c = 52837678）

因此，为了论证的目的，假设您将在前20亿个数字中使用此算法。

接下来，您需要解决剩余数字的问题，这基本上是OP所描述的问题。为此，我建议将随机数采样到缓冲区中，并使用Knuth洗牌算法将缓冲区与其组合。如果您喜欢，也可以从一开始就使用它。

这是我想出来的解决方案（可能仍有错误，请测试……）：

static void Main(string[] args)
{
    Random rnd = new Random();

    byte[] bloom = new byte[512 * 1024 * 1024];
    uint[] randomBuffer = new uint[1024 * 1024];

    ulong value = (uint)rnd.Next(int.MinValue, int.MaxValue);
    long collisions = 0;

    Stopwatch sw = Stopwatch.StartNew();
    int n = 0;

    for (long i = 0; i < uint.MaxValue; i += n)
    {
        // Rebuild the buffer. We know that we have uint.MaxValue-i entries left and that we have a 
        // buffer of 1M size. Let's calculate the chance that you want any available number in your 
        // buffer, which is now:

        double total = uint.MaxValue - i;
        double prob = ((double)randomBuffer.Length) / total;

        if (i >= uint.MaxValue - randomBuffer.Length)
        {
            prob = 1; // always a match.
        }

        uint threshold = (uint)(prob * uint.MaxValue);
        n = 0;

        for (long j = 0; j < uint.MaxValue && n < randomBuffer.Length; ++j)
        {
            // is it available? Let's shift so we get '0' (unavailable) or '1' (available)
            int available = 1 ^ ((bloom[j >> 4] >> (int)(j & 7)) & 1);

            // use the xorshift algorithm to generate a random value:
            value = xorshift64star(value);

            // roll a die for this number. If we match the probability check, add it.
            if (((uint)value) <= threshold * available)
            {
                // Store this in the buffer
                randomBuffer[n++] = (uint)j;

                // Ensure we don't encounter this thing again in the future
                bloom[j >> 4] |= (byte)(1 << (int)(j & 7));
            }
        }

        // Our buffer now has N random values, ready to be emitted. However, it's 
        // still sorted, which is something we don't want. 
        for (int j = 0; j < n; ++j)
        {
            // Grab index to swap. We can do this with Xorshift, but I didn't bother.
            int index = rnd.Next(j, n);

            // Swap
            var tmp = randomBuffer[j];
            randomBuffer[j] = randomBuffer[index];
            randomBuffer[index] = tmp;
        }

        for (int j = 0; j < n; ++j)
        {
            uint randomNumber = randomBuffer[j];
            // Do something with random number buffer[i]
        }

        Console.WriteLine("{0} random in {1:0.00}s", i, sw.Elapsed.TotalSeconds);
    }

    Console.ReadLine();
}

回到需求：

在.NET中有没有一种方法可以以随机顺序生成所有32位整数（Int32），而且不重复，且使用内存高效的方式？内存高效意味着最多只使用几百兆字节的主内存。

成本：512 MB + 4 MB。重复：无。

速度相当快。只是速度不是“均匀”的。每100万个数字，您必须重新计算缓冲区。

另一个好处是：两种算法可以共同使用，因此您可以首先非常快地生成前20亿个数字，然后对其余部分使用第二个算法。

- atlaste

刚刚测试了一下，在我的笔记本电脑上，大约可以在20秒内生成1M个随机数。一个可能的优化是在available和乘法中；你也可以将其强制为0和-1，并使用and而不是乘法。 - atlaste

所以，如果最终内存消耗约为512MB，那么在上面的评论中hvd提出的解决方案是否更简单，甚至更快？或者我错过了什么吗？ - Gabriel S.

是的，这完全是胡说八道。 :) Hvb建议从剩余数字集合中随机选择一个数字，这意味着您必须将它们全部存储。因此，您需要4G才能完成这个过程 - 否则您将遇到冲突（这是第一个算法）。 - atlaste

3

@TomTom 真的吗？我的解决方案有效并满足所有要求；我认识到你的“Twister”（我今天之前没见过）可能是一个更好的解决方案，但没有必要对此不礼貌。 - atlaste

2

@TomTom 我相当肯定，大声喊叫你的显示器上有人是白痴，并详细解释原因，然后再加上这样的评论：“伪随机数生成并不是新鲜事物，一些数学家已经提出了一些好的解决方案，不需要记住所有数字。例如，这本书 _____ 是一个很好的起点。”这只是个想法 :-) 或者，至少在称别人为白痴之前，请使用拼写检查 ;-) - Solomon Rutzky

@atlaste，连三个字母的名字都不想正确拼写？称我的评论完全是胡说八道？然而还在指责别人粗鲁？伪君子。不，我的评论中没有任何需要4GB内存的地方。给定一个512MB位数组，可以轻松找到任何N值的第N个零位，而无需任何额外的内存要求。 - user743382

1

最简单的解决方案之一是使用像AES in countermode这样的块加密算法。您需要一个与AES中的密钥相等的种子。接下来，您需要一个计数器，该计数器在每个新的随机值时递增。随机值是使用密钥加密计数器的结果。由于明文（计数器）和随机数（密文）是双射的，并且由于鸽笼原理，随机数是唯一的（对于块大小）。

内存效率：您只需要存储种子和计数器。

唯一的限制是AES具有128位块大小，而不是32位。因此，您可能需要增加到128位或找到一个块密码，其块大小为32位。

对于您的IEnumerable，可以编写包装器。索引是计数器。

免责声明：您正在请求非重复/唯一性的值，这使得随机数通常会出现碰撞而失去随机性。因此，您不应在长序列中使用它。另请参见 https://crypto.stackexchange.com/questions/25759/how-can-a-block-cipher-in-counter-mode-be-a-reasonable-prng-when-its-a-prp。

- H. Idden

我怀疑密码学可能有一些算法可以实现类似于我所追求的东西，但唯一性的要求是固定的。可以将其视为随机洗牌所有整数序列，不多也不少。根据您的免责声明，我认为AES在这里并不是最佳选择。 - Gabriel S.

那么唯一的问题就是AES的块大小为128位而不是32位。但是，正如所说，任何其他块密码也可以做到。它们之间唯一的区别将是随机数的安全性和偏差程度。我不知道有任何未破解的32位块密码。但是，既然您已经存在偏差/唯一性方面的违规，并且声明您不需要高安全性，那么这个答案符合您的问题。有人已经提到了Skipjack32（我以前从未使用过）。免责声明主要是让其他人考虑，以防他们有其他要求。 - H. Idden

0

你可以尝试使用这个自制的分组密码：

public static uint Random(uint[] seed, uint m)
{   
    for(int i = 0; i < seed.Length; i++)
    {
        m *= 0x6a09e667;
        m ^= seed[i];
        m += m << 16;
        m ^= m >> 16;
    }
    return m;
}

测试代码：

const int seedSize = 3; // larger values result in higher quality but are slower
var seed = new uint[seedSize];
var seedBytes = new byte[4 * seed.Length];
new RNGCryptoServiceProvider().GetBytes(seedBytes);
Buffer.BlockCopy(seedBytes, 0, seed, 0, seedBytes.Length);  

for(uint i = 0; i < uint.MaxValue; i++)
{
    Random(seed, i);
}

我还没有检查它的输出质量。在我的电脑上，当seedSize = 3时运行时间为19秒。

- CodesInChaos

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mateon1 · Accepted Answer

如果您不需要随机数具有密码学安全性，可以使用线性同余生成器（Linear Congruential Generator，LCG）。

LCG是一种形式为X_n+1 = X_n * a + c (mod m)的公式，它只需恒定的内存和时间来生成每个随机数。如果选择了适当的LCG值，它将具有完整的周期长度，即它将输出在0到所选模数之间的每个数字。

仅当以下条件满足时，LCG才具有完整的周期：

模数和增量互质，即GCD(m, c) = 1
a - 1可被m的所有质因数整除
如果m可被4整除，则a - 1必须可被4整除。

我们的模数是2 ^ 32，这意味着a必须是4k + 1的形式，其中k是任意整数，而c不可被2整除。

虽然这是一个关于C#的问题，但我编写了一个小的C++程序来测试该解决方案的速度，因为我更熟悉那种语言：

#include <iostream>
#include <stdlib.h>

class lcg {
private:
    unsigned a, c, val;
public:
    lcg(unsigned seed=0) : lcg(seed, rand() * 4 + 1, rand() * 2 + 1) {}
    lcg(unsigned seed, unsigned a, unsigned c) {
        val = seed;
        this->a = a;
        this->c = c;
        std::cout << "Initiated LCG with seed " << seed << "; a = " << a << "; c = " << c << std::endl;
    }

    unsigned next() {
        this->val = a * this->val + c;
        return this->val;
    }
};

int main() {
    srand(time(NULL));
    unsigned seed = rand();
    int dummy = 0;
    lcg gen(seed);
    time_t t = time(NULL);
    for (uint64_t i = 0; i < 0x100000000ULL; i++) {
        if (gen.next() < 1000) dummy++; // Avoid optimizing this out with -O2
    }
    std::cout << "Finished cycling through. Took " << (time(NULL) - t) << " seconds." << std::endl;
    if (dummy > 0) return 0;
    return 1;
}

您可能注意到，在LCG类中我没有使用模数运算，这是因为我们使用32位整数溢出来进行取模操作。
这将产生范围内的所有值 [0, 4294967295] 。
我还不得不添加一个虚拟变量，以防止编译器优化掉一切。
在没有任何优化的情况下，这个解决方案大约需要15秒才能完成，而在-O2时，适度优化下可在5秒内完成。

如果不需要“真正”的随机性，则这是一个非常快的解决方案。