grep -f 的性能问题

我正在使用 grep 在单个文件中搜索多个正则表达式。 特别是，我正在考虑100 MB 文件，带英文字幕 https://drive.google.com/open?id=0B3oOQ14-tellNzhlU0tKT2xFSW8并运行存储在文件中的以下正则表达式模式.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 所需的时间并不随着正则表达式的数量线性增长。的确，它似乎呈指数级增长.

实验

System:英特尔(R) 酷睿(TM) i5-5200U CPU @ 2.20GHz； 4 核； 8GB 内存

案例 1：20 个正则表达式

Command grep -c -f patterns.txt subtitles.txt统计 2214 次出现并采取
2,19s 用户 0,00s 系统 99% cpu 总计 2,192。

案例 2：30 个正则表达式

如果我添加以下表达式模式.txt

ort.*hros
ove.*ridentify
mis.*tiest
pay.*ne
int.*erchasing
jej.*uneness
sta.*lactiform
und.*ertrain
cob.*bles
Sub.*category

Command grep -c -f patterns.txt subtitles.txt统计了 2894 次出现，总共需要 71,35 秒用户 0,06 秒系统 99% cpu 1:11,42。

案例 3：35 个正则表达式

添加另外五个表达式：

dis.*embosom
imp.*ortunateness
ema.*thion
rho.*mb
haz.*elwood

Command grep -c -f patterns.txt subtitles.txt计数 2904 次出现，需要 211,18 秒用户 0,22 秒系统 99% cpu 3:31,58 总计

为什么 grep -f 表现出这样的行为？它在内部做什么？

我一直在使用的整套正则表达式都可以找到here https://drive.google.com/open?id=0B3oOQ14-tellOG5WcXBlRmFWY00

从阅读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);
    }

这是通过观看证实的stracegrep 在您的命令上运行：

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) 时间内运行，这可能会导致灾难性的 https://stackoverflow.com/questions/5892115/whats-the-time-complexity-of-average-regex-algorithms运行时。

你的假设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