深入脚本编程之一: 优化在大文件中搜索某字串的前 N 个匹配

slimzhao

                                                grep
====
要在一个给定的文件中搜索某个字串, 这是最普通不过的任务:
grep pattern filename
如果匹配的项很多, 而你只想关注前10项呢?
grep pattern filename | head -10
对于filename比较小的情况, 一切OK. 但是, 在真实的工作环境中, 文件大至几百M呢? 你可能(这里留下话头, 有些版本的grep实现会在head 读取10行后退出时也马上退出)会明显感觉到延迟, 你会怀疑你的pattern是否正确, 怀疑你的grep命令有没有被alias偷偷改写, 怀疑程序会不会在等待一个输入, 怀疑telnet是不是断线了, 你会尝试敲几个字符, 看看终端有没有反应, 或者你会按CTRL-Z
如果碰巧你想搜索的pattern 在文件的前面部分出现, 你已经看到了所希望的TOP 10, 但它grep就是挂在那里不退出, 你一定会有一种过河拆桥的冲动想用CTRL-C, CTRL-\, CTRL-Q 灭掉grep
如何在得到想到的东西之后让grep及时停手? 如果只是想知道某文件中是否包含一个pattern, 可以用
grep -l pattern filename
grep会在找到第一个匹配之后退出文件后续部分的读取, 速度很快. 但是, 缺点是明显的, 你无法知道其第一个匹配的行是什么样子.
sed 的q 命令
===========
q代表quit, 这个quit不仅是逻辑上的quit, 实际实现上也不再读取文件的后续部分了.
sed -n '/pattern/{p;q;}' filename
{p;q;} 是一个命令组, 表示如果匹配到/pattern/ 依次执行这个命令组中的命令.
sed的这个命令做到了 1) 显示第一个匹配的行 2) 找到第一个匹配行后不再读取其后的内容, 退出处理
但, 如果想显示前10个而不仅仅是第一个匹配行呢? sed无能为力了, 它没有内置的变量可供记录10这样的状态.
awk 的nextfile
==============
awk 支持变量, 这使得很容易知道"前10个匹配"这样的概念, 关键只在中止对文件的读取这一步了. exit语句. 注意即使有exit语句 END块还是会被执行, 这里用不到END块
awk 'BEGIN{i=0}(i>9){exit;}/pattern/{i++;print;}' filename
三个部分:
a) BEGIN{i=0} 在处理之初给变量i赋0值, 由于awk中的变量会在第一次被使用时获取一个0初值, 所以这一个部分其实可以省略
b) (i>9){ exit; }  如果该变量大于9就退出处理
c) /pattern/{ i++; print; }  如果匹配模式, i自增1, 同时显示该行
测试表明, sed和awk中的方案的确能有效地减少处理时间, 在处理大文件时顾及效率. 这也说明unix下的这些小工具各自具有自己的特殊个性, 具体应用时要关于取材.
管道的问题
=========
现在我捡起前面的话头, grep pattern big_file | head -10 可能是最明显也最快的解决方案. 这一切取决于grep 程序的实现是如何处理 SIGPIPE信号的, 对于管道, 当读进程已经退出而写进程仍尝试写入时, 写进程会收到一个SIGPIPE 信号, 如果grep 在收到该信号时会退出, 它自然不再去读文件后面的内容, 如果它忽略了该信号, 就会出现本文前面提及的情况.
下面是我对管道这一特点的验证:
#!/bin/bash
# test pipe
#trap '' 13
trap 'echo catch SIGPIPE i = $i > result.txt;     exit 2' 13
echo abc
declare -i i=0
while [ $i -lt 200000 ];
do
  echo $i
  let i=i+1
done
echo xyz
此时进行了管道的处理, 脚本退出, 脚本中的while循环是个人为的耗时的操作, 大概耗时10秒. 为什么不用sleep 10是有原因的, 正如CPU的异常只发生在一条机器指令执行完成的边界一样, UNIX的信号只发生在一个系统调用完成的边界上, 而sleep 10是一个系统调用, 所以pipe.sh 有机会处理SIGPIPE 信号是在sleep 10之后. 可能是同样的道理, 用 > /dev/null 同样会延迟pipe.sh 处理信号的机会.
time { ./pipe.sh | head -1; } | tail -1
结果是
abc
real    0m0.062s
user    0m0.039s
sys     0m0.023s
查看 result.txt 文件, 两者都说明pipe.sh 正确地收到了信号并及时退出了.
然后, 只是把上面的脚本中的trap部分修改为默认的忽略该信号:
#!/bin/bash
# test pipe
trap '' 13
#trap 'echo catch SIGPIPE i = $i > result.txt;     exit 2' 13
echo abc
declare -i i=0
while [ $i -lt 200000 ];
do
  echo $i
  let i=i+1
done
echo xyz
再次运行time 查看处理时间:
real    0m10.623s
user    0m9.422s
sys     0m1.201s
大相径庭!
我不知道POSIX的规范有没有对grep的实现做这样的规定, 如果你的系统上grep处理了SIGPIPE并退出, 那么grep pattern big_file | head -10 是最好的方案, 因为grep 的正则表达式引擎被认为是世界上最快的.
启示: 一个好的脚本, 如果希望它的输出很多, 并且它的输出可能会被 | head -1 这样的命令搭配, 应该考虑在管道被中断时优雅地退出.
cat result.txt 的内容也可以看出脚本因SIGPIPE而退出时, while循环正被执行到半途, 其中的i = $i 甚至能告诉你执行到了第几次, 当然, 这个值每次都可能不同.
巧妙构造的脚本可以揭示系统内部的很多原理, 当然, 向外看, 能帮助我们写出更好的命令/脚本.
               
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/8681/showart_266802.html