代码之家 › 专栏 › 技术社区 › paxdiablo

哪个是更有效的regex?

performance regex

paxdiablo · 技术社区 · 14 年前

我最近收到一些求职者的测试结果,其中一个人声称他们给出的解决方案更有效率(我不想说是哪一个,因为我不想影响答案)。不用说,我对此表示怀疑,但我对重新编译程序的内部工作机制了解不够,无法进行明智的评论。

问题是:给出一个正则表达式来识别0到99之间的数字。

答案是:

[0-9]{1,2}
[0-9]?[0-9]
[0-9]|([0-9][0-9])

我会感兴趣的是,为什么这些都更快(或更好的任何其他方式)。提供证据而不是猜测的加分,但如果你说得足够有说服力,我还是会接受猜测的:-)

7 回复 | 直到 14 年前

Mark Byers 14 年前

表达 [0-9]{1,2} 应该是我能想象到的最快的,尽管这取决于具体的引擎。

我的理由是:

[0-9]{1,2}-这正好描述了您想要匹配的内容。
[0-9]?[0-9]-如果第一个匹配失败,这可能会导致回溯。
[0-9]|([0-9][0-9])—如果第一个字符失败,则需要对其进行两次检查,此处的括号是不必要的,并且会导致不必要的捕获。

下面是在.NET中测试时每秒获得的迭代次数(不带RegexOptions.Compiled):

Regex                      100% valid input   50% valid input  100% invalid input
"^[0-9]{1,2}$"             749086             800313           870748
"^[0-9]?[0-9]$"            731951             725984           740152
"^(?:[0-9]|([0-9][0-9]))$" 564654             687248           870378

使用RegexOptions。编译:

Regex                      100% valid input   50% valid input  100% invalid input
"^[0-9]{1,2}$"             1486212            1592535          1831843
"^[0-9]?[0-9]$"            1301557            1448812          1559193
"^(?:[0-9]|([0-9][0-9]))$" 1131179            1303213          1394146

作为图表:

alt text

注意:我修改了每个正则表达式以要求精确匹配,而不是执行搜索。

John Kugelman Michael Hodel 14 年前

至少 理论上 ,像这样相同的正则表达式将产生相同的自动机。基于DFA的匹配器将一次匹配一个字符,并在其状态中编码不同的可能分支(而不是一次获取一个分支,然后在失败时回溯),因此每个分支的性能将相同。

所有三个正则表达式都将与此DFA匹配:

+---+  0-9  +---+  0-9  +---+  *  .---.
| A |  -->  | B |  -->  | C | --> (ERR)
+---+       +---+       +---+     '---'
  |          / \          |
  | *     * /   \ $       | $ 
  V        /     \        V
.---.     /       \     .---.
(ERR) <--'         '--> (ACC)
'---'                   '---'

A州 :开始状态。如果看到一个数字,则转到B,否则转到错误状态。
B国 :到目前为止匹配了一个数字。接受下线($)。一个数字移到C。其他的都是错误。
C国 :两位数匹配。EOL被接受,任何其他都是错误的。

这是我的语言理论答案。我无法与现实世界的regex引擎实现对话。我忽略了括号的捕获语义,因为我猜这不是问题的重点。自动机也不处理其他“非理论”的结构,如贪婪,展望等,至少在他们的教科书演示。

tchrist 14 年前

如果不知道regex引擎,我们甚至无法决定这些是否正确。

例如,POSIX ERE是最长的最左边,而不是最长的最左边,因此它将在一系列备选方案中选择最长的,并因此选择一个字符串匹配 "ab" 反对 /a|ab/ 将匹配整个字符串, “ab” . 但是一个普通的回溯NFA,就像你经常看到的那样,会做一些其他的事情:它会关心订购,所以匹配相同的 “ab” 用同样的线 /a | ab公司/ 模式会选择开始的部分, "a" .

下一个问题是相同模式的捕获组。如果它们是故意的,那么它们是奇怪的,因为您保留的是两位数字,而不是一位数字。其他的模式并没有做到这一点,但据说它们在行为上是相同的。所以我要假设他们在这里是错误的。否则,捕获组的内存使用当然会比存储所需的成本更高不这样做。

