令我对shell中的GREP功能感到惊讶,早些时候我曾经在java中使用substring方法,但现在我使用GREP并且它在几秒钟内执行,它比我以前编写的java代码快得多. (根据我的经验,我可能错了)
话虽如此,我还是无法弄清楚它是如何发生的？网上也没有太多可用的内容.
谁能帮我这个？
Ste*_*eve 159
假设您的问题GNU grep具体.以下是作者Mike Haertel的说明:
GNU grep是快速的,因为它AVOIDS在每个输入字节中查找.
GNU grep的是快,因为它执行非常少的指令,每一个字节,它 不看.
GNU grep使用众所周知的Boyer-Moore算法,该算法首先查找目标字符串的最后一个字母,并使用查找表告诉它在找到不匹配字符时可以在输入中跳过多远.
GNU grep还展开了Boyer-Moore的内部循环,并以这样的方式设置Boyer-Moore delta表条目,使得它不需要在每个展开的步骤中进行循环退出测试.这样做的结果是,在极限情况下,GNU grep平均为它实际查看的每个输入字节执行的指令少于3 x86(并且它完全跳过许多字节).
GNU grep使用原始的Unix输入系统调用,并避免在读取数据后复制数据.此外,GNU grep AVOIDS打破输入线.寻找新行会使grep减慢几倍,因为要查找换行符,必须查看每个字节!
因此,GNU grep不是使用面向行的输入,而是将原始数据读入大缓冲区,使用Boyer-Moore搜索缓冲区,并且只有当找到匹配时才会查找边界换行符(某些命令行选项如 - n禁用此优化.)
这个答案是从这里获取的信息的一个子集.
ari*_*elf 37
添加史蒂夫的优秀答案.
它可能不被广为人知,但grep的几乎总是更快 grepping的时长模式串比一个短,因为在一个较长的模式,博耶-穆尔可以在更长的步幅快进,实现更好的次线性速度:
例:
# 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从模式字符串构造一个跳转表,并且每当存在不匹配时,它会在将输入中的单个char与跳过表中的char进行比较之前选择可能的最长跳过(从最后一个char到第一个).
另一个常见的误解(对于GNU grep)是fgrep比它更快grep.fin fgrep不代表'fast',它代表'fixed'(参见手册页),由于两者都是同一个程序,并且都使用Boyer-Moore,因此在搜索fixed时,它们之间的速度没有区别没有正则表达式特殊字符的字符串.我使用的唯一原因fgrep是,当有一个正则表达式特殊字符(如.,[]或*)我不希望它被解释为这样的.即使这样的更便携/标准形式grep -F优于fgrep.