我可以期待grep对10 TB文件有多长时间？

Question

我有一个10 TB的文件,里面有来自多本书的单词,我正在尝试grep一些不常见的字符串(没有正则表达式).例如:

grep "cappucino" filename

我想估计这需要多长时间.我不是真的在寻找它是否是正确的方法.当我打电话给grep时,我想了解更多关于幕后真正发生的事情.

如果我错了,请纠正我:

我使用机械硬盘驱动器,读取速度大约为200 MB/s,因此需要大约1000万/ 200 = 50000秒= 14小时才能完成.这是一个准确的估计吗？

Answer 1

最简洁的答案是不.

更长的答案是:这取决于.

更长的答案是:grep的性能取决于很多事情:

• 你正在运行一个固定的字符串搜索(-F,fgrep) - grep使用Boyer-Moore算法,它本身不能找到正则表达式,所以grep做的(或者至少用来做)是它首先找到一个regexp中的固定字符串,尝试使用文本中的BM找到它并进行正则表达式匹配(不确定当前实现是否使用NFA或DFA实现,可能是混合)
• 你的模式有多长 - 对于更长的模式,BM的工作速度更快
• 你会有多少场比赛 - 比赛越少,比赛越快
• 什么是你的CPU和内存 - 硬盘驱动器只会在读取期间帮助你,而不是在计算时间内
• 您使用grep还有哪些其他选择？
• 14小时甚至可能不是你的下限,因为Boyer-Moore足够聪明,可以计算下一次可能发生匹配的偏移量,因此不需要读入整个文件.这确实取决于实现,这只是我的推测.用更长的模式重新运行下面的测试后,我能够下降到0.23秒,我认为我的磁盘不是那么快.但是可能会涉及一些缓存.

例如,我运行的是500MB/s的SSD(至少是制造商所说的),并且用一个非常短的模式(少量字符)来打印200MB的文件给了我:

随着808320命中

real    0m1.734s
user    0m1.334s
sys 0m0.120s

随着0点击:

real    0m0.059s
user    0m0.046s
sys 0m0.016s

@Edit:简而言之,请阅读Boyer-Moore :-)

@ Edit2:好好检查一下grep的工作方式,你应该检查源代码,我在上面描述了一个非常通用的工作流程.