正则表达式 – grep -f的性能问题
|
我正在使用grep在单个文件中搜索几个正则表达式.
特别是,我正在考虑 a 100 MB file with English subtitles并运行存储在文件patterns.txt中的以下正则表达式： Cas.*eharden acr.*otic syn.*thesizing sub.*abbot iss.*acharite bot.*onne dis.*similatory ove.*rmantel isa.*tin ado.*nijah sol.*ution zei.*st fam.*ousness inq.*uisitress aor.*tography via.*duct ama.*sa der.*ive pie.*tas kit.*chenette 在这样做时,我观察到grep所需的时间不会与正则表达式的数量呈线性增长.实际上,它似乎成倍增长. 实验 系统：Intel(R)Core(TM)i5-5200U CPU @ 2.20GHz; 4个核心; 8 GB RAM 案例1：20 regexps 命令grep -c -f patterns.txt subtitles.txt计算2214次出现并占用 案例2:30 regexps 如果我将以下表达式添加到patterns.txt ort.*hros ove.*ridentify mis.*tiest pay.*ne int.*erchasing jej.*uneness sta.*lactiform und.*ertrain cob.*bles Sub.*category 命令grep -c -f patterns.txt subtitles.txt计算2894次出现并占用71,35s用户0,06s系统99％cpu 1：11,42总计. 案例3：35个正则表达式 再添加五个表达式： dis.*embosom imp.*ortunateness ema.*thion rho.*mb haz.*elwood 命令grep -c -f patterns.txt subtitles.txt计算2904次出现并占用211,18s用户0,22s系统99％cpu 3：31,58总计 为什么grep -f表现出这种行为？它在内部做什么？ 我一直在使用的整套正则表达式可以在here找到
通过阅读grep源代码,您的文件中的正则表达式似乎不会一次执行一次.相反,它们一下子被读成一个大的正则表达式：
case 'f':
fp = STREQ (optarg,"-") ? stdin : fopen (optarg,O_TEXT ? "rt" : "r");
if (!fp)
error (EXIT_TROUBLE,errno,"%s",optarg);
for (keyalloc = 1; keyalloc <= keycc + 1; keyalloc *= 2)
;
keys = xrealloc (keys,keyalloc);
oldcc = keycc;
while ((cc = fread (keys + keycc,1,keyalloc - 1 - keycc,fp)) != 0)
{
keycc += cc;
if (keycc == keyalloc - 1)
keys = x2nrealloc (keys,&keyalloc,sizeof *keys);
}
这是确认看到你的命令运行grep strace： open("testreg",O_RDONLY) = 3
fstat(3,{st_mode=S_IFREG|0664,st_size=124,...}) = 0
mmap(NULL,4096,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0) = 0x7fd8912fe000
read(3,"ort.*hrosnove.*ridentifynmis.*ti"...,4096) = 124
回溯正则表达式实现(允许反向引用),不在O(n)时间运行,而是在O(2 ^ m)运行,这可能导致catastrophic运行时. 你假设grep只是依次遍历每个正则表达式,将每个正则表达式编译成DFA然后执行它是完全合理的.然而,似乎grep作者假设通过一次运行你的正则表达式,他们可能在某些情况下更有效地这样做.结果是,通过将正则表达式添加到文件中,您将进入O(2 ^ m)运行时,从而导致运行时呈指数级增长. 事实证明,简单地循环遍历执行它们的每个正则表达式可能会更有效,从而迫使grep线性运行.在我的笔记本电脑上,运行grep版本2.20,我只使用你提供的文件中的最后29个正则表达式得到以下结果： [Downloads]$wc -l patterns.txt 29 patterns.txt [Downloads]$time grep -c -f ~/Downloads/patterns.txt /usr/share/dict/linux.words 117 real 0m3.092s user 0m3.027s sys 0m0.047s [csd@alcazar Downloads]$time for regex in `cat ~/Downloads/patterns.txt`; do grep -c $regex /usr/share/dict/linux.words > /dev/null; done real 0m0.474s user 0m0.312s sys 0m0.158s （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |