更多互联网新鲜资讯、工作奇淫技巧关注原创【飞鱼在浪屿】（日更新）

GNU的grep程序作者认为是有两个因素：fast search和fast input。

https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

快速查找/fast search

grep是基于Boyer-Moore算法，该算法首先查找目标字符串的最后一个字母，并使用查找map表，当找到不匹配的字符，该map表告诉算法可以跳过多长的位置。

BM算法的wiki链接：

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm

BM还在于能够判断出一些不必要的内循环，加快运行速度。

在随机文本查找上，BM的平均时间复杂度是o(n)，最差情况是o(m*n)。其中m是搜索字符串长度，n是查找范围长度，

快速输入/fast input

• GNU grep使用原生的输入系统调用，而不用read，避免内存拷贝。
• grep内部没有行，而是用一块大缓冲区包括放置换行符，因为新行会变慢效率。
• 在查找中使用连续内存空间。
• 在输出写出有没有使用原生系统调用不是很重要，因为输出缓存空间相比输入往往小很多

进阶版的ripgrep（俗称rg）

那么grep做到了极致吗，显然不是。ripgrep（俗称rg）是grep的演进版。在一些场景比grep更快更好用。github链接在这：

https://github.com/BurntSushi/ripgrep

比如在读输入数据上的一个优化。有没有使用mmap来存放输入字符串，这里有一个探讨。

• 如果是在一堆连续内存空间的小文件查找，mmap没有优势。mmap 会导致连加载到内存的小文件连续缺页中断。
• 而如果是大文件查找，mmap是有优势的

$ rg --mmap zqzqzqzq big-file  #比较快
 $ rg --no-mmap zqzqzqzq big-file #比较慢

glibc 的实现使用一种双向字符串匹配算法
/Two-way_string-matching_algorithm。它是前进的Knuth-Morris-Pratt算法和后向运行的Boyer-Moore字符串搜索算法的组合。

https://en.wikipedia.org/wiki/Two-way_string-matching_algorithm