search - 在列出 pi 的前十亿位数字的 1 GB txt 文件中搜索任何数字序列（例如 334455）的简单快速方法是什么？

Question

这是在 Linux 环境中，以防万一。

pi.txt 是一个文本文件，列出了 pi 的前十亿位，全部在一行中（没有换行符，没有空格。）

现在要找到任意序列的字符位置，例如 334455，我正在这样做：

LANG=C grep -aob '334455' pi.txt | 头-1

这非常慢，我认为在这种情况下我已经尽可能地优化了 grep。以 100% 的速度消耗 CPU，大约需要 15 秒。

什么是更好的解决方案？

标签： searchpi

Answer 1

这个答案可能跑题了。如果是这样，我将删除我的答案。

您可以尝试预先构建搜索树以提高搜索速度，例如前缀树，它可以有效地折叠搜索时间。

但是，就我目前的想法而言，为 Pi 构建一个搜索树几乎等于为所有查询构建一个字典/缓存......

以下只是对https://www.angio.net/pi/how.html的简单总结。

直接使用grep，更有可能进行线性搜索，这很慢而且很“胖”。

• 对于“胖”：根据 ASCII，我们知道数字位于 的区域中0x3*，在 Pi 的文本表示中，左 nybble3一直重复，如果我们只想进行搜索，可以折叠。例如，存储14159265在磁盘中可以优化为存储0x14 0x15 0x92 0x65而不是 ASCII 存储0x31 0x34 0x31 0x35 0x39 0x32 0x36 0x35。

• 对于慢速：如果输入很长，那么我们可以打包前 4 位，就像我们之前打包 Pi 一样。然后我们可以对 2 位数字进行一次比较，与每次比较只比较 1 位数字的朴素线性搜索相比。

然后，他们做了一些基准测试并使用了混合搜索：

• 对于长度 <= 5 的搜索，它们会如前所述进行线性搜索。

• 对于更长的搜索，他们在后缀数组的帮助下进行索引搜索。

然后，他们将搜索引擎从 C++ 重写为 Go。