124

我对 GREP 在 shell 中的功能感到非常惊讶，之前我曾经在 java 中使用 substring 方法，但现在我使用 GREP 并且它在几秒钟内执行，它比我以前编写的 java 代码快得多。 （根据我的经验，我可能是错的）

话虽如此，我一直无法弄清楚它是如何发生的？网上也没有太多可用的。

谁能帮我这个？

4

2 回答 2

188

假设您的问题GNU grep具体涉及。这是作者 Mike Haertel 的注释：

GNU grep 速度很快，因为它避免查看每个输入字节。

GNU grep 速度很快，因为它对每个字节执行非常少的 指令。

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

GNU grep 还展开 Boyer-Moore 的内部循环，并设置 Boyer-Moore 增量表条目，使其不需要在每个展开的步骤中进行循环退出测试。这样做的结果是，在极限情况下，GNU grep 为它实际查看的每个输入字节平均执行少于 3 个 x86 指令（并且它完全跳过了许多字节）。

GNU grep 使用原始的 Unix 输入系统调用并避免在读取数据后复制数据。此外，GNU grep 避免将输入分成几行。寻找换行符会使 grep 减慢几倍，因为要找到换行符，它必须查看每个字节！

因此，GNU grep 不是使用面向行的输入，而是将原始数据读入一个大缓冲区，使用 Boyer-Moore 搜索缓冲区，只有当它找到匹配项时，它才会去寻找边界换行符（某些命令行选项，如 - n 禁用此优化。）

这个答案是从这里获取的信息的一个子集。

于 2012-09-27T21:56:54.700 回答
47

补充史蒂夫的出色答案。

它可能并不广为人知，但 grep 在 grep搜索较长的模式字符串时几乎总是比短模式字符串更快，因为在较长的模式中，Boyer-Moore可以以更长的步幅向前跳跃以实现更好的亚线性速度：

例子：

# after running these twice to ensure apples-to-apples comparison
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log
28
0.168u 0.068s 0:00.26

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log
28
0.100u 0.056s 0:00.17

较长的形式快 35%！

怎么来的？Boyer-Moore从模式字符串构造一个向前跳过的表，每当出现不匹配时，它会在将输入中的单个字符与跳过表中的字符进行比较之前选择可能的最长跳过（从最后一个字符到第一个字符）。

这是一个解释 Boyer Moore 的视频 （归功于 kommradHomer）

另一个常见的误解（对于 GNU grep）是fgrep比grep. finfgrep不代表“快速”，它代表“固定”（参见手册页），并且由于两者都是同一个程序，并且都使用Boyer-Moore，因此在搜索固定时它们之间的速度没有差异-没有正则表达式特殊字符的字符串。我使用的唯一原因fgrep是当有一个正则表达式特殊字符（如.、[]或*）时，我不希望它被解释为这样。即便如此，更便携/标准的形式grep -F还是优于fgrep.

于 2014-09-10T05:36:27.293 回答