gpt4 book ai didi

regex - 为什么正则表达式/[\w\W] + x/i运行起来会非常慢?

转载 作者:行者123 更新时间:2023-12-04 03:19:49 28 4
gpt4 key购买 nike

尝试:

time perl -E '$x="a" x 100000; $x =~ /[\w\W]+x/i'  

将运行很长时间(在我的笔记本上20秒)。没有 /i,例如
time perl -E '$x="a" x 100000; $x =~ /[\w\W]+x/' 

在0.07秒内完成。

不管正则表达式 [\w\W]没有多大意义,这种巨大的差异使我感到惊讶。

为什么会有如此大的差异?

编辑

更准确地说:
$ time perl -E '$x="a" x 100000; $x =~ /[\w\W]+x/i'  

real 0m19.479s
user 0m19.419s
sys 0m0.038s

我的 perl
Summary of my perl5 (revision 5 version 20 subversion 3) configuration:

Platform:
osname=darwin, osvers=15.0.0, archname=darwin-2level
uname='darwin nox.local 15.0.0 darwin kernel version 15.0.0: sat sep 19 15:53:46 pdt 2015; root:xnu-3247.10.11~1release_x86_64 x86_64 '
config_args='-Dprefix=/opt/anyenv/envs/plenv/versions/5.20.3 -de -Dusedevel -A'eval:scriptdir=/opt/anyenv/envs/plenv/versions/5.20.3/bin''
hint=recommended, useposix=true, d_sigaction=define
useithreads=undef, usemultiplicity=undef
use64bitint=define, use64bitall=define, uselongdouble=undef
usemymalloc=n, bincompat5005=undef
Compiler:
cc='cc', ccflags ='-fno-common -DPERL_DARWIN -fno-strict-aliasing -pipe -fstack-protector -I/opt/local/include',
optimize='-O3',
cppflags='-fno-common -DPERL_DARWIN -fno-strict-aliasing -pipe -fstack-protector -I/opt/local/include'
ccversion='', gccversion='4.2.1 Compatible Apple LLVM 7.0.0 (clang-700.1.76)', gccosandvers=''
intsize=4, longsize=8, ptrsize=8, doublesize=8, byteorder=12345678
d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16
ivtype='long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
alignbytes=8, prototype=define
Linker and Libraries:
ld='env MACOSX_DEPLOYMENT_TARGET=10.3 cc', ldflags =' -fstack-protector -L/opt/local/lib'
libpth=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../lib/clang/7.0.0/lib /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib /usr/lib /opt/local/lib
libs=-lpthread -lgdbm -ldbm -ldl -lm -lutil -lc
perllibs=-lpthread -ldl -lm -lutil -lc
libc=, so=dylib, useshrplib=false, libperl=libperl.a
gnulibc_version=''
Dynamic Linking:
dlsrc=dl_dlopen.xs, dlext=bundle, d_dlsymun=undef, ccdlflags=' '
cccdlflags=' ', lddlflags=' -bundle -undefined dynamic_lookup -L/opt/local/lib -fstack-protector'


Characteristics of this binary (from libperl):
Compile-time options: HAS_TIMES PERLIO_LAYERS PERL_DONT_CREATE_GVSV
PERL_HASH_FUNC_ONE_AT_A_TIME_HARD PERL_MALLOC_WRAP
PERL_NEW_COPY_ON_WRITE PERL_PRESERVE_IVUV
PERL_USE_DEVEL USE_64_BIT_ALL USE_64_BIT_INT
USE_LARGE_FILES USE_LOCALE USE_LOCALE_COLLATE
USE_LOCALE_CTYPE USE_LOCALE_NUMERIC USE_PERLIO
USE_PERL_ATOF
Locally applied patches:
Devel::PatchPerl 1.38
Built under darwin
Compiled at Oct 28 2015 14:46:19
@INC:
/opt/anyenv/envs/plenv/versions/5.20.3/lib/perl5/site_perl/5.20.3/darwin-2level
/opt/anyenv/envs/plenv/versions/5.20.3/lib/perl5/site_perl/5.20.3
/opt/anyenv/envs/plenv/versions/5.20.3/lib/perl5/5.20.3/darwin-2level
/opt/anyenv/envs/plenv/versions/5.20.3/lib/perl5/5.20.3
.

