13

问题

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 阶

  • Bucket 将这组 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。

非常感谢大家！

4

4 回答 4

6

这是一个有趣的问题。

首先让我们做一些信封号码的背面。任何特定的 20 位数字序列将在 10 20中匹配一次。如果我们走到第 n 位，我们大约有 n 2 /2 对 20 位序列。因此，为了找到匹配的几率，我们可能需要 na 略高于 10 10。假设我们每条记录占用 40 字节，我们将需要大约 400 GB 的数据。（我们实际上需要比这更多的数据，所以我们应该为超过 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. 重复此搜索。

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

事实上，这种模式很常见。真正不同的是把初始数据变成要排序的东西，然后查看匹配的组。这是http://en.wikipedia.org/wiki/MapReduce算法。这将很好地解决这个问题。

于 2012-04-17T23:09:49.860 回答
4

Trie

RBarryYoung has pointed out that this will exceed the memory limits.

A trie data structure might be appropriate. In a single pass you can build up a trie with every prefix you've seen up to length n (e.g., n = 20). As you continue to process, if you ever reach a node at level n that already exists, you've just found a duplicate substring.

Suffix Matching

Another approach involves treating the expansion as a character string. This approach finds common suffixes, but you want common prefixes, so start by reversing the string. Create an array of pointers, with each pointer pointing to the next digit in the string. Then sort the pointers using a lexicographic sort. In C, this would be something like:

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

When the qsort finishes, similar substrings will be adjacent in the pointer array. So for every pointer, you can do a limited string comparison with that string and the one pointed to by the next pointer. Again, in 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
  }
}

The sort is (typically) O(n log_2 n), and the search afterwards is O(n).

This approach was inspired by this article.

于 2012-04-17T19:48:13.170 回答
2

也许这样的事情会起作用：

  1. 搜索长度为 2 的重复子串（或一些小的基本情况），记录起始索引 S={s_i}

  2. 对于 n=3..N，从 S 中的索引中查找长度为 n 的子串

  3. 每次迭代，用长度为 n 的子串更新 S

  4. 在 n=20 时，前两个指标将是您的答案

您可能想要调整初始大小和步长（可能不需要每次都以 1 为单位）

于 2012-04-17T19:11:56.760 回答
2

您的数据集非常大，因此需要某种“分而治之”。我建议作为第一步，您将问题细分为若干个部分（例如 100 个）。首先查看文件是否有任何重复的以 00 开头的 20 位序列，然后查看是否有任何以 01 开头的序列，以此类推直到 99。通过将所有以正确数字开头的 20 位序列。如果前两位数不变，则只需写出后 18 位；由于 18 位十进制数字适合 8 字节“长”，因此输出文件可能包含大约 5,000,000,000 个数字，占用 40GB 磁盘空间。请注意，一次生成多个输出文件可能是值得的，

一旦为特定的“主要通道”生成了数据文件，就必须确定其中是否有任何重复。根据存储在其中的数字中的位将其细分为一些较小的部分可能是一个很好的下一步。如果将其细分为 256 个较小的部分，则每个部分将有大约 16-32 百万个数字；5 GB 的 RAM 可用于为 256 个存储桶中的每一个存储一百万个数字。写出一百万个数字的每一块都需要随机磁盘寻道，但这样的写入次数相当合理（可能大约 10,000 次磁盘寻道）。

将数据细分为每个包含 16-32 百万个数字的文件后，只需将每个此类文件读入内存并查找重复项即可。

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

于 2012-04-17T22:20:07.457 回答