☰

Unix grep 使用长搜索词还是短搜索词速度更快？

tag-icon • tag-icon unix performance speed grep
Unix grep 使用长搜索词还是短搜索词速度更快？

查找长搜索词还是短搜索词更快？或者这是否会影响速度？换句话说，您是否应该使搜索词尽可能精确？

有超过 100,000 个文件，每个文件包含 20 到 5,000 多行数据。通常 grep 仅用于查找搜索词的一个实例。

假设搜索词是SEARCHTERM，它将出现在如下行中：

NAD+DP+1234567890:92++UNIQUE+NAME+SEARCHTERM++12345+FI'

查找“SEARCH”或“SEARCHTERM”哪个更快？假设在这种情况下我们不关心是否也在其他不相关的行中找到匹配项。

这是我目前的做法：

grep NAD+DP 123* | grep SEARCHTERM

但我发现它仍然很慢。通常需要大约 3-5 分钟才能找到数据，即使我知道大致的文件名，这也将范围限制在 10,000 个文件左右。

那么，更长或更短的搜索词会有帮助吗？据我所知，grep 会查找特定长度的单词“块”？

答案1

一些参考资料：

GNU grep 使用著名的 Boyer-Moore 算法，该算法首先查找目标字符串的最后一个字母，并使用查找表来告诉它在找到不匹配的字符时可以在输入中跳过多远。

从为什么 GNU grep 很快。

该算法对被搜索的字符串（模式）进行预处理，但不对被搜索的字符串（文本）进行预处理。 [...] 通常，随着模式长度的增加，算法运行速度更快。

从Boyer–Moore 字符串搜索算法。

结论：使用更长的字符串。

现在，进行一些有趣的基准测试：

# Initialisation
cd $(mktemp -d) && dd if=/dev/urandom of=random bs=1M count=1000
# Version
grep --v` # grep (GNU grep) 2.9
# Benchmark
(for s in 'short' 'this is not so short and we could even consider this as pretty long'; do for t in {1..10}; do time grep "$s" random; done; done ) 2> result

结果：短字符串的平均值是0.952s，长字符串的平均值是0.244s。

注意：：长度不是唯一需要考虑的标准。

答案2

您可以尝试使用 SEARCH 或 SEARCHTERM。还可以尝试更改两个 grep 命令的顺序。无论如何，唯一有用的选项很可能是使用多个 CPU 核心进行一次搜索。请参阅命令parallel。

答案3

我认为指定更具体的搜索词不会使其速度明显加快。

由于需要搜索的文件太多，您需要以某种方式索引数据以加快搜索速度。

我可以建议几种方法：

  • 创建数据库（PostgreSQL 或 MySQL），将数据导入数据库 - 一行一个文件，添加 FTS（全文搜索）索引。创建一些实用程序来查询数据库。

  • 以更细粒度的方式将数据导入数据库，可能一行一行（或者可能不止一个表），创建索引，以便可以使用索引搜索数据。创建一些实用程序来查询数据库。

  • 将文件添加到git存储库，使用 压缩它git gc，然后使用git grep进行搜索。根据我的经验，git grep可以比标准速度快grep10 倍到 100 倍。

答案4

从逻辑上讲，较短的任期将需要较少的 CPU 时间，grep就像

if (filechar[i] == pattern[i]) ...

更少的次数。实际上，我猜想 agrep是 I/O 密集型的，而不是 CPU 密集型的，所以这无关紧要。

相关内容