下一个问题是没有任何锚。同样,我们也不知道这些是否正确,因为我们不清楚输入集是什么样子的,也不清楚特定引擎使用未编排的模式做什么。大多数引擎都会搜索字符串中的所有位置,但一些不太友好的引擎会在字符串中添加行首(BOL)和行尾(EOL)锚。在更为常用的引擎中,如果不发生这种情况,则行中间的邮政编码也将匹配,因为五位数字显然包含一位和两位数字的子字符串。你是否愿意 ^ 和 $ 锚,或 \b 锚,我猜不出来。

所以我得在这里做些猜测。我将关闭锚,但我将重新排序第三个版本分支,因为否则你永远无法匹配一个两位数的正常(非POSIX)类型的回溯NFAs大多数事情运行。

在考虑时机之前,看看regex编译器是用这些模式构建什么样的程序是值得的。

% perl -Mre=debug -ce '@pats = ( qr/[0-9]{1,2}/, qr/[0-9]?[0-9]/, qr/[0-9][0-9]|[0-9]/ )'
Compiling REx "[0-9]{1,2}"
Final program:
   1: CURLY {1,2} (14)
   3:   ANYOF[0-9][] (0)
  14: END (0)
stclass ANYOF[0-9][] minlen 1 
Compiling REx "[0-9]?[0-9]"
synthetic stclass "ANYOF[0-9][]".
Final program:
   1: CURLY {0,1} (14)
   3:   ANYOF[0-9][] (0)
  14: ANYOF[0-9][] (25)
  25: END (0)
stclass ANYOF[0-9][] minlen 1 
Compiling REx "[0-9][0-9]|[0-9]"
Final program:
   1: BRANCH (24)
   2:   ANYOF[0-9][] (13)
  13:   ANYOF[0-9][] (36)
  24: BRANCH (FAIL)
  25:   ANYOF[0-9][] (36)
  36: END (0)
minlen 1 
-e syntax OK
Freeing REx: "[0-9]{1,2}"
Freeing REx: "[0-9]?[0-9]"
Freeing REx: "[0-9][0-9]|[0-9]"

查看编译的模式确实是个好主意。观察正在执行的编译模式会更有指导意义。这两个都要注意:

% perl -Mre=debug -e '"aabbbababbaaqcccaaaabcacabba" =~ /abc|bca|cab|caab|baac|bab|aaa|bbb/'
Compiling REx "abc|bca|cab|caab|baac|bab|aaa|bbb"
Final program:
   1: TRIEC-EXACT[abc] (25)
      <abc> 
      <bca> 
      <cab> 
      <caab> 
      <baac> 
      <bab> 
      <aaa> 
      <bbb> 
  25: END (0)
stclass AHOCORASICKC-EXACT[abc] minlen 3 
Matching REx "abc|bca|cab|caab|baac|bab|aaa|bbb" against "aabbbababbaaqcccaaaabcacabba"
Matching stclass AHOCORASICKC-EXACT[abc] against "aabbbababbaaqcccaaaabcacabba" (28 chars)
   0 <> <aabbbababb>         | Charid:  1 CP:  61 State:    1, word=0 - legal
   1 <a> <abbbababba>        | Charid:  1 CP:  61 State:    2, word=0 - legal
   2 <aa> <bbbababbaa>       | Charid:  2 CP:  62 State:   11, word=0 - fail
   2 <aa> <bbbababbaa>       | Fail transition to State:    2, word=0 - legal
   3 <aab> <bbababbaaq>      | Charid:  2 CP:  62 State:    3, word=0 - fail
   3 <aab> <bbababbaaq>      | Fail transition to State:    5, word=0 - legal
   4 <aabb> <bababbaaqc>     | Charid:  2 CP:  62 State:   13, word=0 - legal
   5 <aabbb> <ababbaaqcc>    | Charid:  1 CP:  61 State:   14, word=8 - accepting
Matches word #8 at position 2. Trying full pattern...
   2 <aa> <bbbababbaa>       |  1:TRIEC-EXACT[abc](25)
   2 <aa> <bbbababbaa>       |    State:    1 Accepted:    0 Charid:  2 CP:  62 After State:    5
   3 <aab> <bbababbaaq>      |    State:    5 Accepted:    0 Charid:  2 CP:  62 After State:   13
   4 <aabb> <bababbaaqc>     |    State:   13 Accepted:    0 Charid:  2 CP:  62 After State:   14
   5 <aabbb> <ababbaaqcc>    |    State:   14 Accepted:    1 Charid:  8 CP:   0 After State:    0
                                  got 1 possible matches
                                  only one match left: #8 <bbb>
   5 <aabbb> <ababbaaqcc>    | 25:END(0)
