Pi = 3.14159 26 5358979323846 26 433 …因此，要重复的第一个2位数子字符串为26。
找到要重复的前20位子字符串的有效方法是什么？
我有大约500 GB的Pi数字（每位1字节），以及大约500 GB的可用磁盘空间。
我有大约5 GB的可用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分钟才能重新扫描文件以查找匹配项。
20位子字符串84756845106452435773位于Pi的十进制扩展内的位置1,549,4062,637和17,601,613,330处。
非常感谢大家！
您的数据集非常大，因此需要某种“分而治之”。我建议第一步，将问题细分为一定数量（例如100）。首先查看文件中是否有重复的20位序列（从00开始），然后查看文件中是否有任何以01开头（依此类推，直到99）。通过将所有“以正确数字开头的20位数字序列。如果前两位是常数，则只需要写出后18位即可；由于18位十进制数字将适合8字节的“长”，因此输出文件可能会容纳大约5,000,000,000个数字，占用40GB的磁盘空间。请注意，一次生成多个输出文件可能是值得的，
一旦为一个特定的“主要通行证”生成了数据文件，就必须确定其中是否有重复项。根据存储在其中的数字中的位将其细分为一些较小的部分可能是不错的下一步。如果将其细分为256个较小的部分，则每个部分将有大约16-3200万个数字。5 GB的RAM可以用来为256个存储桶中的每一个缓冲一百万个数字。写出一百万个数字的每个块都需要一个随机的磁盘搜索，但是这种写操作的数量将是相当合理的（大约10,000个磁盘搜索）。
将数据细分为每个16-32百万个数字的文件后，只需将每个这样的文件读入内存并查找重复项即可。
所描述的算法可能不是最佳算法，但是应该相当接近。最令人感兴趣的事实是，将主要通道的数量减少一半，将使源数据文件必须读取的次数减少一半，但是一旦其数据被处理，处理每个通道所需的时间将增加一倍以上。复制。我猜想在源文件中使用100次传递可能不是最佳选择，但是使用该分割因子的整个过程所需的时间将与使用最佳分割因子的时间非常接近。
