blocks|key|3068256|text|假设你的问题是关于GNU+grep的。这是作者Mike+Haertel的笔记：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3068257|3068258|+GNU+grep速度很快，因为它避免了查看每个输入字节。|blockquote|3068259|3068260|GNU+grep很快，因为它对所查看的每个字节执行很少的指令。|3068261|GNU+grep使用著名的Boyer-Moore算法，该算法首先查找目标字符串的最后一个字母，并使用查找表告诉它，只要找到不匹配的字符，就可以在输入中跳过多远。|3068262|GNU+grep还展开Boyer-Moore的内部循环，并以这样的方式设置Boyer-Moore增量表条目，这样它就不需要在每个展开的步骤都执行循环退出测试。其结果是，在限制中，GNU+grep对于它实际查看的每个输入字节平均执行的x86指令少于3条(并且它完全跳过了许多字节)。|3068263|GNU+grep使用原始Unix输入系统调用，并避免在读取数据后复制数据。此外，GNU+grep避免将输入拆分成行。查找换行符将使grep减慢数倍，因为要找到换行符，它必须查看每个字节！|3068264|因此，GNU+grep不使用面向行的输入，而是将原始数据读入大型缓冲区，使用Boyer-Moore搜索缓冲区，只有在找到匹配项时，它才会继续查找边界换行符(某些命令行选项，如-n，将禁用此优化)。|3068265|3068266|这个答案是取自here的信息的一个子集。|3068267|entityMap|0|LINK|mutability|MUTABLE|url|http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html^0|9|8|0|0|0|0|0|0|0|0|0|0|7|4|0|0^^$0|@$1|2|3|4|5|6|7|15|8|@$9|16|A|17|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|18|8|@]|D|@]|E|$]]|$1|G|3|H|5|I|7|19|8|@]|D|@]|E|$]]|$1|J|3|-4|5|6|7|1A|8|@]|D|@]|E|$]]|$1|K|3|L|5|6|7|1B|8|@]|D|@]|E|$]]|$1|M|3|N|5|6|7|1C|8|@]|D|@]|E|$]]|$1|O|3|P|5|6|7|1D|8|@]|D|@]|E|$]]|$1|Q|3|R|5|6|7|1E|8|@]|D|@]|E|$]]|$1|S|3|T|5|6|7|1F|8|@]|D|@]|E|$]]|$1|U|3|-4|5|6|7|1G|8|@]|D|@]|E|$]]|$1|V|3|W|5|6|7|1H|8|@]|D|@$9|1I|A|1J|1|1K]]|E|$]]|$1|X|3|-4|5|6|7|1L|8|@]|D|@]|E|$]]]|Y|$Z|$5|10|11|12|E|$13|14]]]]

Assuming your question regards <code>GNU grep</code> specifically. Here's a note from the author, Mike Haertel:

<blockquote>
 GNU grep is fast because it AVOIDS LOOKING AT EVERY INPUT BYTE.
 
 GNU grep is fast because it EXECUTES VERY FEW INSTRUCTIONS FOR EACH
 BYTE that it 
 does look at.
 
 GNU grep uses the well-known Boyer-Moore algorithm, which looks first
 for the final letter of the target string, and uses a lookup table to
 tell it how far ahead it can skip in the input whenever it finds a
 non-matching character.
 
 GNU grep also unrolls the inner loop of Boyer-Moore, and sets up the
 Boyer-Moore delta table entries in such a way that it doesn't need to
 do the loop exit test at every unrolled step. The result of this is
 that, in the limit, GNU grep averages fewer than 3 x86 instructions
 executed for each input byte it actually looks at (and it skips many
 bytes entirely).
 
 GNU grep uses raw Unix input system calls and avoids copying data
 after reading it. Moreover, GNU grep AVOIDS BREAKING THE INPUT INTO
 LINES. Looking for newlines would slow grep down by a factor of
 several times, because to find the newlines it would have to look at
 every byte!
 
 So instead of using line-oriented input, GNU grep reads raw data into
 a large buffer, searches the buffer using Boyer-Moore, and only when
 it finds a match does it go and look for the bounding newlines
 (Certain command line options like 
 -n disable this optimization.)
</blockquote>

This answer is a subset of the information taken from <a href="http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html">here</a>.

