有效地计算在Pi的十进制展开中重复的第一个20位子串

Question

Pi=3.14159 26 535 8979323846 26 433...所以要重复的第一个2位数子字符串是26。

找到要重复的第一个20位数子串的有效方法是什么？

>

我有大约500千兆字节的Pi数字（每个数字1字节），大约500千兆字节的磁盘空间可用。

我有大约5GB的内存空闲。

这很好，直到我用完了内存。

为了扩展到更长的序列，我考虑过：

>

为从某个范围开始的所有子字符串生成哈希，然后继续搜索剩余的数字。这需要重新扫描每个范围的整个Pi序列，因此成为顺序n^2

Bucket将一组20位数的子字符串排序到多个文件，然后使用哈希表分别查找每个文件中的第一个重复。不幸的是，使用这种方法，我将耗尽磁盘空间，因此需要对数据进行20次传递。（如果我从1000个数字开始，那么我将得到1000个20个数字的子串。）

每字节存储2位圆周率以释放更多内存。

>

我尝试了Adrian McCarthy的qsort方法，但这似乎比散列查找重复项慢一点

我查看了Btilly的MapReduce的并行算法建议，但它在我的单机上被严重绑定了IO，所以不适合我（用我的单机磁盘驱动器）

我实现了Supercat的方法，在昨晚拆分文件并在前180亿位数中搜索19位数的子字符串。

非常感谢大家！

Answer 1

这是一个有趣的问题。

首先，让我们做一些信封后面的号码。任何20位数字的特定序列都将在10²⁰中匹配一次。如果我们到第n个数字，我们大约有n²/2对20个数字序列。因此，为了有很好的几率找到匹配，我们可能需要n略高于10¹⁰。假设我们每条记录占用40字节，我们将需要大约400 GB的数据。（我们实际上需要比这更多的数据，所以我们应该为超过太字节的数据做好准备。）

这给了我们一个所需数据量的概念。几百亿位数。数百GB的数据。

现在问题来了。如果我们使用任何需要随机访问的数据结构，随机访问时间由磁盘速度设置。假设您的磁盘运行速度为6000转。每秒100次。平均而言，您需要的数据位于磁盘的一半。所以你平均每秒得到200次随机访问。（这可能因硬件而异。）访问它100亿次将需要5000万秒，这是一年多的时间。如果你读，然后写，最终需要200亿个数据点--你已经超过了你的硬盘的预期寿命。

另一种方法是以不随机访问的方式处理一批数据。经典的是做好外部排序，这样的合并排序。假设我们有1TB的数据，在排序过程中，我们读30次，写30次。（两个估计都比需要的要高，但我在这里画了一个最坏的情况。）假设我们的硬盘具有100 Mb/s的持续吞吐量。然后每一次通过需要10，000秒，为600，000秒，略低于一周。这是非常可行的！（实际上应该比这更快。）

以下是算法：

1. 从一长串数字开始，3141...
2. 将其转换成一个大得多的文件，其中每行为20位数字，后面跟着pi中出现的位置。
3. 对这个较大的文件进行排序。
4. 搜索排序文件中的任何重复项。
   1. 如果找到任何值，则返回第一个值。
   2. 如果没有找到，请重复步骤1-3并使用另一大块数字。
   3. 将其合并到前一个排序文件中。
   4. 重复此搜索。

   现在这是伟大的，但如果我们不想花一个星期呢？如果我们想向它扔多台机器呢？事实证明，这出奇地容易。有众所周知的分布式排序算法。如果我们将初始文件分成块，我们可以并行执行步骤1和步骤4。如果在第4步之后我们没有找到匹配项，那么我们可以从一开始就用更大的输入块重复。

   事实上，这种模式很常见。真正不同的是将初始数据转换为要排序的数据，然后查看匹配的组。这是http://en.wikipedia.org/wiki/mapreduce算法。这对这个问题很有效。