Grep 怎么跑得这么快？

我真的很惊讶 GREP 在 shell 中的功能，早些时候我在 Java 中使用子字符串方法，但现在我使用 GREP，它在几秒钟内执行，它比我以前写的 Java 代码快得多。(根据我的经验，我可能错了)

也就是说我还没弄明白这是怎么回事？网上也没有太多可用的东西。

有人能帮我吗？

45109

小开

为了补充史蒂夫精彩的回答。

它可能不是广为人知的，但是 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)

另一个常见的误解是(对于 GNUgrep) fgrep比 grep快。fgrep中的 f不代表“ fast”，它代表“ fix”(参见手册页) ，而且因为两者是同一个程序，都使用 grep0，所以在搜索没有 regexp 特殊字符的固定字符串时，它们之间的速度没有差别。我使用 fgrep的唯一原因是当有一个 regexp 特殊字符(如 .、 []或 *)时，我不希望它被解释为这样。即便如此，更便携/更标准的 grep -F形式仍然优于 fgrep。

最佳答案

假设你的问题特别关注 GNU grep，下面是作者 Mike Haertel 的一个注释:

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

GNUgrep 速度很快，因为它对每个指令执行的指令非常少 BYTE 它 看看。

GNU grep 使用著名的 Boyer-Moore字符串搜索算法，它是第一个查看的获取目标字符串的最后一个字母，并使用查找表来告诉它，当它发现一个不匹配的字符。

GNU grep 还展开了 Boyer-Moore 的内部循环，并设置了以一种不需要的方式输入 Boyer-Moore delta 表在每个展开的步骤中进行循环退出测试在这个限制下，GNU grep 的平均指令少于3 x86 对它实际查看的每个输入字节执行(并跳过许多字节)。

GNUgrep 使用原始的 Unix 输入系统调用，并避免复制数据此外，GNU grep 避免了将输入中断到查找换行将使 grep 的速度减慢一倍因为要找到新行，它必须看每一个字节！

因此，GNUgrep 不使用面向行的输入，而是将原始数据读入一个大的缓冲区，搜索缓冲区使用博耶-摩尔，只有当它找到一个匹配它是否去寻找边界换行 (某些命令行选项如 - n 禁用此优化。)

这个答案是从给你获得的信息的子集。

小开

为了补充史蒂夫精彩的回答。

它可能不是广为人知的，但是 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)

另一个常见的误解是(对于 GNUgrep) fgrep比 grep快。fgrep中的 f不代表“ fast”，它代表“ fix”(参见手册页) ，而且因为两者是同一个程序，都使用 grep0，所以在搜索没有 regexp 特殊字符的固定字符串时，它们之间的速度没有差别。我使用 fgrep的唯一原因是当有一个 regexp 特殊字符(如 .、 []或 *)时，我不希望它被解释为这样。即便如此，更便携/更标准的 grep -F形式仍然优于 fgrep。