algorithm - 有效地计算在 Pi 的十进制扩展中重复的前 20 位子串

Question

问题

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

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

约束

• 我有大约 500 GB 的 Pi 数字(每个数字 1 个字节)和大约 500 GB 的可用磁盘空间。

• 我有大约 5 GB 的可用 RAM。

• 我对一种适用于任意序列的高效算法感兴趣，而不是对 Pi 本身的特定答案感兴趣。换句话说，我对“打印 123....456”形式的解决方案不感兴趣，即使它打印的数字是正确的。

我尝试过的

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

(哈希表是一个排序好的链表数组，数组中的索引由字符串的底部数字给出(转换为整数)，每个节点存储的值是在数组中的位置在子串第一次​​出现的地方展开 Pi。)

在我用完 RAM 之前，这一切正常。

我考虑过要扩展到更长的序列:

• 为从特定范围开始的所有子字符串生成散列，然后继续搜索其余数字。这需要为每个范围重新扫描 Pi 的整个序列，因此变成阶数 N^2

• 将 20 位子字符串集合分桶排序到多个文件，然后使用哈希表分别查找每个文件中的第一个重复项。不幸的是，使用这种方法我用完了磁盘空间，因此需要 20 次遍历数据。 (如果我以 1000 位数字开始，那么我将以 1000 个 20 位数字的子字符串结束。)

• 每字节存储 2 位 Pi 以释放更多内存。

• 将基于磁盘的后备存储添加到我的哈希表。我担心这会表现得很差，因为没有明显的引用位置。

有没有更好的方法？

更新

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

2. 我查看了 btilly 关于并行化算法的 MapReduce 建议，但它在我的单台计算机上受到严重 IO 限制，因此不适合我(使用我的单磁盘驱动器)

3. 昨晚我实现了supercat的方法来拆分文件，并在前180亿位中搜索19位子串。

4. 这找到了 16 个匹配，所以我使用 Jarred 的建议重新检查 19 个数字匹配以找到第一个 20 个数字匹配

搜索 180 亿个数字拆分文件需要 3 小时，然后重新扫描文件以查找匹配项需要 40 分钟。

回答

20 位子字符串 84756845106452435773 位于 Pi 的十进制扩展中的位置 1,549,4062,637 和 17,601,613,330。

非常感谢大家!

Answer 1

这是一个有趣的问题。

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

这让我们了解了所需的数据量。百亿位数。数百 GB 的数据。

问题来了。如果我们使用任何需要随机访问的数据结构，随机访问时间由磁盘速度设置。假设您的磁盘以 6000 rpm 的速度运行。那是每秒 100 次。平均而言，您想要的数据位于磁盘的一半位置。所以你平均每秒得到 200 次随机访问。 (这可能因硬件而异。)访问它 100 亿次将花费 5000 万秒，也就是一年多的时间。如果您先读再写，最后需要 200 亿个数据点 - 您已经超出了硬盘驱动器的预计使用生命周期。

另一种方法是以不随机访问的方式处理一批数据。经典的做法是进行良好的外部排序，例如合并排序。假设我们有 1 TB 的数据，我们在排序期间读取了 30 次，写入了 30 次。 (两个估计都高于需要，但我在这里描绘了最坏的情况。)假设我们的硬盘驱动器具有 100 MB/s 的持续吞吐量。然后每次通过需要 10,000 秒，共 600,000 秒，略低于一周。这是非常可行的! (实际上它应该比这更快。)

算法如下:

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

这很好，但如果我们不想花一周时间怎么办？如果我们想向它扔多台机器怎么办？事实证明这非常容易。有众所周知的分布式排序算法。如果我们将初始文件分成 block ，我们可以并行执行第 1 步和第 4 步。如果在第 4 步之后我们没有找到匹配项，那么我们可以使用更大的输入 block 从头开始重复。

其实这种模式很常见。真正不同的是将初始数据转换为要排序的内容，然后查看匹配的组。这是 http://en.wikipedia.org/wiki/MapReduce算法。这将很好地解决这个问题。