仓酷云

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 692|回复: 15
打印 上一主题 下一主题

[其他Linux] Linux制作之为何GNU grep云云之快?仓酷云

[复制链接]
金色的骷髅 该用户已被删除
跳转到指定楼层
楼主
发表于 2015-1-18 11:22:51 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
对于linux命令,一定要学会用man和info去查他们的解释;
编注:这是GNUgrep的原作者MikeHaertel在FreeBSD邮件列表中对“GNUgrep为何比BSDgrep要快”所做的回覆,上面是邮件注释内容:
Gabor您好,
我是GNUgrep的原作者,同时也是一位FreeBSD用户,不外我一向利用的是-stable版本(也就是更老的版本),而没怎样存眷-current版本。
可是,当我偶然间翻阅-current版的邮件列表时,偶尔发明了一些关于BSDgrep与GNUgrep功能的会商,你大概也注重到了那些会商。
不论怎样说,仅供参考吧,上面是一些复杂的总结,关于为何GNUgrep云云之快。也许你能自创个中的一些头脑使用到BSDgrep中往。
#技能1:GNUgrep之以是快是由于它并不会往反省输出中的每个字节
#技能2:GNUgrep之以是快是由于它对那些切实其实必要反省的每一个字节都实行十分少的指令(操纵)
GNUgrep利用了十分出名的Boyer-Moore算法(译者注:BM算法,是一种十分高效的字符串搜刮算法,一样平常情形下,比KMP算法快3-5倍,详细可检察这篇解说十分具体的文章:grep之字符串搜刮算法Boyer-Moore由浅进深(比KMP快3-5倍)),该算法起首从方针字符串的最初一个字符入手下手查找,而且利用一个查找表,它能够在发明一个不婚配字符以后,盘算出能够跳过量少个输出字符并持续查找。
GNUgrep还睁开了Boyer-Moore算法的外部轮回,并创建了一个Boyer-Moore的delta表,如许它就不必要在每个睁开的步骤举行轮回加入判别了。如许的了局就是,在极限情形下(inthelimit),GNUgrep在必要反省的每个输出字节上所实行的x86指令不会凌驾3条(而且还跳过了很多字节)。
你能够看看由AndrewHume和DanielSunday1991年11月在“SoftwarePractice&Experience”上宣布的论文“FastStringSearching”,该文很好的会商了Boyer-Moore算法的完成技能,该文有收费的PDF在线版(译者注:点这里检察或下载)。
一旦有了疾速搜刮,这时候你会发明也必要一样疾速的输出。
GNUgrep利用了原生Unix输出体系挪用并制止了在读取后对数据举行拷贝。
并且,GNUgrep还制止了对输出举行分行,查找换行符会让grep减慢好几倍,由于要找换行符你就必需检察每一个字节!
以是GNUgrep没有利用基于行的输出,而是将原数据读进到一个年夜的缓冲区buffer,用Boyer-Moore算法对这个缓冲区举行搜刮,只要在发明一个婚配以后才会往查找比来的换行符(某些命令参数,好比-n会克制这类优化)。
最初,当我还在保护GNUgrep的时分(15+年前……),GNUgrep也实验做一些十分坚苦的事变使内核也能制止处置输出的每一个字节,好比利用mmap()而不是read()来举行文件输出。事先,用read()会使年夜部分Unix版本形成一些分外的拷贝。由于我已不再GNUgrep了,以是仿佛mmap已不再默许利用了,可是你仍旧能够经由过程参数–mmap来启用它,最少在文件体系的buffer已缓存了你的数据的情形下,mmap仍旧要快一些:
1
2
3
4
5
6
7
8
$timesh-cfind.-typef-print|xargsgrep-l123456789abcdef
real0m1.530s
user0m0.230s
sys0m1.357s
$timesh-cfind.-typef-print|xargsgrep--mmap-l123456789abcdef
real0m1.201s
user0m0.330s
sys0m0.929s