blocks|key|2854734|text|为史蒂夫的精彩回答再添一笔。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2854735|这可能不是广为人知的，但grep几乎总是更快的时，更长的模式串比短的，因为在更长的模式中，Boyer-Moore可以以更大的步幅向前跳跃，以获得更好的次线性速度：|offset|length|style|BOLD|2854736|示例：|2854737|#+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|code-block|syntax|javascript|2854738|较长的表单快35%25！|2854739|怎么会这样?Boyer-Moore从pattern-string构造一个跳转表，当出现不匹配时，它会在将输入中的单个字符与跳过表中的字符进行比较之前，选择可能的最长跳过(从最后一个字符到第一个字符)。|2854740|这是a+video+explaining+Boyer+Moore+(归功于kommradHomer)|2854741|另一个常见的误解(对于GNU+grep)是认为fgrep比grep更快。fgrep中的f不代表'fast'，它代表'fixed‘(参见手册页)，而且由于这两个程序都是同一个程序，并且都使用Boyer-Moore，所以在搜索没有regexp特殊字符的固定字符串时，它们之间的速度没有差别。我使用fgrep的唯一原因是，当有一个regexp特殊字符(如.、[]或*)时，我不希望它被解释为这样。而且，与fgrep相比，更易移植/更标准的grep+-F形式更受欢迎。|CODE|2854742|entityMap|0|LINK|mutability|MUTABLE|url|https://www.youtube.com/watch?v=4Xyhb72LCX4^0|0|K|3|P|3|23|3|0|0|0|0|0|2|U|0|0|N|5|T|4|10|5|17|1|42|5|4U|1|4W|2|4Z|1|5J|5|60|7|0^^$0|@$1|2|3|4|5|6|7|15|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|16|8|@$D|17|E|18|F|G]|$D|19|E|1A|F|G]|$D|1B|E|1C|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|1D|8|@]|9|@]|A|$]]|$1|J|3|K|5|L|7|1E|8|@]|9|@]|A|$M|N]]|$1|O|3|P|5|6|7|1F|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1G|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|1H|8|@]|9|@$D|1I|E|1J|1|1K]]|A|$]]|$1|U|3|V|5|6|7|1L|8|@$D|1M|E|1N|F|W]|$D|1O|E|1P|F|W]|$D|1Q|E|1R|F|W]|$D|1S|E|1T|F|W]|$D|1U|E|1V|F|W]|$D|1W|E|1X|F|W]|$D|1Y|E|1Z|F|W]|$D|20|E|21|F|W]|$D|22|E|23|F|W]|$D|24|E|25|F|W]]|9|@]|A|$]]|$1|X|3|-4|5|6|7|26|8|@]|9|@]|A|$]]]|Y|$Z|$5|10|11|12|A|$13|14]]]]

To add to Steve's excellent answer.

It may not be widely known but grep is almost always faster when grepping for a longer pattern-string than a short one, because in a longer pattern, Boyer-Moore can skip forward in longer strides to achieve even better sublinear speeds:

Example:

<pre><code># 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
</code></pre>

The longer form is 35% faster!

How come? Boyer-Moore consructs a skip-forward table from the pattern-string, and whenever there's a mismatch, it picks the longest skip possible (from last char to first) before comparing a single char in the input to the char in the skip table.

Here's <a href="https://www.youtube.com/watch?v=4Xyhb72LCX4" rel="noreferrer">a video explaining Boyer Moore</a> (Credit to kommradHomer)

Another common misconception (for GNU grep) is that <code>fgrep</code> is faster than <code>grep</code>. <code>f</code> in <code>fgrep</code> doesn't stand for 'fast', it stands for 'fixed' (see the man page), and since both are the same program, and both use Boyer-Moore, there's no difference in speed between them when searching for fixed-strings without regexp special chars. The only reason I use <code>fgrep</code> is when there's a regexp special char (like <code>.</code>, <code>[]</code>, or <code>*</code>) I don't want it to be interpreted as such. And even then the more portable/standard form of <code>grep -F</code> is preferred over <code>fgrep</code>.

I am really amazed by the functionality of GREP in shell, earlier I used to use substring method in java but now I use GREP for it and it executes in a matter of seconds, it is blazingly faster than java code that I used to write.(according to my experience I might be wrong though)

That being said I have not been able to figure out how it is happening? there is also not much available on the web.

Can anyone help me with this?

How does grep run so fast?

Unix

我真的对shell中GREP的功能感到惊讶，以前我在java中使用substring方法，但现在我使用GREP，它可以在几秒钟内执行，它比我过去编写的java代码快得多。(根据我的经验，我可能是错的。)也就是说，我还不能弄清楚它是如何发生的？在网络上也没有太多可用的东西。有人能帮我吗？

问grep是如何运行得这么快的？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问grep是如何运行得这么快的？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问grep是如何运行得这么快的？
EN