关山难越,谁悲失路之人;萍水相逢,尽是他乡之客。
百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 编程教程 > 技术文章 > 正文

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

guanshanw 2023-08-24 00:16 119 浏览 0 评论

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


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


相关推荐

七条简单命令让您玩转Git
七条简单命令让您玩转Git

凭借着出色的协作能力、快速部署效果与代码构建辅助作用,Git已经得到越来越多企业用户的青睐。除了用于开发商业及消费级应用之外,众多科学及政府机构也开始尝试使用这...

2023-10-07 12:14 guanshanw

基本完整的关于Git分支branch的操作
基本完整的关于Git分支branch的操作

Git使用背景项目中要用到dev或者其他分支开发完代码,需要将该分支合并到master的需求操作步骤下面以dev名称为lex为分支名为例来操作一遍客户端操作:...

2023-10-07 12:14 guanshanw

Git 进阶(合并与变基)
Git 进阶(合并与变基)

在Git中整合来自不同分支的修改主要有两种方法:合并(merge)以及变基(rebase)合并(merge)merge流程图merge的原理是找到这两个分...

2023-10-07 12:13 guanshanw

Git学习笔记 003 Git进阶功能 part5 合并(第一部分)

合并(merge)是很常用的操作。尤其是一个庞大的很多人参与开发的企业级应用。一般会设定一个主分支,和多个副分支。在副分支开发完成后,合并到主分支中。始终保持主分支是一个完整的,稳定的最新状态的分支。...

非标题党,三张图帮你理解git merge和git rebase的区别
非标题党,三张图帮你理解git merge和git rebase的区别

初始场景:基于正常的开发分支修改几个小bug,然后在合并到开发分支上。gitmergegitcheckoutfeaturegitmergeho...

2023-10-07 12:13 guanshanw

git 初次使用(01)
git 初次使用(01)

先从github上克隆代码下来:使用vscode克隆代码如下图,填写上github仓库地址:vscode有时候克隆代码速度比较慢,可以用命令行方式克隆gitc...

2023-10-07 12:12 guanshanw

Git 远程操作

4.Git远程操作命令说明gitremote远程版本库操作gitfetch从远程获取版本库gitpull下载远程代码并合并gitpush上传远程代码并合并4.1远程版本库操作gitre...

Git常用命令-总结
Git常用命令-总结

创建git用户$gitconfig--globaluser.name"YourName"$gitconfig--globaluser.em...

2023-10-07 12:12 guanshanw

git中删除从别人clone下来项目的git信息,并修改为自己的分支

如果你从别人的Git存储库中克隆了一个项目,并想要删除与该存储库相关的Git信息,并将其修改为你自己的分支,则可以执行以下步骤:使用gitclone命令克隆存储库:gitclone<u...

git系列-回滚和放弃本地修改

回滚历史提交就是reset的功能。这种情况是已经提交远程仓库,需要回滚到之前的提交。gitreset--hardcommitId//注:强制提交后,当前版本后面的提交版本将会删掉!gi...

GIT使用小技巧大全
GIT使用小技巧大全

在大型软件工程的开发过程中,版本控制是无法绕过去的;目前来说,最火的版本控制软件就是GIT了。早两年SVN比较火,不过被大神linus喷了几次后,就日落西山了,...

2023-10-07 12:11 guanshanw

git相关命令-上
git相关命令-上

这些命令都是看了文档后,个人觉得比较有用的一些,展示给大家。回到远程仓库的状态抛弃本地所有的修改,回到远程仓库的状态。gitfetch--all&...

2023-10-07 12:10 guanshanw

Git命令行接口:掌握Git的必备技能
Git命令行接口:掌握Git的必备技能

Git是一款强大的分布式版本控制工具,它支持命令行界面操作。熟练掌握Git命令行接口,是开发者使用Git的必备技能之一。在这篇文章中,我们将介绍Git命令行接口...

2023-10-07 12:10 guanshanw

Git命令详解
Git命令详解

相信各位小伙伴们应该都对git有一些了解,毕竟作为代码管理的神器,就算不是IT行业的小伙伴肯定也或多或少的听说过一些。今天就来和小伙伴们分享一下自己总结的常用命...

2023-10-07 12:10 guanshanw

工作7年收集到的git命令
工作7年收集到的git命令

概念git中的术语解释:仓库也叫版本库(repository)stage:暂存区,add后会存到暂存区,commit后提交到版本库git安装linux...

2023-10-07 12:10 guanshanw

取消回复欢迎 发表评论: