regex - 使用 regcomp 进行 ^[az]{0,20000}$ 正则表达式编译的糟糕表现

Question

我想知道为什么这种正则表达式的编译占用了我 70% 的 RAM，导致频繁交换和 16 的平均负载：

strcpy(regexStr,"^[a-z]{0,20000}$" );
regcomp( &regex , regexStr , REG_NOSUB | REG_EXTENDED );

执行时间以分钟为单位（必须先终止进程）。（2,000，而不是 20,000）的执行时间^[a-z]{0,2000}$约为 100 毫秒，这对我来说非常重要。

我用它来检查模式并同时检查长度。Ï 发现正则表达式对两者都很方便。难道我做错了什么？

score 10 · Accepted Answer

我建议使用strlen来测量字符串长度，然后使用正则表达式/[^a-z]/来测试是否没有非字母字符。吻。

顺便说一句，不，我看不出有什么充分的理由*说明你为什么会获得这种表现。

*好的理由显然不包括错误或糟糕的设计......

编辑：事实证明，这实际上可能是设计不佳的情况

edit2：由于您正在做的检查非常简单，您实际上可以用纯 C 实现：

int i;
for (i=0; i<20000 && str[i]!=0; i++)
  if (str[i] < 'a' || str[i] > 'z')
    return -1;
return i;

如果返回 -1，则字符串包含范围 az 之外的字符；如果返回 20000，则字符串长度超过 20000 个字符；否则返回字符串长度。（注意：这显然只适用于非宽字符字符串）

score 4 · Accepted Answer

奇怪的是，在引擎盖下，您的正则表达式引擎正在将您的模式转换为类似于^(|[a-z]|[a-z][a-z]|[a-z][a-z][a-z]|..)$您范围的基数的二次方。

score 1 · Accepted Answer

我的猜测是基数范围是杀死你的原因。尝试使用贪婪的非特定基数匹配，例如"^[a-z]*$"，加上最大长度检查。它应该快得多。

score 0 · Accepted Answer

你必须考虑你要求编译器做什么。以一种天真的方式，您可以将正则表达式编译视为构建一个仅接受与正则表达式匹配的字符串的有限状态机。考虑必须跟踪字符串中有多少字符的机器的状态大小，您应该会看到当前正则表达式的问题。

4 回答 4