2

我一直在观察带有几个前瞻的表达式的执行时间非常慢。

我想这是由于底层数据结构造成的，但这似乎非常极端，我想知道我是否做错了什么，或者是否有已知的解决方法。

问题是确定一组单词是否以任何顺序出现在字符串中。例如，我们想找出两个术语“term1”和“term2”是否在字符串中的某个位置。我用表达式做到这一点：

(?=.*\bterm1\b)(?=.*\bterm2\b)

但我观察到的是，这比首先检查要慢一个数量级

\bterm1\b

就在那时

\bterm2\b

这似乎表明我应该使用模式数组而不是带有前瞻的单个模式......这是对的吗？好像不对……

这是一个示例测试代码和结果时间：

public static void speedLookAhead() {
    Matcher m, m1, m2;
    boolean find;
    int its = 1000000;

    // create long non-matching string
    char[] str = new char[2000];
    for (int i = 0; i < str.length; i++) {
      str[i] = 'x';
    }
    String test = str.toString();

    // First method: use one expression with lookaheads
    m = Pattern.compile("(?=.*\\bterm1\\b)(?=.*\\bterm2\\b)").matcher(test);
    long time = System.currentTimeMillis();
    ;
    for (int i = 0; i < its; i++) {
      m.reset(test);
      find = m.find();
    }
    time = System.currentTimeMillis() - time;
    System.out.println(time);

    // Second method: use two expressions and AND the results
    m1 = Pattern.compile("\\bterm1\\b").matcher(test);
    m2 = Pattern.compile("\\bterm2\\b").matcher(test);
    time = System.currentTimeMillis();
    ;
    for (int i = 0; i < its; i++) {
      m1.reset(test);
      m2.reset(test);
      find = m1.find() && m2.find();
    }
    time = System.currentTimeMillis() - time;
    System.out.println(time);
  }

这在我的电脑中输出：

1754
150
4

3 回答 3

2

这可能会节省一些时间

贪婪的
([AB]).*(?!\1)[AB]

不贪心
([AB]).*?(?!\1)[AB]

重做

我在这个问题上做了我自己的板凳。一次匹配一个术语/term/
而不是一个正则表达式中的两个术语总是会花费更少的时间，因为它不会
回溯。它就像 strncmp(term) 一样简单。然后分别做 2 个术语会
快得多。

如果您可以定义术语，使得没有重叠的可能性，那么这就是
要走的路。IE; /term1/ && /term2/。

如果不调用回溯，就无法将术语组合成单个正则表达式。

也就是说，如果您真的关心重叠，那么有一些技术可以最大限度地减少
回溯。

/(?=.*A)(?=.*B)/ 就像 /A/ && /B/ 一样，只是它看起来慢了很多，两者都不考虑重叠。

所以，如果你真的关心重叠（我强烈建议你这样做），有
两种方法可以结合起来以获得最大效率。

/(A|B) .* (?!\1)(?:A|B)/

或者

/A/ && /B/ && /(A|B) .* (?!\1)(?:A|B)/

最后一个会增加一个小的（相对的）开销，但会抑制逻辑
链中的访问，要求 A 和 B 至少存在，然后再检查重叠。

而且，根据字符串中 A 和 B 的位置， /(A|B) .* (?!\1)(?:A|B)/
也可能需要时间，但它仍然是最短的时间一切都很
平均。

下面是一个 Perl 程序，它对一些示例（可能的场景）字符串进行基准测试。

祝你好运！

use strict;
use warnings;

use Benchmark ':hireswallclock';
my ($t0,$t1);

my ($term1, $term2) = ('term','m2a');
my  @samples = (
   ' xaaaaaaa term2ater  ',
   ' xaaaaaaa term2aterm ',
   ' xaaaaaaa ter2ater  ',
   ' Aaa term2ater ' . 'x 'x100 . 'xaaaaaaa mta ',
   ' Baa term      ' . 'x 'x100 . 'xaaaaaaa mta ',
   ' Caa m2a       ' . 'x 'x100 . 'xaaaaaaa term ',
   ' Daa term2a       ' . 'x 'x100 . 'xaaaaaaa term ',
);

my $rxA  = qr/$term1/;
my $rxB  = qr/$term2/;
my $rxAB = qr/ ($term1|$term2) .* (?!\1)(?:$term1|$term2) /x;


for (@samples)
{
    printf "Checking string:  '%.40s'\n-------------\n", $_;

    if (/$term1/ && /$term2/ ) {
       print "  Found possible candidates (A && B)\n";
    }
    if (/ ($term1|$term2) .* ((?!\1)(?:$term1|$term2)) /x) {
       print "  Found non-overlaped terms: '$1'  '$2'\n";
    }
    else {
       print "  No (A|B) .* (?!\\1)(A|B) terms found!\n";
    }
    print "\n   Bench\n";

    $t0 = new Benchmark;
    for my $cnt (1 .. 500_000) {
       /$rxA/  &&  /$rxB/;
    }
    $t1 = new Benchmark;
    print "    $rxA && $rxB\n    -took: ", timestr(timediff($t1, $t0)), "\n\n";

    $t0 = new Benchmark;
    for my $cnt (1 .. 500_000) {
       /$rxAB/;
    }
    $t1 = new Benchmark;
    print "    $rxAB\n    -took: ", timestr(timediff($t1, $t0)), "\n\n";

    $t0 = new Benchmark;
    for my $cnt (1 .. 500_000) {
       /$rxA/  &&  /$rxB/ && /$rxAB/;
    }
    $t1 = new Benchmark;
    print "    $rxA && $rxB &&\n    $rxAB\n    -took: ", timestr(timediff($t1, $t0)), "\n\n";

}

