当前位置：网站首页 > IT知识 > 正文

程序员面试冷知识:为什么grep查找效率这么快

liuian 2025-05-23 18:30 30 浏览

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

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是查找范围长度，

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

https://github.com/BurntSushi/ripgrep

比如在读输入数据上的一个优化。有没有使用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