regex - 在匹配字符串 : testing against the regex/regex1|regex2|regex3/, 或一个接一个地测试模式时，哪个性能更好？

Question

假设我有几百万个(可能很长)字符串，并且需要知道每个字符串是否包含这些给定模式中的任何一个:

• regex1
• regex2
• regex3
• ...

在性能方面，是否会更好:

1. 根据“完整”正则表达式测试每个字符串 /regex1|regex2|regex3|.../，或

2. 针对 regex1 测试每个字符串，如果不匹配则针对 regex2 进行测试，依此类推...?

我想知道这一点，而且由于我对正则表达式实现的了解非常有限，所以我不知道它们是否会输出类似的行为。

---

编辑:我刚刚做了一个快速基准测试。没想太多，就脱口而出一些代码。请指出任何可能使输出产生偏差的内容。

这是 JavaScript，我用 Node.js 做了测试。

注意:我尝试运行 500 万个字符串和 500 个正则表达式，但进程耗尽了内存，所以我降低了数字

"use strict";

var strMinSize      = 50;
var strMaxSize      = 500;
var howManyStrings  = 100000;  // hundred thousand
var howManyRegex    = 50;      // fifty

var possible = " ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

function makestr() {
    var text = "";
    var strSize = Math.floor(Math.random() * strMaxSize) + strMinSize;
    for (var i=0; i < strSize; i++) {
      text += possible.charAt(Math.floor(Math.random() * possible.length));
    }
    return text;
}

function makeregex() {
    var regexstr = "";
    var regexSize = Math.floor(Math.random() * 50) + 5;
    for (var i=0; i < regexSize; ++i) {
      regexstr += possible.charAt(Math.floor(Math.random() * possible.length));
    }
    return regexstr;
}

var stringList = [];
for (var i=0; i < howManyStrings; ++i) {
    stringList.push(makestr());
}
var regexList = [];
var fullRegex = ""; // aux to build the disjunction
for (var i=0; i < howManyRegex; ++i) {
    var localRegex = makeregex();
    regexList.push(new RegExp(localRegex));
    fullRegex += '|' + localRegex;
}
fullRegex = new RegExp(fullRegex.substr(1));

// let's do this...

for (var kase=1; kase < 10; ++kase) {
    // Test 1: one disjunction with every regex
    var time1 = 0;
    var time2 = 0;

    var start = new Date().getTime();
    stringList.forEach( function(str) {
      fullRegex.test(str);
    });
    var end = new Date().getTime();
    time1 = end - start;

    // Test 2: one regex at a time
    start = new Date().getTime();
    stringList.forEach( function(str) {
      regexList.every( function(rx) {
        if (rx.test(str)) {
          return false;
        } else {
          return true;
        }
      });
    });
    end = new Date().getTime();
    time2 = end - start;

    console.log(time1 + ";" + time2);
}

运行时间为:

+--------+---------+
| Test 1 | Test 2  |
+--------+---------+
|   813  |  1817   |
|   558  |  1750   |
|   566  |  1756   |
|   558  |  1783   |
|   560  |  1755   |
|   559  |  1736   |
|   551  |  1749   |
|   552  |  1743   |
|   558  |  1746   |
+--------+---------+

所以，正如我所怀疑的那样，第二种选择更糟糕......但为什么这么多？

Answer 1

一个正则表达式总是会更快，因为每个正则表达式测试需要通过输入，即使组合的正则表达式比单个表达式(稍微)复杂，它仍然是一个常数时间计算。

使用“大 O”表示法表达问题:

• 在输入中给定位置的单个正则表达式评估 = O(1)
• 在输入中给定位置的组合正则表达式评估 = 有效 O(1)
• 字符串上的正则表达式匹配 = O(n)(其中 n = 字符串长度)

从这些，我们可以说每个术语的个体传递 = O(n * k)，其中 k 是正则表达式/术语的数量，但一个正则表达式是 O(n)。

这是从您的测试中得出的结论，测试表明单独的正则表达式的速度大约慢 3 倍。

这一切都取决于组合正则表达式与简单正则表达式“差不多一样快”的前提。之所以如此，是因为正则表达式状态引擎非常高效，将执行时间减少到与普通模式的简单交替几乎相同的时间。它会慢一点，但无论术语列表变得多长，都不足以保证对单独的正则表达式进行单独传递。