输出 

Checking string:  ' xaaaaaaa term2ater  '
-------------
  Found possible candidates (A && B)
  No (A|B) .* (?!\1)(A|B) terms found!

   Bench
    (?-xism:term) && (?-xism:m2a)
    -took: 1.46875 wallclock secs ( 1.47 usr +  0.00 sys =  1.47 CPU)

    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 3.3748 wallclock secs ( 3.34 usr +  0.00 sys =  3.34 CPU)

    (?-xism:term) && (?-xism:m2a) &&
    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 5.0623 wallclock secs ( 5.06 usr +  0.00 sys =  5.06 CPU)

Checking string:  ' xaaaaaaa term2aterm '
-------------
  Found possible candidates (A && B)
  Found non-overlaped terms: 'm2a'  'term'

   Bench
    (?-xism:term) && (?-xism:m2a)
    -took: 1.48403 wallclock secs ( 1.49 usr +  0.00 sys =  1.49 CPU)

    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 3.89044 wallclock secs ( 3.89 usr +  0.00 sys =  3.89 CPU)

    (?-xism:term) && (?-xism:m2a) &&
    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 5.40607 wallclock secs ( 5.38 usr +  0.00 sys =  5.38 CPU)

Checking string:  ' xaaaaaaa ter2ater  '
-------------
  No (A|B) .* (?!\1)(A|B) terms found!

   Bench
    (?-xism:term) && (?-xism:m2a)
    -took: 0.765321 wallclock secs ( 0.77 usr +  0.00 sys =  0.77 CPU)

    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 1.29674 wallclock secs ( 1.30 usr +  0.00 sys =  1.30 CPU)

    (?-xism:term) && (?-xism:m2a) &&
    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 0.874842 wallclock secs ( 0.88 usr +  0.00 sys =  0.88 CPU)

Checking string:  ' Aaa term2ater x x x x x x x x x x x x x'
-------------
  Found possible candidates (A && B)
  No (A|B) .* (?!\1)(A|B) terms found!

   Bench
    (?-xism:term) && (?-xism:m2a)
    -took: 1.46842 wallclock secs ( 1.47 usr +  0.00 sys =  1.47 CPU)

    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 28.078 wallclock secs (28.08 usr +  0.00 sys = 28.08 CPU)

    (?-xism:term) && (?-xism:m2a) &&
    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 29.4531 wallclock secs (29.45 usr +  0.00 sys = 29.45 CPU)

Checking string:  ' Baa term      x x x x x x x x x x x x x'
-------------
  No (A|B) .* (?!\1)(A|B) terms found!

   Bench
    (?-xism:term) && (?-xism:m2a)
    -took: 1.68716 wallclock secs ( 1.69 usr +  0.00 sys =  1.69 CPU)

    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 15.1563 wallclock secs (15.16 usr +  0.00 sys = 15.16 CPU)

    (?-xism:term) && (?-xism:m2a) &&
    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 1.64033 wallclock secs ( 1.64 usr +  0.00 sys =  1.64 CPU)

Checking string:  ' Caa m2a       x x x x x x x x x x x x x'
-------------
  Found possible candidates (A && B)
  Found non-overlaped terms: 'm2a'  'term'

   Bench
    (?-xism:term) && (?-xism:m2a)
    -took: 1.62448 wallclock secs ( 1.63 usr +  0.00 sys =  1.63 CPU)

    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 3.0154 wallclock secs ( 3.02 usr +  0.00 sys =  3.02 CPU)

    (?-xism:term) && (?-xism:m2a) &&
    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 4.56226 wallclock secs ( 4.56 usr +  0.00 sys =  4.56 CPU)

Checking string:  ' Daa term2a       x x x x x x x x x x x '
-------------
  Found possible candidates (A && B)
  Found non-overlaped terms: 'm2a'  'term'

   Bench
    (?-xism:term) && (?-xism:m2a)
    -took: 1.45252 wallclock secs ( 1.45 usr +  0.00 sys =  1.45 CPU)

    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 16.1404 wallclock secs (16.14 usr +  0.00 sys = 16.14 CPU)

    (?-xism:term) && (?-xism:m2a) &&
    (?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
    -took: 17.6719 wallclock secs (17.67 usr +  0.00 sys = 17.67 CPU)
于 2012-03-22T23:42:20.883 回答
1

您需要将每个循环放在一个单独的方法中，如果交换测试的顺序，您将得到不同的结果。

您可以将其与test.indexOf('A') >= 0 && test.indexOf('B') >= 0我想象的速度进行比较吗？

于 2012-03-22T21:48:21.433 回答
1

您发布的正则表达式

(?=.\A\b)(?=.\B\b)

与代码中的不匹配

.(?=.*B)(?=.*A)

事实上，第一个正则表达式似乎无法匹配。

您能否提供一些应该匹配和不匹配的内容的示例输入。

这是解释代码中的正则表达式。

Match any single character that is not a line break character «.»
Assert that the regex below can be matched, starting at this position (positive lookahead) «(?=.*B)»
   Match any single character that is not a line break character «.*»
      Between zero and unlimited times, as many times as possible, giving back as needed (greedy) «*»
   Match the character “B” literally «B»
Assert that the regex below can be matched, starting at this position (positive lookahead) «(?=.*A)»
   Match any single character that is not a line break character «.*»
      Between zero and unlimited times, as many times as possible, giving back as needed (greedy) «*»
   Match the character “A” literally «A»
于 2012-03-22T21:56:40.907 回答