[这里利用的输出是一个648M的MH邮件文件夹,包括约莫41000条信息]
以是即便在明天,利用–mmap仍旧能够提速20%以上。
总结:
-利用Boyer-Moore算法(而且睁开它的内层轮回)。

不同版本的Linux命令数量不一样,这里笔者把它们中比较重要的和使用频率最多的命令。
金色的骷髅 该用户已被删除
沙发
 楼主| 发表于 2015-1-20 22:32:25 | 只看该作者
首先Linux是开源的,这也是最主要的原因,想学windows,Unix,对不起我们没源代码。也正是因为这样,Linux才能够像滚雪球一样越滚越大,发展到现在这种规模。
柔情似水 该用户已被删除
板凳
发表于 2015-1-21 14:11:06 | 只看该作者
熟悉操作是日常学习Linux中的三大法宝。以下是作者学习Linux的一些个人经验,供参考:
兰色精灵 该用户已被删除
地板
发表于 2015-1-30 19:45:41 | 只看该作者
其中不乏很多IT精英的心血。我们学透以后更可以做成自己的OS!?
第二个灵魂 该用户已被删除
5#
发表于 2015-2-5 15:25:37 | 只看该作者
任何人都可以根据自己的喜好来定制适合自己的操作系统,Linux?是抢占式多任务多用户操作系统.
若天明 该用户已被删除
6#
发表于 2015-2-12 12:45:13 | 只看该作者
通过一条缓慢的调制解调器线路,它也能操纵几千公里以外的远程系统。
再见西城 该用户已被删除
7#
发表于 2015-2-19 19:42:40 | 只看该作者
如果你有庞大而复杂的测试条件,尽量把它剪裁得越小越好。可能你会遇到这种情况,对于一个问题会出现不同内容回答,这时你需要通过实践来验证。
admin 该用户已被删除
8#
发表于 2015-2-26 11:53:40 | 只看该作者
请问谁有Linux的学习心得的吗?简单的说说?
愤怒的大鸟 该用户已被删除
9#
发表于 2015-2-27 10:51:00 | 只看该作者
眼看这个学期的Linux课程已经告一段落了,我觉得有必要写一遍心得体会来总结一下这学期对着门课程的学习。
谁可相欹 该用户已被删除
10#
发表于 2015-2-27 15:01:30 | 只看该作者
随着IT从业人员越来越多,理论上会有更多的人使用Linux,可以肯定,Linux在以后这多时间不会消失。
飘灵儿 该用户已被删除
11#
发表于 2015-3-6 14:56:46 | 只看该作者
学习Linux,应该怎样学,主要学些什么,一位Linux热心学习者,一段学习Linux的风云经验,历时十二个小时的思考总结,近十位网络Linux学习者权威肯定,为您学习Linux指明方向。
透明 该用户已被删除
12#
发表于 2015-3-7 03:01:07 | 只看该作者
工具书对于学习者而言是相当重要的。一本错误观念的工具书却会让新手整个误入歧途。目前国内关于Linux的书籍有很多不过精品的不多。
13#
发表于 2015-3-8 00:15:51 | 只看该作者
当然你不需搭建所有服务,可以慢慢来。自己多动手,不要非等着别人帮你解决问题。
精灵巫婆 该用户已被删除
14#
发表于 2015-3-10 12:30:26 | 只看该作者
再次,Linux是用C语言编写的,我们有学习C语言的基础,读程序和编写代码方面存在的困难小一点,也是我们能较快掌握的原因之一。?
因胸联盟 该用户已被删除
15#
发表于 2015-3-17 06:22:42 | 只看该作者
安装一个新的软件时先看README,再看INSTALL然后看FAQ,最后才动手安装,这样遇到问题就知道为什么。如果Linux说明文档不看,结果出了问题再去论坛来找答案反而浪费时间。
爱飞 该用户已被删除
16#
发表于 2015-3-23 23:31:19 | 只看该作者
然我们对Linux的学习首先是通过对它的产生,发展,到今天仍然在不断完善开始的。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|仓酷云 鄂ICP备14007578号-2

GMT+8, 2024-12-23 18:05

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表