grep簡介
在Linux里面园骆，如果按照使用頻率給命令排個序分俯，那么grep絕對榜上有名蹈垢。
grep的全稱是Global Expression Print畜伐，用于正則表達式匹配文本丈咐，并把匹配到的行打印出來瑞眼。
命令的基本形式是：
grep [option] pattern file
此處的file并不一定是特指某個文件，準確來說是指棵逊，任何的輸入流伤疙。所以時常grep會合別的命令結(jié)合在一起來使用，例如查找Java進程:
ps -ef | grep java
在我機器上的輸出是：
501 25223 16384 0 7:05下午 ttys002 0:00.00 grep --color=auto --exclude-dir=.bzr --exclude-dir=CVS --exclude-dir=.git --exclude-dir=.hg --exclude-dir=.svn java
grep作為一個基本工具辆影，其性能是極高的:
現(xiàn)在我們就要思考一下掩浙，為什么grep會那么快呢？
grep那么快秸歧，就兩個原因：
- 快的算法
- 快的輸入厨姚。
我們先討論快的算法。
字符串檢索
我們先來了解一下字符串搜索键菱，即如何在一個字符串中找到我們所需要的字符串谬墙，或者說子串。這些字符串一般都是符合某個規(guī)則经备，通常而言是使用正則表達式來進行描述拭抬。
在字符串檢索里面，鼎鼎有名的就是Boyer-Moore字符串檢索算法了額侵蒙。這個算法阮一峰有過很精彩很簡潔的介紹造虎，地址是:
http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
也可以閱讀Moor教授對算法的介紹：
http://www.cs.utexas.edu/~moore/best-ideas/string-searching/fstrpos-example.html
我這里總結(jié)一下阮一峰文章的精髓：
這個算法的核心是“壞字符規(guī)則”和“好后綴規(guī)則”。
壞字符規(guī)則
壞字符是指纷闺，無法匹配上模式的字符算凿，例如：
S和E無法匹配上份蝴，也就是一個壞字符。
而所謂壞字符規(guī)則就是：
后移位數(shù) = 壞字符的位置 - 搜索詞中的上一次出現(xiàn)位置
所以下一次的匹配應(yīng)該變成了：
氓轰；
在上圖的情況下婚夫，可以進一步將字符串后移，將P對齊：
好后綴規(guī)則
這種所有尾部都匹配的字符串就叫做好后綴署鸡。當(dāng)好后綴遇到第一個不匹配的字符的時候案糙，在上圖中也就是I和A，那么移動位數(shù)是:
后移位數(shù) = 好后綴的位置 - 搜索詞中的上一次出現(xiàn)位置
這就是Boyer-Moor算法的核心靴庆。
我們可以簡單分析一下Boyer-Moor算法的效率时捌。它是O(n)的，但是很多情況下炉抒，它并不需要遍歷文本里面的每一個字符匣椰。
實現(xiàn)技巧
主要是使用了兩個技巧：
- 循環(huán)展開。GNU grep將Boyer-Moor算法的內(nèi)層循環(huán)展開了端礼；
- 建立了一個jump table禽笑，也叫做delta table。通過該表可以避免進行循環(huán)退出判斷了蛤奥；
快的輸入
grep在這方面所進行的優(yōu)化佳镜，即使用系統(tǒng)調(diào)用，以避免數(shù)據(jù)拷貝的開銷凡桥。
這是一種常見的優(yōu)化手段蟀伸，比如在Java NIO里面也使用到了類似的技術(shù)手段以避免數(shù)據(jù)從內(nèi)核態(tài)拷貝到用戶態(tài)，再由用戶態(tài)拷貝到內(nèi)核態(tài)
第二個優(yōu)化是避免了對輸入進行分行缅刽。grep直接將文本放在Buffer之中進行處理啊掏，在找到了匹配的字符串之后，再去查找里面有沒有換行符衰猛。因為查找換行符是一個可怕的操作迟蜜，這意味著需要逐個字符查找。
后記
原文是https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html#
郵件里面還提到一個東西啡省，即Fast String Search娜睛，這是一個關(guān)于Boyer-Moor算法實現(xiàn)優(yōu)化的論文。我表示這篇論文沒怎么讀懂卦睹，我就不誤人子弟了畦戒。
下載鏈接是:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.9460&rep=rep1&type=pdf
可以翻墻的同志可以看這個視頻，對Boyer-Moor算法的講解還是很好的：
https://www.youtube.com/watch?v=4Xyhb72LCX4
