Pi = 3.14159 26 5358979323846 26 433 ...所以重复的第一个2位数子串是26.
找到重复的第一个20位子字符串的有效方法是什么？
我有大约500千兆字节的Pi(每个数字1个字节),大约500千兆字节的磁盘空间.
我有大约5千兆字节的RAM免费.
我感兴趣的是一种适用于任意序列的高效算法,而不是Pi本身的特定答案.换句话说,即使打印的数字是正确的,我对"print 123 .... 456"形式的解决方案也不感兴趣.
我将每个子字符串放入一个哈希表并报告第一次碰撞.
(哈希表构造为排序链表的数组.数组的索引由字符串的底部数字(转换为整数)给出,并且存储在每个节点中的值是Pi扩展中的位置子串最初出现的地方.)
这工作正常,直到我用完RAM.
为了扩展到更长的序列,我考虑过:
为从特定范围开始的所有子字符串生成哈希值,然后继续搜索其余数字.这需要为每个范围重新扫描整个Pi序列,因此变为N ^ 2阶
将一组20位子串分组到多个文件,然后使用哈希表分别查找每个文件中的第一个重复.不幸的是,使用这种方法,我的磁盘空间不足,因此需要20次通过数据.(如果我以1000位开头,那么我最终会得到1000个20位数的子串.)
每字节存储2位Pi,以释放更多内存.
将基于磁盘的后备存储添加到我的哈希表.我担心这会表现得非常糟糕,因为没有明显的参考地点.
有更好的方法吗？
我尝试了Adrian McCarthy的qsort方法,但这似乎比找到重复的哈希慢一点
我查看了btilly的MapReduce建议,用于并行化算法,但它在我的单台计算机上严重IO绑定,因此不适合我(使用我的单个磁盘驱动器)
我实现了supercat的方法,用于昨晚分割文件并在前180亿个数字中搜索19位数字的子串.
这找到16场比赛,所以我用Jarred的建议重新检查19位数的比赛,找到前20位数的比赛
要搜索180亿个数字需要3个小时来分割文件,然后40分钟再重新扫描文件以查找匹配项.
在Pi的十进制扩展内,在位置1,549,4062,637和17,601,613,330处找到20位子串84756845106452435773.
非常感谢大家!
这是一个有趣的问题.
首先让我们回顾一下信封号码.任何特定的20位数序列将在10 20中匹配一次.如果我们走出去到第n位,我们有大约N个2 /2双20个序列.因此,为了找到匹配的好机会,我们可能需要在10 10以上.假设我们每个记录占用40个字节,我们将需要大约400 GB数据的东西.(我们实际上需要比这更多的数据,因此我们应该为超过1TB的数据做好准备.)
这让我们了解了所需的数据量.数十亿的数字.数百GB的数据.
现在这是问题所在.如果我们使用任何需要随机访问的数据结构,则随机访问时间由磁盘速度设置.假设您的磁盘速度为6000 rpm.那是每秒100次.平均而言,您想要的数据是磁盘的中间位置.所以你平均每秒可以获得200次随机访问.(这可能因硬件而异.)访问它100亿次需要5000万秒,这是一年多的时间.如果你读,然后写,并最终需要200亿个数据点 - 你超过了硬盘的预计寿命.
另一种方法是以不随机访问的方式处理一批数据.经典是做一个好的外部排序,如合并排序.假设在排序期间我们有1 TB的数据,我们读了30次,写了30次.(两个估计都高于需要,但我在这里描绘的是最糟糕的情况.)假设我们的硬盘具有100 MB/s的持续吞吐量.然后每次通过需要10,000秒,持续600,000秒,这稍微低于一周.这是非常可行的!(实际上它应该比这更快.)
所以这是算法:
现在这很好,但是如果我们不想花一个星期呢？如果我们想要多台机器怎么办？事实证明这很容易.有众所周知的分布式排序算法.如果我们将初始文件拆分为块,我们可以并行化步骤1和4.如果在步骤4之后我们找不到匹配,那么我们可以从一开始就用更大的输入块重复.
实际上这种模式很常见.所有真正不同的是将初始数据转换为要排序的东西,然后查看匹配的组.这是http://en.wikipedia.org/wiki/MapReduce算法.这对于这个问题也会很好.
您的数据集非常大，因此需要某种“分而治之”的方法。我建议第一步，将问题细分为一定数量的部分（例如 100）。首先查看文件是否有任何以 00 开头的重复 20 位序列，然后查看是否有以 01 开头的重复序列，以此类推，直至 99。通过将所有以正确数字开头的 20 位数字序列。如果前两位数字不变，则只需写出最后 18 位；由于 18 位十进制数可容纳 8 字节“长”，因此输出文件可能会容纳大约 5,000,000,000 个数字，占用 40GB 磁盘空间。请注意，一次生成多个输出文件可能是值得的，以避免读取源文件的每个字节 100 次，但如果您只是读取一个文件并写入一个文件，磁盘性能可能会更好。
一旦生成了特定“主通道”的数据文件，就必须确定其中是否存在重复项。根据存储在其中的数字中的位将其细分为一些较小的部分可能是下一步的好方法。如果将其细分为 256 个较小的部分，则每个部分大约有 16-3200 万个数字；5 GB 的 RAM 可用于为 256 个存储桶中的每个存储桶缓冲一百万个数字。写出一百万个数字的每个块将需要随机磁盘寻道，但此类写入的数量相当合理（可能大约 10,000 次磁盘寻道）。
将数据细分为每个包含 16-3200 万个数字的文件后，只需将每个此类文件读入内存并查找重复项即可。
所描述的算法可能不是最优的，但应该相当接近。最有趣的是，将主遍数减少一半，就会将必须读取源数据文件的次数减少一半，但一旦数据被读取，处理每遍所需的时间就会增加一倍多。复制的。我猜测使用 100 次遍历源文件可能不是最佳的，但使用该分割因子的整个过程所需的时间将非常接近使用最佳分割因子的时间。