Match successful!
Freeing REx: "abc|bca|cab|caab|baac|bab|aaa|bbb"

编译器得到了 真聪明 在我们身上,把它编译成一个ahocarasick-trie结构。显然,这将执行完全不同于正常的回溯NFA将对同一个程序。

不管怎样,这里是你的模式的时间,或接近他们。我为第二个添加了一个替代公式,并且我交换了第三个的替代顺序。

testing against short_fail
                 Rate     second      first      third second_alt
second      9488823/s         --        -9%       -21%       -29%
first      10475308/s        10%         --       -13%       -22%
third      11998438/s        26%        15%         --       -11%
second_alt 13434377/s        42%        28%        12%         --

testing against long_fail
                 Rate     second      first      third second_alt
second     11221411/s         --        -3%        -5%        -5%
first      11618967/s         4%         --        -1%        -1%
third      11776451/s         5%         1%         --        -0%
second_alt 11786700/s         5%         1%         0%         --
testing against short_pass

                 Rate      first second_alt     second      third
first      11720379/s         --        -4%        -7%        -7%
second_alt 12199048/s         4%         --        -3%        -4%
second     12593191/s         7%         3%         --        -1%
third      12663378/s         8%         4%         1%         --

testing against long_pass
                 Rate      third     second      first second_alt
third      11135053/s         --        -1%        -5%        -8%
second     11221655/s         1%         --        -4%        -7%
first      11716924/s         5%         4%         --        -3%
second_alt 12042240/s         8%         7%         3%         --

这是由这个节目制作的:

#!/usr/bin/env perl
use Benchmark qw<cmpthese>;

$short_fail = "a" x   1;
$long_fail  = "a" x 600;

$short_pass = $short_fail . 42;
$long_pass  = $long_fail  . 42;

for my $name (qw< short_fail long_fail short_pass long_pass >) {   
    print "\ntesting against $name\n";
    $_ = $$name;    
    cmpthese 0 => {
        first       => '/[0-9]{1,2}/',
        second      => '/[0-9]?[0-9]/',
        second_alt  => '/[0-9][0-9]?/',
        third       => '/[0-9][0-9]|[0-9]/',
    }    
}

以下是添加了锚的数字:

testing against short_fail
                 Rate      first     second second_alt      third
first      11720380/s         --        -3%        -4%       -11%
second     12058622/s         3%         --        -1%        -9%
second_alt 12180583/s         4%         1%         --        -8%
third      13217006/s        13%        10%         9%         --
testing against long_fail
                 Rate      third      first second_alt     second
third      11378120/s         --        -2%        -4%       -12%
first      11566419/s         2%         --        -2%       -10%
second_alt 11830740/s         4%         2%         --        -8%
second     12860517/s        13%        11%         9%         --
testing against short_pass
                 Rate     second      third second_alt      first
second     11540465/s         --        -5%        -5%        -7%
third      12093336/s         5%         --        -0%        -3%
second_alt 12118504/s         5%         0%         --        -2%
first      12410348/s         8%         3%         2%         --
testing against long_pass
                 Rate      first     second second_alt      third
first      11423466/s         --        -1%        -4%        -7%
second     11545540/s         1%         --        -3%        -7%
second_alt 11870086/s         4%         3%         --        -4%
third      12348377/s         8%         7%         4%         --

下面是生成第二组数字的最小修改程序:

#!/usr/bin/env perl
use Benchmark qw<cmpthese>;

$short_fail = 1  . "a";
$long_fail  = 1  . "a" x 600;

$short_pass =  2;
$long_pass  = 42;

for my $name (qw< short_fail long_fail short_pass long_pass >) {
    print "testing against $name\n";
    $_ = $$name;
    cmpthese 0 => {
        first       => '/^(?:[0-9]{1,2})$/',
        second      => '/^(?:[0-9]?[0-9])$/',
        second_alt  => '/^(?:[0-9][0-9]?)$/',
        third       => '/^(?:[0-9][0-9]|[0-9])$/',
    }
}

