在.NET中生成所有整数的随机，非重复序列
在.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
我刚刚测试了线性同余发生器 ，我可以说我对结果非常满意。 对于这个post中的赢家位置来说，它看起来像是一个强有力的竞争者。
正确性 ：所有整数只生成一次（我使用了一个位向量来检查）。
随机性 ：相当不错。
内存使用 ：非常好，只需几个字节。
运行时间 ：非常快速地生成下一个随机整数，正如您可以从O（1）算法中获得的那样。 生成每个整数总共花费大约。 在我的机器上11秒。
总而言之，如果你不寻找高度随机化的序列，我会说这是一种非常合适的技术。
更新4
下面描述的模乘乘逆技术与LCG技术非常相似 – 这并不奇怪，因为两者都是基于模运算 – 虽然我发现它实现起来不那么简单，以便产生令人满意的随机序列。
我发现一个有趣的区别是这种技术似乎比LCG更快：生成整个序列需要大约8秒，而LCG则需要11秒。 除此之外，关于内存效率，正确性和随机性的所有其他评论都是相同的。
更新5
看起来用户TomTom在没有通知的情况下删除了他们的答案，我在评论中指出，我发现它比所需的更快地生成重复的数字。 所以我想这完全排除了Mersenne Twister。
更新6
我测试了另一种看起来很有前景的建议技术， Skip32 ，虽然我非常喜欢随机数的质量，但算法并不适合在可接受的时间内生成整个整数范围。 所以不幸的是，与其他能够完成这一过程的技术相比，它不足。 顺便说一句，我在C＃中使用了C＃的实现 – 我更改了代码以将轮数减少到1，但仍然无法及时完成。
毕竟，根据上述结果判断，我个人对解决方案的选择是模块乘法逆变技术，紧接着是线性同余生成器 。 有些人可能会争辩说，这在某些方面比其他技术要差，但鉴于我原来的限制，我认为它最适合他们。
在.NET中有没有办法
实际上，这可以用大多数语言来完成
生成所有32位整数的序列（Int32）
是。
按随机顺序，
在这里我们需要就术语达成一致，因为“随机”并不是大多数人认为的。 稍后详细介绍。
没有重复，
是。
并以记忆效率的方式？
是。
内存效率意味着最多只能使用几百兆字节的主内存。
好的，几乎没有记忆可以接受吗？ 😉
在得出建议之前，我们需要澄清“随机性”的问题。 真正随机的东西没有明显的模式。 因此，连续数百万次运行算法理论上可以在所有迭代中返回相同的值。 如果你抛出“必须与先前的迭代不同”的概念，那么它就不再是随机的。 然而，综合考虑所有要求，似乎所有真正被要求的是“整数分布的不同模式”。 这是可行的。
那么如何有效地做到这一点？ 使用Modular乘法逆 。 我用它来回答以下问题，该问题在某些范围内生成非重复的伪随机样本数据的要求类似：
在给定的时间间隔内生成不同的随机时间
我在这里首先了解了这个概念（ 在SQL Server中生成看似随机的唯一数字ID ），您可以使用以下任一在线计算器来确定您的“整数”和“模块化乘法反转（MMI）”值：
在此处应用该概念，您将使用Int32.MaxSize作为Modulo值。
这将给出随机分布的明确外观，没有碰撞的可能性并且不需要存储器来存储已经使用的值。
唯一的初始问题是，在给定相同的“整数”和“MMI”值的情况下，分布模式总是相同的。 所以，你可以通过在起始值中添加一个“随机”生成的Int来提出不同的模式（我相信我在关于在SQL Server中生成示例数据的答案中做了），或者你可以预先生成几个组合“整数“和相应的”MMI“值，将它们存储在配置文件/字典中，并使用.NET随机函数在每次运行开始时选择一个。 即使您存储了100种组合，也几乎没有内存使用（假设它不在配置文件中）。 实际上，如果同时存储Int和字典使用Int作为索引，那么1000个值大约是12k？
UPDATE
笔记：
- 结果中有一种模式，但除非你在任何特定时刻有足够的模式来总体看，否则它是不可辨别的。 对于大多数用例，这是可以接受的，因为没有值的接收者会有大量的集合，或者知道它们是按顺序分配的，没有任何间隙（并且需要知识才能确定是否存在模式） 。
- 在特定运行的公式中，只需要两个变量值中的一个 – “整数”和“模数乘法逆（MMI）”。 因此：
- 每对给出两个不同的序列
- 如果在内存中维护一个集合，只需要一个简单的数组，并假设数组索引只是内存中与数组基址的偏移量，那么所需的内存应该只有4个字节*容量（即1024个选项是只有4k，对吗？）
这是一些测试代码。 它是用Microsoft SQL Server的T-SQL编写的，因为这是我主要工作的地方，它还具有使其真正易于测试唯一性，最小值和最大值等的优点，而无需编译任何东西。 该语法适用于SQL Server 2008或更高版本。 对于SQL Server 2005，尚未引入变量的初始化，因此每个包含= DECLARE只需要自己分成DECLARE ，而SET @Variable = ...但是该变量正在被初始化。 并且SET @Index += 1; 需要成为SET @Index = @Index + 1; 。
如果提供产生任何重复项的值，则测试代码将出错。 并且最后的查询表明是否存在任何差距，因为可以推断出如果表变量总体没有错误（因此没有重复）， 并且值的总数是预期的数量，则可能只有间隙（即缺失）如果实际MIN和MAX值中的任何一个或两个都在预期值之外。
请注意，此测试代码并不意味着任何值是预先生成的或需要存储的。 代码仅存储值以测试唯一性和最小/最大值。 在实践中，所需要的只是简单的公式，而传递给它的所有内容都是：
- 容量（虽然在这种情况下也可以硬编码）
- MMI / Integer值
- 目前的“指数”
所以你只需要保持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;
如果您不需要随机数加密安全，则可以使用线性同余生成器 。
LCG是X_n + 1 = X_n * a + c（mod m）forms的公式，对于每个生成的数字，它需要恒定的存储器和恒定的时间。
如果选择了适当的LCG值，它将具有一个完整的周期长度，这意味着它将输出介于0和您选择的模数之间的每个数字。
当且仅当以下情况时，LCG才有完整的期限：
- 模量和增量是相对质数，即
GCD(m, c) = 1 -
a - 1可被m所有素因子整除 - 如果
m可被4整除，则a - 1必须可被4整除。
我们的模数是2 ^ 32 ，意味着必须是4k + 1的forms，其中k是任意整数， c必须不能被2整除。
虽然这是一个C＃问题，但我编写了一个小型C ++程序来测试这个解决方案的速度，因为我对这种语言感觉更舒服：
#include #include 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秒内完成适度优化。
如果“真实”随机性不是问题，这是一个非常快速的解决方案。
CTR模式下的32位PRP似乎是我唯一可行的方法（您的第四种变体）。
你也可以
-
使用专用的32位分组密码。
Skip32，Skipjack的32位变体是一个受欢迎的选择。
作为质量/安全性和性能之间的权衡，您可以根据需要调整轮数。 更多轮更慢但更安全。
-
长度保留加密（格式保留加密的特殊情况）
FFX模式是典型的建议。 但在其典型的实例化中（例如，使用AES作为底层密码），它将比专用的32位分组密码慢得多。
请注意，许多这些结构都有一个重大缺陷：它们甚至是排列。 这意味着一旦你看到2 ^ 32-2输出，你就能够确定地预测倒数第二个输出，而不是只有50％。 我认为Rogaways AEZ论文提到了解决这个缺陷的方法。
我将在这个问题的前言中说，我意识到其他一些答案更加优雅，并且可能比这个更适合您的需求。 对于这个问题，这当然是一种蛮力的方法。
如果获得真正随机的*（或伪随机*足以用于加密目的）很重要，您可以提前生成所有整数的列表，并将它们全部以随机顺序存储在磁盘上。 在程序运行时，您可以从磁盘中读取这些数字。
下面是我建议生成这些数字的算法的基本概要。 所有32位整数都可以存储在~16 GiB的磁盘空间中（32位= 4字节，4字节/整数* 2 ^ 32整数= 2 ^ 34字节= 16 GiB，加上OS /文件系统需要的任何开销），而且我已经花费了“几百兆字节”来表示你想要一次读取不超过256 MiB的文件。
- 生成16 GiB / 256 MiB = 64个ASCII文本文件，每个文本文件具有256 MiB的“空”字符（所有位设置为0）。 将每个文本文件命名为“0.txt”到“64.txt”
- 从Int32.MinValue到Int32.MaxValue顺序循环，跳过0.这是您当前存储的整数的值。
- 在每次迭代中，从您选择的随机源（硬件真随机生成器，伪随机算法，无论如何）生成从0到UInt32.MaxValue的随机整数。 这是您当前存储的值的索引。
- 将索引拆分为两个整数：6个最高有效位，其余为26.使用高位加载相应的文本文件。
- 将低26位乘以4并将其用作打开文件中的索引。 如果该索引后面的四个字节仍然是“空”字符，则将当前值编码为四个ASCII字符，并将这些字符存储在该位置。 如果它们不是所有“空”字符，请返回步骤3。
- 重复，直到存储了所有整数。
这将确保数字来自已知的随机来源但仍然是唯一的，而不是具有一些其他提出的解决方案的限制。 “编译”需要很长时间（特别是使用上面相对天真的算法），但它符合运行时效率要求。
在运行时，您现在可以生成随机起始索引，然后按顺序读取文件中的字节以获得唯一的，随机*，非重复的整数序列。 假设您一次使用相对较少的整数，您甚至可以随机索引到文件中，存储您使用的索引并确保数字不会以这种方式重复。
（*我理解通过强加“唯一性”约束来减少任何来源的随机性，但这种方法应该产生与原始来源相对接近的数字）
TL; DR – 提前对整数进行混洗，将所有这些整数存储在磁盘上的许多较小的文件中，然后在运行时根据需要从文件中读取。
由于您的定义中的数字应该是随机的 ，因此根据定义，除了存储所有数据之外没有其他方式，因为数字彼此之间没有内在关系。 因此，这意味着您必须存储您使用的所有值，以防止再次使用它们。
然而，在计算中没有真正的随机性。 通常，系统通过执行具有巨大预定值和定时器值的乘法运算来计算随机数，使得它们超出存储器限制并因此随机选择。 所以要么你使用你的第三个选项，要么你必须考虑生成这些伪随机数，你可以重现生成的每个数字的序列，并检查是否有重新复制的东西。 这显然在计算上非常昂贵但你要求内存效率。
因此，您可以存储随机生成器的种子数和您生成的元素数。 每次需要一个新数字时，重新设置生成器并迭代生成的元素数量+ 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亿个值之前溢出。
考虑到这一点，递归调用也不适用于此，因为它几乎肯定会导致堆栈溢出（并且不必要地占用大量内存） - 但我只是想给你一般的想法。
好难题。 我想到了一些事情：
- 我们需要存储已使用的项目。 如果大约足够好，您可能需要使用布隆filter。 但是既然你明确表示你想要所有数字，那么只有一个数据结构：一个位向量。
- 您可能希望使用长周期的伪随机生成器算法。
- 解决方案可能涉及使用多种算法。
我的第一个尝试是弄清楚伪随机数生成如何与简单的位向量一起工作。 我接受碰撞（因此减速），但绝对没有太多的碰撞。 这个简单的算法将在有限的时间内为您生成大约一半的数字。
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.74s（c = 10005932）[...] 2108000000随机在430.66s（c = 52837678）
所以，让我们为了争论说你将使用这个算法用于前+/- 20亿个数字。
接下来，您需要其余的解决方案，这基本上是OP描述的问题。 为此，我将随机数采样到缓冲区中，并将缓冲区与Knuth shuffle算法结合起来。 如果您愿意，也可以从一开始就使用此function。
这就是我想出来的（可能还有马车，所以测试...）：
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亿个数字，然后使用第二个算法。
One of the easiest solutions is to use an block encrytion algorithm like AES in countermode. You need a seed which equals the key in AES. Next you need a counter which is incremented for each new random value. The random value is the result of encrypting the counter with the key. Since the cleartext (counter) and the random number (ciphertext) is bijectiv and because of the pigeon hole principle the random numbers are unique (for the blocksize).
Memory efficiency: you only need to store the seed and the counter.
The only limmitation is that AES has 128 bit block size instead of your 32 bit. So you might need to increase to 128 bit or find a block cipher with 32 bit block size.
For your IEnumerable you can write a wrapper. The index is the counter.
Disclaimer: You are asking for non-repeating/unique: This disqualifies from random because normally you should see collisions in random numbers. Therefore you should not use it for a long sequence. See also https://crypto.stackexchange.com/questions/25759/how-can-a-block-cipher-in-counter-mode-be-a-reasonable-prng-when-its-a-prp
You could try this homebrew block-cipher:
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); }
I haven't checked the quality of its outputs yet. Runs in 19 sec on my computer for seedSize = 3 .