我想在特定范围内生成随机数,并确保每个新数字都不是以前的重复项。一种解决方案是将以前生成的数字存储在容器中,每个新数字检查容器。如果容器中有这样的数字,则我们再次生成,否则我们使用并将其添加到容器中。但是,随着每个新数字的出现,此操作变得越来越慢。是否有更好的方法或任何可以更快地工作并确保生成独特性的rand函数?
编辑:是的,有一个限制(例如从0到10亿)。但我想生成100,000个唯一数字!(如果解决方案使用Qt功能将非常好。)
我想在特定范围内生成随机数,并确保每个新数字都不是以前的重复项。一种解决方案是将以前生成的数字存储在容器中,每个新数字检查容器。如果容器中有这样的数字,则我们再次生成,否则我们使用并将其添加到容器中。但是,随着每个新数字的出现,此操作变得越来越慢。是否有更好的方法或任何可以更快地工作并确保生成独特性的rand函数?
编辑:是的,有一个限制(例如从0到10亿)。但我想生成100,000个唯一数字!(如果解决方案使用Qt功能将非常好。)
随机生成器不可能根据先前输出的值输出值,因为它们不会是随机的。但是,您可以通过使用不同的随机值池来提高性能,每个池都有一个不同的盐值组合的值,这将把要检查的数字数量除以您拥有的池的数量。
如果随机数的范围不重要,您可以使用非常大的随机数范围,并希望您不会遇到任何碰撞。如果您的范围比您预计创建的元素数量大数十亿倍,则发生碰撞的几率很小但仍然存在。如果数字没有实际的随机分布,您可以使用由两部分组成的数字{计数器} {随机x个数字},这将确保一个唯一的数字,但其分布不是随机的。
在返回结果数量上,没有一个纯函数式方法不是O(n^2)的 - 每次生成一个数字时,您都需要检查到目前为止的每个结果。此外,考虑一下当您返回例如1000个中的第1000个数字时会发生什么 - 平均需要尝试1000次,直到随机算法找到最后一个未使用的数字,每次尝试需要与已生成的数字进行平均499.5次比较。
从这个例子可以清楚地看出,您发布的描述并不完全符合您的要求。更好的方法是像其他人建议的那样,提前获取一个包含1000个数字的列表,对其进行洗牌,然后逐步从该列表中返回数字。这将确保您不会返回任何重复项,并且在初始设置后以O(1)时间返回数字。
你可以为每个可能的数字分配一个位,为位数组分配足够的内存,并检查/设置每个生成的数字的位。例如,对于从0到65535的数字,您只需要8192(8kb)的内存。
这是我想出的一个有趣的解决方案:
假设你有数字1到1000,但内存不够用。
你可以把所有1000个数字放入一个数组中,然后逐个删除,但会导致内存溢出错误。
你可以将数组分成两部分,一部分是1-500的数组,另一部分为空数组。
然后你可以检查数字是否存在于数组1中,或者不存在于第二个数组中。
因此,假设你有1000个数字,你可以从1-1000中随机选择一个数字。如果它小于500,则检查数组1并在其中删除它。如果它不在数组2中,你可以添加它。
这样可以减少一半的内存使用。
如果你使用递归来推广这个方法,你可以将你的500个数组分成250和空数组。
假设空数组不占用空间,你可以大大减少内存使用。
搜索速度也会大大加快,因为如果你将其分解,你会生成一个数字,例如29。它小于500,小于250,小于125,小于62,小于31,大于15,所以你进行这6个计算,然后检查包含平均16/2个项目-总共8个的数组。
我应该申请专利这种搜索方法,尽管我打赌它已经存在了!
当你放入下一个数字时,使用该函数来获取索引并检查该值是否存在。如果不存在,则放入;如果存在,则创建新的数字并尝试。你可以以最快的方式使用这种方法创建。这种方式的缺点是你永远无法找到末尾部分相同的数字。
例如,对于末尾部分为: 1231232444556 3458923444556
即使它们完全不同,但你的列表中永远不会有这样的数字。
如果一个值可以由前一个值计算出来,那么使用LFSR和LCG是没问题的。但是当你不希望一个输出值可以被另一个值计算出来时,你可以使用块密码在计数器模式下生成输出序列,前提是密码块长度等于输出长度。
HashSet<int> array = new HashSet<int>();
array.Add(1);
array.Add(2);
array.Add(1);
foreach (var item in array)
{
Console.WriteLine(item);
}
Console.ReadKey();
C++
,我会给予我的 +1。 - ereOnstd::unordered_set<>
,添加元素使用其insert()
成员函数完成,没有foreach
循环(但是),我们通过执行std::cout << item << '\n';
将行写入控制台,并使用std::getline()
读取。但是除了每一行都至少包含一个错误之外,它是有效解决方案的坚实基础(随机数生成器从哪里开始呢?),所以我不会对其进行负面评价。 :)
- sbi