特别是,我正在考虑 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,19s用户0,00s系统99％cpu 2,192总计.
案例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找到
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.*hros\nove.*ridentify\nmis.*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
