假设我们希望生成一个没有重复的10000000个随机32位整数的序列。我们该怎么做？
我最近遇到了这个问题，在最终实现自定义的，非重复的伪随机数生成器（运行时间为O（1），仅需要8个字节的存储空间，并且分布良好）之前，考虑了几种选择。我以为我会在这里分享细节。
已经有几种众所周知的伪随机数生成器（PRNG），例如Mersenne Twister，这是一种出色的PRNG，可以在整个32位范围内均匀地分配整数。不幸的是，将此PRNG调用10000000次并不会生成10000000个唯一值的序列。根据哈希冲突概率，所有10000000个随机数唯一的概率为：
从天文学角度讲，这不太可能。实际上，此类序列中唯一值的预期数量仅约为9988367。您可以使用Python自己尝试一下：
一种明显的改进是拒绝序列中已经存在的随机数，并继续进行迭代，直到达到10000000个元素为止。要检查序列中是否已存在特定值，可以线性搜索，也可以保留序列的排序副本并使用二进制搜索。我们甚至可以使用巨型512 MB位域或稀疏位域（例如Judy1数组）显式跟踪每个值的存在。
另一种改进：我们可以为每个元素生成一个范围为[0，N）的随机索引，而不是为每个元素生成一个任意的32位整数，并希望它是唯一的，其中N是剩余的未使用值的数量。索引会告诉我们接下来要使用哪个空闲时段。通过实现适合此目的的特里，我们可能可以在对数时间内找到每个空闲插槽。
集思广益，基于Fisher-Yates Shuffle的方法也很诱人。使用这种方法，我们可以从一个包含所有可能的32位整数的数组开始，然后将数组中的前10000000个值混洗以获得序列。那将需要16 GB的内存。可以通过将数组表示为稀疏关联映射（例如JudyL数组）来减少占用空间，该数组仅存储x，其中A [x]≠x。或者，我们可以从任何10000000个排序整数的初始序列开始，而不是从所有可能的32位整数的数组开始。为了扩展32位值的可用范围，我们甚至可以将初始序列建模为泊松过程。
以上所有方法要么在非线性时间内运行，要么需要大量存储。它们中的几个对于仅10000000个整数的序列都是可行的，但是让我开始思考是否有可能采用一种更有效的方法，该方法可以扩展到任意序列长度。
解决此问题的理想PRNG是一个会在我们调用它的前2 32次中生成一个唯一的随机整数，然后在随后调用它的2 32次中无限期重复相同的序列。换句话说，一个2 32个值的重复循环。这样，我们可以在循环中的任何时候开始PRNG，并始终保证接下来的2 32个值是无重复的。
实现此类PRNG的一种方法是在整数上定义一对一函数-该函数将每个32位整数唯一地映射到另一个整数。我们称这种功能为置换。如果我们想出一个很好的排列，我们所需要的只是用增加的输入{0，1，2，3，…}来称呼它。我们甚至可以以任何值开始输入序列。
出于某种原因，我从一年级有限数学中记得，当p是素数时，\（x ^ 2 \，\ bmod \，p \）具有一些有趣的特性。以这种方式产生的数字称为二次余数，我们可以使用表达式x * x％p在C中计算它们。特别地，x的二次残基只要\（2x ＜p \）是唯一的。例如，当p = 11时，二次残基0、1、2、3、4、5都是唯一的：
幸运的是，对于剩余的整数，表达式p-x * x％p也恰好适合剩余的插槽。这仅适用于满足\（p \ equiv 3 \，\ bmod \，4 \）的素数p。
这使我们对小于p的整数进行一对一置换，其中p可以是满足\（p \ equiv 3 \，\ bmod \，4 \）的任何素数。似乎是构建自定义PRNG的好工具。
就我们的自定义PRNG而言，我们需要一个排列，该排列适用于整个32位整数范围。但是，2 32不是质数。小于2 32的最接近质数是4294967291，它恰好满足\（p \ equiv 3 \，\ bmod \，4 \）。作为一种折衷方案，我们可以编写一个C ++函数，对所有低于此质数的整数进行置换，然后将剩余的5个整数相互映射。
unsigned int permuteQPR（无符号int x） { 静态const unsigned int质数= 4294967291; 如果（x＆gt; =质数） 返回x; //超出范围的5个整数将映射到它们自己。 无符号整数残基=（（（unsigned long long）x x x）％素数; 返回（x＆lt; =素数/ 2）？残留物：素-残留物; }
此功能本身并不是世界上最好的排列-它倾向于将输出值聚集在某些输入范围内-但它是一对一的。因此，我们可以将其与其他一对一功能（例如加法和XOR）结合使用，以实现更好的置换。我发现以下表达式相当有效。 IntermediateOffset变量充当种子，使我们可以使用各种不同的序列。
在GitHub上，我发布了一个C ++类，该类基于该表达式实现了伪随机数生成器。
我还发布了一个工作项目，以验证PRNG确实输出2 32个唯一整数的循环。
那么，该发生器的随机性如何堆积？我不是PRNG专家，所以我信任由蒙特利尔大学发布的TestU01，这是一个用于测试PRNG质量的库。这是一些测试代码，可以使我们新构思的PRNG逐步发展。它通过了TestU01的SmallCrush测试套件中的所有15个测试，我认为这相当不错。它还在更严格的Crush套件中通过了140/144测试。
========= SmallCrush的摘要结果========= 版本：TestU01 1.2.3 生成器：ursu_CreateRSU 统计数量：15 CPU总时间：00：00：49.95 所有测试均通过
可能已经知道这种用于生成唯一随机数序列的方法，或者它可能与现有PRNG共享属性。如果是这样，我很想找出答案。如果需要，您可能也可以使其适应于除2 32以外的整数范围。环顾四周，我注意到OpenBSD实现了另一个非重复的PRNG，尽管我不确定它们的实现是周期性的还是覆盖整个数字空间。
顺便说一句，我的下一篇文章“此哈希表比Judy数组快”中使用了PRNG。