从问题的背景来看:实际代码将字符串与大量正则表达式(某种反垃圾邮件)匹配,因此我无法可靠地手动检查正则表达式数据库。真正的代码片段是
sub docheck {
...
...
foreach my $regex (@$regexs) {
if ( $_[0] =~ /$regex/i ) {

[\w\W]+是10k正则表达式之一:(,例如: [\w\W]+medicine\.netfirms\.com-regex-DB可能需要清理-但...您知道:)

现在,代码已更改:
sub docheck {
...
my $str = lc($_[0]);
foreach my $regex (@$regexs) {
if ( $str =~ /$regex/ ) {

所以避免 /i

最佳答案

TL; DR
在第二种情况下,优化器非常智能,并且意识到
字符串中没有"x",因此无法进行匹配,并且会更早失败。
但是,对于/i情况,同时测试两个
大写和小写x,所以它继续进行并尝试匹配整个正则表达式。

调试
尽管我无法重现如此大的性能差异,但是针对区分大小写的匹配触发了优化。
让我们以'debug'模式运行它:
代码

use re 'debug';
$x="a" x 100000;
$x =~ /[\w\W]+x/;
  • 您还可以将-Mre=debug添加到perl调用中。

  • 输出
    Compiling REx "[\w\W]+x"
    Final program:
    1: PLUS (13)
    2: ANYOF[\x{00}-\x{7F}][{non-utf8-latin1-all}{unicode_all}] (0)
    13: EXACT <x> (15)
    15: END (0)
    floating "x" at 1..9223372036854775807 (checking floating) stclass ANYOF[\x{00}-\x{7F}][{non-utf8-latin1-all}{unicode_all}] plus minlen 2
    Matching REx "[\w\W]+x" against "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"...
    Intuit: trying to determine minimum start position...
    Did not find floating substr "x"...
    Match rejected by optimizer
    Freeing REx: "[\w\W]+x"
    并注意最后一部分:
    Intuit: trying to determine minimum start position...
    Did not find floating substr "x"...
    Match rejected by optimizer

    优化器尝试查找 "x"的第一个匹配项,由于找不到它,因此在正则表达式引擎甚至尝试匹配之前就拒绝匹配。
    Perl正则表达式经过了优化,希望尽早失败而不是成功。

    慢速情况
    我无法在终端上重现相同的行为(Perl v5.20.2),但在以后的优化中失败了,这可能是由于特定于版本的差异所致。但是,在这种情况下不会进行不区分大小写的 "x"的优化。
    不会触发此优化,因为它有超过一种匹配主题的可能性(小写的 "x"和大写的 "X")。
  • 如果您对此优化内部知识感兴趣,请检查ThisSuitIsBlackNot's answer

  • 现在,在没有优化的情况下,正则表达式引擎理论上会尝试将 "x"匹配为:
  • 一起在 [\w\W]+中进行所有可能的匹配(使用整个字符串,然后回溯1个字符,等等)。
  • 主题字符串中的每个起始位置(99,999个位置)。

  • 当然,还有其他优化措施可以减少此数量,但这就是为什么它这么慢的原因。请注意,它随着字符串的增加呈指数增长。
    解决方法
    如果您不特别要求x之前至少要有一个字符,则应使用 /.*x/is,因为在第一个位置尝试匹配后它会失败(优化器实际上将 .* anchor 定到文本的开头)。
    *感谢 @nhahtdh提出了这一点。
    但是,对于可能出现此行为的更一般的情况,一种提高性能的选项是在其余代码之前检查 "x"(作为独立条件或在同一正则表达式中):
    $x =~ /(?:^(*COMMIT)(?=.*x))?[\w\W]+x/is;
  • (?:^ ... )?如果在字符串开头,则仅检查一次。
  • (?=.*x)如果前面有一个x
  • (*COMMIT)否则,它会回溯,并且 COMMIT 是控制动词,会使整个匹配失败。

  • 这将运行得更快。

    关于regex - 为什么正则表达式/[\w\W] + x/i运行起来会非常慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34009968/

    28 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com