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

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

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

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

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是有优势的
Bash
$ 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

相关推荐

面试怕被问Hashmap,多看看这个文章

o数据结构otable数组长度永远为2的幂次方o那么为什么要把数组长度设计为2的幂次方呢？o扩容o链表树化o红黑树拆分o查找o插入o删除o遍历oequasl和hashcode总结HashMap是面试中...

非常简洁地重试Retry组件，使用起来杠杠的

前言小伙伴是不是经常遇到接口调用异常，超时的场景？尤其网络抖动导致timeout超时的场景，我们一般产品就会叫我们要重试几次。很多小伙伴的实现方式是写个循环调用for（inti=1;i<=3;...

Kafka消息可靠传输之幂等、事务机制

一般而言，消息中间件的消息传输保障有3个层级，分别如下。atmostonce：至多一次。消息可能会丢失，但绝对不会重复传输。atleastonce：最少一次。消息绝不会丢失，但可能会重复传输。...

Seata源码—9.Seata XA模式的事务处理

大纲1.SeataXA分布式事务案例及AT与XA的区别2.SeataXA分布式事务案例的各模块运行流程3.Seata使用SpringBoot自动装配简化复杂配置4.全局事务注解扫描组件的自动装配...

Disruptor—3.核心源码实现分析一

大纲1.Disruptor的生产者源码分析2.Disruptor的消费者源码分析3.Disruptor的WaitStrategy等待策略分析4.Disruptor的高性能原因5.Disruptor高性...

Spring Boot 进阶-详解SpringBoot中条件注解使用

作为使用SpringBoot框架的开发者来讲，如果你连如下的这些注解你都没有听说过，没有用过，那我劝你还是放弃吧？在SpringBoot中我们最常见到的注解应该是条件注解了吧！也就是@Condit...

如何自定义编解码器（如何自定义编解码器的程序）

1.前言上一节我们一节了解了什么是编码解码、序列化和反序列化了，并且留有一道思考题，本节内容主要是深入解析该思考题。思考题：能否把我们的编码和解码封装成独立的Handler呢？那么应该如何去封装...

Disruptor—3.核心源码实现分析二

大纲1.Disruptor的生产者源码分析2.Disruptor的消费者源码分析3.Disruptor的WaitStrategy等待策略分析4.Disruptor的高性能原因5.Disruptor高性...

线程的状态有哪些?它是如何工作的?

线程的状态有哪些？它是如何工作的？线程（Thread）是并发编程的基础，也是程序执行的最小单元，它依托进程而存在。一个进程中可以包含多个线程，多线程可以共享一块内存空间和一组系统资源，因此线程之间的切...

有图解有案例，我终于把Condition的原理讲透彻了

平时加解锁都是直接使用Synchronized关键字来实现的，简单好用，为啥还要引用ReentrantLock呢？为了解决小伙伴的疑问，我们来对两者做个简单的比较吧：相同点两者都是“可重入锁”，即当前...

白话DUBBO原理，通俗易记，再也不怕面试时讲不清楚了

现在的各种面试免不了要问些中间件，尤其是互联网公司，更注重获选人对中间件的掌握情况。在中间件中，有一大类是关于RPC框架的，Dubbo即是阿里出品的一款很著名的RPC中间件，很多互联网公司都在用，面试...

Java 最细的集合类总结（java常用的集合类有哪些）

数据结构作为每一个开发者不可回避的问题，而Java对于不同的数据结构提供了非常成熟的实现，这一个又一个实现既是面试中的难点，也是工作中必不可少的工具，在此，笔者经历漫长的剖析，将其抽丝剥茧的呈现出...

详解Java异常(Exception)处理及常见异常

很多事件并非总是按照人们自己设计意愿顺利发展的，经常出现这样那样的异常情况。例如：你计划周末郊游，计划从家里出发→到达目的→游泳→烧烤→回家。但天有不测风云，当你准备烧烤时候突然天降大雨，只能终止郊...

为什么阿里强制要求不要在foreach循环里进行元素remove和add操作

在阅读《阿里巴巴Java开发手册》时，发现有一条关于在foreach循环里进行元素的remove/add操作的规约，具体内容如下：错误演示我们首先在IDEA中编写一个在foreach循...

SpringBoot条件化配置(@Conditional)全面解析与实战指南

一、条件化配置基础概念1.1什么是条件化配置条件化配置是Spring框架提供的一种基于特定条件来决定是否注册Bean或加载配置的机制。在SpringBoot中，这一机制通过@Conditional...

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