Gab*_* S. 29 .net c# random algorithm int
在.NET中是否有一种方法可以以随机顺序生成所有 32位整数(Int32)的序列,而不会重复,并且以内存效率的方式生成？内存效率意味着最多只能使用几百兆字节的主内存.
理想情况下,序列应该像a一样IEnumerable<int>,只有在请求时才会延迟返回下一个数字.
我做了一些快速研究,我找到了一些部分解决方案:
Random)直到它不重复,即它不在集合中 - 除了可能无法满足内存要求之外,在生成最后一个数字时它会变得非常慢顺序.有另一种方式来看待这个问题 - 也许是考虑值的固定范围内的优势 - 这将给予满足存储需求的解决方案？也许.NET类库带有一些有用的东西？
更新1
感谢大家对解决方案的见解和创意建议.我将尝试尽快实施和测试(正确性和内存效率)这里提出的2或3个最有希望的解决方案,发布结果然后选择"赢家".
更新2
我试着在下面的评论中实现hvd的建议.我尝试使用BitArray.NET和我的自定义实现,因为.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
下面描述的模乘乘逆技术与LCG技术的行为非常相似 - 这并不奇怪,因为两者都是基于模运算 - 尽管我发现为了产生令人满意的随机序列,它实现起来并不那么简单.
我发现一个有趣的区别是这种技术似乎比LCG更快:生成整个序列需要大约8秒,而LCG则需要11秒.除此之外,关于内存效率,正确性和随机性的所有其他评论都是相同的.
更新5
看起来用户TomTom在没有通知的情况下删除了他们的答案,我在评论中指出我发现它比所需的更快地生成重复的数字.所以我想这完全排除了Mersenne Twister.
更新6
我测试了另一种看起来很有前景的建议技术,Skip32,虽然我非常喜欢随机数的质量,但算法不适合在可接受的时间内生成整个整数范围.不幸的是,与能够完成该过程的其他技术相比,它不足.我在这里使用了C#中的实现,顺便说一下 - 我更改了代码以将轮数减少到1,但仍然无法及时完成.
毕竟,根据上述结果判断,我个人对解决方案的选择是模块乘法逆变技术,紧接着是线性同余生成器.有些人可能会争辩说,这在某些方面比其他技术要差,但鉴于我原来的限制,我认为它最适合他们.
Mat*_*on1 11
如果您不需要随机数加密安全,则可以使用线性同余生成器.
LCG是X_n + 1 = X_n*a + c(mod m)形式的公式,它对于每个生成的数字需要恒定的存储器和恒定的时间.
如果选择了适当的LCG值,它将具有一个完整的周期长度,这意味着它将输出介于0和您选择的模数之间的每个数字.
当且仅当以下情况时,LCG才有完整的期限:
GCD(m, c) = 1a - 1 被所有主要因素整除 mm可被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秒内完成.
如果"真实"随机性不是问题,这是一个非常快速的解决方案.
在.NET中有没有办法
实际上,这可以用大多数语言来完成
生成所有32位整数的序列(Int32)
是.
按随机顺序,
在这里我们需要就术语达成一致,因为"随机"并不是大多数人认为的.稍后详细介绍.
没有重复,
是.
并以记忆效率的方式？
是.
内存效率意味着最多只能使用几百兆字节的主内存.
好的,几乎没有记忆可以接受吗？;-)
在得到建议之前,我们需要澄清"随机性"问题.真正随机的东西没有明显的模式.因此,连续数百万次运行算法理论上可以在所有迭代中返回相同的值.如果你抛出"必须与先前的迭代不同"的概念,那么它就不再是随机的.然而,综合考虑所有要求,似乎所有真正被要求的是"整数分布的不同模式".这是可行的.
那么如何有效地做到这一点？使用Modular乘法反转.我用它来回答以下问题,该问题在某些范围内生成非重复的伪随机样本数据的要求类似:
我首先在这里了解了这个概念(在SQL Server中生成看似随机的唯一数字ID),您可以使用以下任一在线计算器来确定您的"整数"和"模块化乘法反转(MMI)"值:
在此处应用该概念,您将使用Int32.MaxSize作为Modulo值.
这将给出随机分布的明确外观,没有碰撞的可能性并且不需要存储器来存储已经使用的值.
唯一的初始问题是,在给定相同的"整数"和"MMI"值的情况下,分布模式总是相同的.所以,你可以通过在起始值中添加"随机"生成的Int来提出不同的模式(我相信我在关于在SQL Server中生成示例数据的答案中做了),或者你可以预先生成几个组合"整数"和相应的"MMI"值,将它们存储在配置文件/字典中,并使用.NET随机函数在每次运行开始时选择一个.即使您存储了100种组合,也几乎没有内存使用(假设它不在配置文件中).事实上,如果同时存储Int和字典使用Int作为索引,那么1000个值大约是12k？
UPDATE
笔记:
这是一些测试代码.它是用Microsoft SQL Server的T-SQL编写的,因为这是我主要工作的地方,它还具有使其真正易于测试唯一性,最小值和最大值等的优点,而无需编译任何东西.语法适用于SQL Server 2008或更高版本.对于SQL Server 2005,尚未引入变量的初始化,因此每个DECLARE包含a 的变量=只需要将其DECLARE自身分开,然后SET @Variable = ...对于该变量进行初始化.而且SET @Index += 1;需要成为SET @Index = @Index + 1;.
如果提供产生任何重复项的值,则测试代码将出错.并且最后的查询表明是否存在任何差距,因为可以推断出如果表变量总体没有错误(因此没有重复),并且值的总数是预期的数量,那么可能只有间隙(即缺失)如果实际MIN和MAX值中的任何一个或两个都在预期值之外.
请注意,此测试代码并不意味着任何值都是预先生成的或需要存储的.代码仅存储值以测试唯一性和最小/最大值.在实践中,所需要的只是简单的公式,而传递给它的所有内容都是:
所以你只需要保持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;
| 归档时间： |
|
| 查看次数： |
2863 次 |
| 最近记录： |