百度360必应搜狗淘宝本站头条
python判断字典是否为空crontab每周一执行aes和des区别安装指定版本npmadb pull
当前位置：网站首页 > IT知识 > 正文

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

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

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

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

相关推荐

教你把多个视频合并成一个视频的方法

一.情况介绍当你有一个m3u8文件和一个目录，目录中有连续的视频片段，这些片段可以连成一段完整的视频。m3u8文件打开后像这样：m3u8文件,可以理解为播放列表，里面是播放视频片段的顺序。视频片段像这...

零代码编程:用kimichat合并一个文件夹下的多个文件

一个文件夹里面有很多个srt字幕文件，如何借助kimichat来自动批量合并呢？在kimichat对话框中输入提示词：你是一个Python编程专家，完成如下的编程任务：这个文件夹：D:\downloa...

Java APT_java APT 生成代码

JavaAPT（AnnotationProcessingTool）是一种在Java编译阶段处理注解的工具。APT会在编译阶段扫描源代码中的注解，并根据这些注解生成代码、资源文件或其他输出，...

Unit Runtime:一键运行 AI 生成的代码，或许将成为你的复制 + 粘贴神器

在我们构建了UnitMesh架构之后，以及对应的demo之后，便着手于实现UnitMesh架构。于是，我们就继续开始UnitRuntime，以用于直接运行AI生成的代码。PS：...

挣脱臃肿的枷锁:为什么说Vert.x是Java开发者手中的一柄利剑?

如果你是一名Java开发者，那么你的职业生涯几乎无法避开Spring。它如同一位德高望重的老国王，统治着企业级应用开发的大片疆土。SpringBoot的约定大于配置、SpringCloud的微服务...

五年后，谷歌还在全力以赴发展 Kotlin

作者|FredericLardinois译者|Sambodhi策划|Tina自2017年谷歌I/O全球开发者大会上，谷歌首次宣布将Kotlin（JetBrains开发的Ja...

kotlin和java开发哪个好，优缺点对比

Kotlin和Java都是常见的编程语言，它们有各自的优缺点。Kotlin的优点：简洁：Kotlin程序相对于Java程序更简洁，可以减少代码量。安全：Kotlin在类型系统和空值安全...

移动端架构模式全景解析:从MVC到MVVM，如何选择最佳设计方案?

掌握不同架构模式的精髓，是构建可维护、可测试且高效移动应用的关键。在移动应用开发中，选择合适的软件架构模式对项目的可维护性、可测试性和团队协作效率至关重要。随着应用复杂度的增加，一个良好的架构能够帮助...

颜值非常高的XShell替代工具Termora，不一样的使用体验!

Termora是一款面向开发者和运维人员的跨平台SSH终端与文件管理工具，支持Windows、macOS及Linux系统，通过一体化界面简化远程服务器管理流程。其核心定位是解决多平台环境下远程连接、文...

预处理的底层原理和预处理编译运行异常的解决方案

若文章对您有帮助，欢迎关注程序员小迷。助您在编程路上越走越好！[Mac-10.7.1LionIntel-based]Q：预处理到底干了什么事情？A：预处理，顾名思义，预先做的处理。源代码中...

为“架构”再建个模:如何用代码描述软件架构?

在架构治理平台ArchGuard中，为了实现对架构的治理，我们需要代码+模型描述所要处理的内容和数据。所以，在ArchGuard中，我们有了代码的模型、依赖的模型、变更的模型等，剩下的两个...

深度解析:Google Gemma 3n —— 移动优先的轻量多模态大模型

2025年6月，Google正式发布了Gemma3n，这是一款能够在2GB内存环境下运行的轻量级多模态大模型。它延续了Gemma家族的开源基因，同时在架构设计上大幅优化，目标是让...

比分网开发技术栈与功能详解_比分网有哪些

一、核心功能模块一个基本的比分网通常包含以下模块：首页/总览实时比分看板：滚动展示所有正在进行的比赛，包含比分、比赛时间、红黄牌等关键信息。热门赛事/焦点战：突出显示重要的、关注度高的比赛。赛事导航...

设计模式之-生成器_一键生成设计

一、【概念定义】——“分步构建复杂对象，隐藏创建细节”生成器模式（BuilderPattern）：一种“分步构建型”创建型设计模式，它将一个复杂对象的构建与其表示分离，使得同样的构建过程可以创建...

构建第一个 Kotlin Android 应用_kotlin简介

第一步：安装AndroidStudio（推荐IDE）AndroidStudio是官方推荐的Android开发集成开发环境（IDE），内置对Kotlin的完整支持。1.下载And...

一周热门
最近发表
标签列表