Lucero 14 年前

如果其中一个必须更快(可能取决于使用的regex引擎),那么在我看来,很明显第一个(可以是一个简单的Morris Pratt表DFA,与其他两个相反),因为其他两个可能需要回溯或执行额外的工作:

[0-9]?[0-9] -对于一个数字的情况,引擎会贪婪地匹配第一个数字,然后第二个数字失败;回溯然后成功

[0-9]|([0-9][0-9]) -这里使用了一个捕捉组,可以减缓速度

Ivo Wetzel 14 年前

我不知道内部结构,但一些假板凳怎么办?:天

蟒蛇

import re
import time

regs = ["^[0-9]{1,2}$", "^[0-9]?[0-9]$", "^[0-9]|([0-9][0-9])$"]
numbers = [str(n) for n in range(0, 100)]

result = None

// determine loop overhead
start = time.time()
for e in xrange(0, 10000):
    for n in numbers:
        result = n

loop = time.time() - start


for i in regs:
    r = re.compile(i)
    now = time.time()
    for e in xrange(0, 10000):
        for n in numbers:
            result = r.search(n)

    print (time.time() - now) - loop

以秒为单位的结果

0.874
0.869
0.809

JavaScript

var regs = ["^[0-9]{1,2}$", "^[0-9]?[0-9]$", "^[0-9]|([0-9][0-9])$"]

var numbers = [];
for(var n = 0; n < 100; n++) {
    numbers.push(''+n);
}


// determine loop overhead
var result = null;
var start = new Date().getTime();
for(var e = 0; e < 10000; e++) {
    for(var n = 0; n < 100; n++) {
        result = numbers[n];
    }
}

// test regex
var loop = new Date().getTime() - start;
for(var i = 0; i < regs.length; i++) {
    var r = new RegExp(regs[i]);
    var now = new Date().getTime();
    for(var e = 0; e < 10000; e++) {
        for(var n = 0; n < 100; n++) {
            result = r.exec(numbers[n]);
        }
    }
    console.log((new Date().getTime() - now) - loop); //using document.write here in Browsers
}

以秒为单位的结果

Node.js
0.197
0.193
0.226

Opera 11
0.836
0.408
0.372

Firefox 4
2.039
2.491
2.488

我们学到了什么?好吧,蟒蛇似乎是相当慢,V8似乎是相当快。
但是坐板凳总是很有趣的!

更新:Java版本

import java.util.regex.Pattern;

public class Test {
    public static void main(String args[]) {
        test();
        test();
        test();
        test();
    }

    public static void test() {
        String regs[] = {"^[0-9]{1,2}$", "^[0-9]?[0-9]$", "^[0-9]|([0-9][0-9])$"};
        String numbers[] = new String[100];
        for(int n = 0; n < 100; n++) {
            numbers[n] = Integer.toString(n);
        }

        // determine loop overhead
        String nresult = "";
        long start = System.nanoTime();
        for(int e = 0; e < 10000; e++) {
            for(int n = 0; n < 100; n++) {
                nresult = numbers[n];
            }
        }

        long loop = System.nanoTime() - start;

        boolean result = false;
        for(int i = 0; i < regs.length; i++) {
            Pattern p = Pattern.compile(regs[i]);

            long now = System.nanoTime();
            for(int e = 0; e < 10000; e++) {
                for(int n = 0; n < 100; n++) {
                    result = p.matcher(numbers[i]).matches();
                }
            }
            System.out.println(((System.nanoTime() - now) - loop) / 1000000);
        }
        System.out.println(result);
        System.out.println(nresult);
    }
}

以秒为单位的结果(第4次运行的次数)

0.230
0.262
0.210

jfclavette 14 年前

那些正则表达式太小了,应该没关系。但是,如果我必须选择一个更有效的实现,它可能是[0-9]{1,2}或者[0-9][0-9]?,这不在您的选择范围内,因为不需要回溯。

R.. GitHub STOP HELPING ICE 14 年前

就像C和 ++i 对 i=i+1 ,一个好的regex编译器应该把这三个编译成 完全相同的有限自动机 . 如果没有,我会认为那是个虫子。

(异常:如果启用了带圆括号的子表达式标记,则第三个显然会编译为包含额外的标记信息。)