在Pi的十进制展开中高效地计算前20位子串以重复

Question

问题

Pi = 3.14159 26 5358979323846 26 433.所以要重复的第一个2位数的子串是26.

找到要重复的前20位子串的有效方法是什么？

约束条件

• 我有大约500 of的Pi数字(每位数字1字节)和大约500 of的空闲磁盘空间。
• 我有大约5G的内存免费。
• 我对一种有效的算法感兴趣，它适用于任意序列，而不是Pi本身的具体答案。换句话说，即使打印的数字是正确的，我对“打印123.456”表格的解决方案也不感兴趣。

我试过的

我将每个子字符串放入哈希表中，并报告第一次冲突。

(哈希表被构造为排序链接列表的数组。数组中的索引由字符串的底部数字(转换为整数)提供，每个节点中存储的值是首先出现子字符串的Pi展开中的位置。

在我用完内存之前，这一切都很顺利。

要扩展到更长的序列，我已经考虑过：

• 为从一定范围开始的所有子字符串生成散列，然后对其余的数字继续搜索。这需要重新扫描每个范围的整个Pi序列，因此成为N^2阶。
• 桶将20位子字符串的集合排序为多个文件，然后使用哈希表分别在每个文件中查找第一次重复。不幸的是，使用这种方法，我耗尽了磁盘空间，因此需要20次遍历数据。(如果我以1000位数开头，那么我将得到1000个20位的子字符串。)
• 每个字节存储2位Pi以释放更多内存。
• 向哈希表中添加基于磁盘的备份存储。我担心这样做会很糟糕，因为没有明显的参考地点。

有没有更好的方法？

更新

1. 我尝试过禤浩焯McCarthy的qsort方法，但这似乎比散列查找重复项的方法慢一些。
2. 我看了btilly关于并行化算法的MapReduce建议，但是它在我的单台计算机上被大量的IO绑定，所以不适合我(用我的单个磁盘驱动器)。
3. 我实现了超级猫的方法，昨晚把文件分割开来，在前180亿位数字中搜索19个数字子字符串。
4. 这发现了16位匹配，所以我使用Jarred的建议重新检查19位匹配，以找到前20位匹配。

搜索180亿位数需要3小时来拆分文件，然后用40分钟重新扫描寻找匹配的文件。

回答

在Pi的十进制展开中，20位数的子字符串84756845106452435773位于1,549,4062,637和17,601,613,330位置.

非常感谢大家！

Answer 1

您的数据集相当大，因此需要某种“分而治之”的方法。我建议，作为第一步，您可以将问题细分为若干部分(例如100)。首先查看文件是否有任何重复的20位序列，从00开始，然后查看它是否有任何从01开始的序列，等等，直到99。通过将以正确的数字开头的所有20位数的序列写到一个文件中，开始这些“主通行证”的每一个。如果前两位数是常量，您只需要写出最后的18位；因为一个18位数字的十进制数可以容纳8字节的“长”，输出文件可能容纳大约5,000,000,000个数字，占用40 of的磁盘空间。请注意，一次生成多个输出文件可能是值得的，这样可以避免读取源文件的每个字节100次，但如果只是读取一个文件并写入一个文件，则磁盘性能可能会更好。

一旦为特定的“主传递”生成了数据文件，就必须确定其中是否有任何副本。根据存储在其中的数字中的位将其细分为一些较小的部分可能是下一步的好方法。如果将其细分为256个较小的部分，每个部分将有大约1600万到3200万个数字；一个内存的5G可以用来为256个桶中的每个存储100万个数字。写出一百万个数字中的每一个块都需要一个随机的磁盘查找，但是这种写入的次数将是相当合理的(可能大约是10,000个磁盘查找)。

一旦数据被细分为1600万到3200万个数字的文件，只需将每个这样的文件读入内存并查找重复的文件。

所描述的算法可能不是最优的，但应该相当接近。最令人感兴趣的是这样一个事实，即将主传递次数减少一半将减少读取源数据文件的次数的一半，但一旦复制其数据后，处理每次传递所需的时间将增加一倍以上。我猜想使用100通过源文件可能不是最优的，但是使用这个拆分因子的整个过程所需的时间将非常接近使用最优拆分因子的时间。

Answer 2

Trie

RBarryYoung指出，这将超过内存限制。

trie数据结构可能是合适的。在一次传递中，您可以使用您所看到的长度为n的每一个前缀(例如，n= 20)建立一个trie。当您继续处理时，如果您到达一个已经存在的n级节点，您就会发现一个重复的子字符串。

后缀匹配

另一种方法是将展开处理为字符串。这种方法可以找到常见的后缀，但是您需要通用前缀，所以从反转字符串开始。创建一个指针数组，每个指针指向字符串中的下一个数字。然后使用字典排序对指针进行排序。在C语言中，这可能类似于：

qsort(array, number_of_digits, sizeof(array[0]), strcmp);

当qsort完成时，指针数组中类似的子字符串将相邻。因此，对于每个指针，您可以使用该字符串和下一个指针所指向的字符串进行有限的字符串比较。同样，在C语中：

for (int i = 1; i < number_of_digits; ++i) {
  if (strncmp(array[i - 1], array[i], 20) == 0) {
    // found two substrings that match for at least 20 digits
    // the pointers point to the last digits in the common substrings
  }
}

排序通常是O(n log_2 n)，之后的搜索是O(n)。

这种方法是受这篇文章启发的。

Answer 3

也许像这样的东西会起作用：

1. 搜索长度为2的重复子字符串(或一些小的大小写)，记录起始指示符S={s_i}
2. 对于n=3..N，从S中的索引中查找长度为n的子字符串
3. 每次迭代，用长度为n的子串更新S
4. 在n=20，前两项指控将是你的答案

您可能需要调整初始大小和步长(可能不需要每次1步)。