regex - 优化一个充满 '?' 的正则表达式

Question

在速记键盘上，有键STKPWHRAO*EUFRPBLGTSDZ。用户按下几个键，然后在抬起时一次性注册所有键。这类似于在钢琴上弹奏和弦。示例笔划为 KAT、TPHOEUGT。

我有一个正则表达式来测试有效的速记和弦。它可以是任意数量的这些键，但它们必须按该顺序排列。我的解决方案是 qr/S?T?K?P?W?H?R?A?O?\*?E?U?F?R?P?B?L?G?T?S?D ?Z?/ 但由于此正则表达式被调用了数百次，可变长度可能成为速度瓶颈。由于所有 ?

，正则表达式中的每一步都是越来越大的可能性集

是否有更快的正则表达式方法？如果键乱序，我需要正则表达式失败。

Answer 1

要检查字符串是否是有效的和弦，您实际上需要

/^(?=.)S?T?K?P?W?H?R?A?O?\*?E?U?F?R?P?B?L?G?T?S?D?Z?\z/s

一个简单的优化是确保匹配是可能的。

/^(?=[STKPWHRAO*EUFBLGDZ])S?T?K?P?W?H?R?A?O?\*?E?U?F?R?P?B?L?G?T?S?D?Z?\z/s

下一步是消除回溯。这就是浪费时间的地方。

/
   ^
   (?=[STKPWHRAO*EUFBLGDZ])
   S?+ T?+ K?+ P?+ W?+ H?+ R?+ A?+ O?+ \*?+ E?+
   U?+ F?+ R?+ P?+ B?+ L?+ G?+ T?+ S?+  D?+ Z?+
   \z
/x

幸运的是，即使S、T、P和R出现了两次，回溯也可以完全消除没有麻烦。这实际上应该匹配时间几乎为零。

如果这还不够快，下一步就是编写专门的 C 函数。启动正则表达式匹配引擎是昂贵的，并且可以通过一个简单的函数完全避免。

请注意，上述优化仅在模式不匹配时有用。当模式匹配时，它们应该是中性的。另一方面，即使 then 模式匹配，C 函数也会有所帮助。

基准:

use strict;
use warnings;
use feature qw( say );

use Benchmark qw( cmpthese );

my %tests = (
   orig => q{ $s =~ /^(?=.)S?T?K?P?W?H?R?A?O?\*?E?U?F?R?P?B?L?G?T?S?D?Z?\z/s},
   new  => q{ $s =~
      /
         ^
         (?=[STKPWHRAO*EUFBLGDZ])
         S?+ T?+ K?+ P?+ W?+ H?+ R?+ A?+ O?+ \*?+ E?+
         U?+ F?+ R?+ P?+ B?+ L?+ G?+ T?+ S?+  D?+ Z?+
         \z
      /x
   },
);

$_ = 'use strict; use warnings; our $s; ' . $_
   for values %tests;

{ say "Matching:";     local our $s = "STAODZ";   cmpthese(-3, \%tests); }
{ say "Not matching:"; local our $s = "STPRSTPR"; cmpthese(-3, \%tests); }

输出:

Matching:
         Rate  new orig
new  509020/s   -- -29%
orig 712274/s  40%   --
Not matching:
         Rate orig  new
orig 158758/s   -- -73%
new  579851/s 265%   --

这意味着
匹配从 1.40μs 减慢到 1.96μs(在本例中)，并且
非匹配速度从 6.30μs 提高到 1.72μs(在本例中)。

---

要检查字符串是否是一系列有效的和弦，您只需要

/^[STKPWHRAO*EUFBLGDZ]+\z/

---

如果你想提取字符串中的所有和弦，我会先提取与以下匹配的序列，然后在提取的序列中找到和弦:

/([STKPWHRAO*EUFBLGDZ]+)/