如何生成唯一(!)均匀分布随机数的数组/列表/序列
假设我生成了一个包,也就是说,一个由10个随机数和一个随机生成器组成的一维数组。然后我生成另一个由10个随机数组成的数组。我做了x次。我如何生成唯一的数组,即使经过一万亿代,也没有一个数组与另一个相等?
在一个数组中,元素可以是重复的。数组只需与其他数组不同,它的所有元素中至少有一个不同的元素。
这有什么简单的方法吗?是否有一些特殊的算法,通过为随机生成探索一些空间而不同地工作?我不知道。
一个简单的答案是将数组写入一个文件并检查它们是否已经生成,但是对随后较大的文件执行i/o操作需要太多时间。
编辑:编辑决定关闭我以前的主题。一位编辑修改了我的文本,然后评论并问我这是否是另一个问题的一部分,我解释了为什么不是。然后他在我面前的评论被删除了,见评论。然后有人通过引用虚假副本来结束这个主题。搞什么鬼?我又重新开门了。
3条答案
按热度按时间63lcw9qa1#
这是一个困难的请求,因为rng的特性之一是它应该随机重复序列。
您还存在试图记录TB以前结果的问题。您可以尝试的一件事是为现有数组形成一个哈希表(以提高搜索速度)。这在很大程度上取决于您是否有足够的ram来保存整个列表。
如果不是,您可以考虑磁盘Map某种类型的快速搜索结构。例如,您可以实现一个磁盘上的散列键二叉树,只要将树的大小增加一倍(使用插入),就可以重新平衡。这使您可以保持文件打开状态,并通过
seek
,而不需要表示内存中的完整文件。您还可以维护表的内存索引,用它来驱动
seek
到适当的文件部分,然后仅读取文件的一小部分进行最终搜索。这有助于集中您的实现吗?
thigvfpy2#
假设一个包中的10个数字都在[0..max]范围内。每个包可以被视为基数max+1中的10位数字。显然,max的大小决定了有多少个唯一的包。例如,如果max=9,则可能有1000000000个从[0000000000]到[9999999999]的唯一包。
然后问题就归结为在正确的范围内生成唯一的数字。
考虑到您的“万亿”,那么生成该范围内有保证的唯一数字的最佳方法可能是使用具有正确大小输出的加密。除非您想要64位(des)或128位(aes)输出,否则您将需要某种格式保留加密以获得所需范围内的输出。
对于输入,只需加密数字0、1、2。。。反过来加密保证,给定相同的密钥,每个唯一的输入的输出都是唯一的。您只需跟踪输入的数字到了什么程度。考虑到这一点,您可以根据需要在max施加的限制范围内生成更多独特的包。在这一点之后,输出将开始重复。
显然,作为最后一步,您需要将加密输出转换为10位数的base max+1数字,并将其放入数组中。
igetnqfo3#
重要警告:
这将不允许您“任意”生成许多独特的包。请参见@prune突出显示的限制。
请注意,随着请求包的数量接近唯一包的数量,查找包的时间越来越长。我还加了一个保险箱,这样经过一定次数的尝试后,它就放弃了。
请随意调整: