이 Perl 정규식에서`\ s +`가`\ s \ s *`보다 훨씬 빠른 이유는 무엇입니까?

programing

이 Perl 정규식에서`\ s +`가`\ s \ s *`보다 훨씬 빠른 이유는 무엇입니까?

nasanasas 2020. 12. 31. 08:28

이 Perl 정규식에서`\ s +`가`\ s \ s *`보다 훨씬 빠른 이유는 무엇입니까?

대체 \s*(또는 심지어 \s\s*) \s+가이 입력의 속도를 높이는 이유는 무엇 입니까?

use Benchmark qw(:all);
$x=(" " x 100000) . "_\n";
$count = 100;
timethese($count, {
    '/\s\s*\n/' => sub { $x =~ /\s\s*\n/ },
    '/\s+\n/' => sub { $x =~ /\s+\n/ },
});

온라인 버전에 연결

s/\s*\n\s*/\n/g내 코드에서 느린 정규식 을 발견했습니다. 여기 저기 몇 개의 공백이없는 많은 공백으로 구성된 450KB 입력 파일과 끝에 마지막 줄 바꿈이 주어 졌을 때 정규식이 중단되고 완료되지 않았습니다.

나는 직관적으로 정규식을로 교체했으며 s/\s+\n/\n/g; s/\n\s+/\n/g;모두 잘되었습니다.

하지만 왜 그렇게 더 빠를까요? 사용 후 버전이 한 번만 반복 실행되도록 최적화되어 re Debug => "EXECUTE"있음을 알았습니다 \s+. http://pastebin.com/0Ug6xPiQ

Matching REx "\s*\n" against "       _%n"
Matching stclass ANYOF{i}[\x09\x0a\x0c\x0d ][{non-utf8-latin1-all}{unicode_all}] against "       _%n" (9 bytes)
   0 <> <       _%n>         |  1:STAR(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
   1 < > <      _%n>         |  1:STAR(3)
                                  SPACE can match 6 times out of 2147483647...
                                  failed...
   2 <  > <     _%n>         |  1:STAR(3)
                                  SPACE can match 5 times out of 2147483647...
                                  failed...
   3 <   > <    _%n>         |  1:STAR(3)
                                  SPACE can match 4 times out of 2147483647...
                                  failed...
   4 <    > <   _%n>         |  1:STAR(3)
                                  SPACE can match 3 times out of 2147483647...
                                  failed...
   5 <     > <  _%n>         |  1:STAR(3)
                                  SPACE can match 2 times out of 2147483647...
                                  failed...
   6 <      > < _%n>         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
                                  failed...
   8 <       _> <%n>         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
   8 <       _> <%n>         |  3:  EXACT <\n>(5)
   9 <       _%n> <>         |  5:  END(0)
Match successful!

Matching REx "\s+\n" against "       _%n"
Matching stclass SPACE against "       _" (8 bytes)
   0 <> <       _%n>         |  1:PLUS(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...

줄 바꿈이 없으면 Perl 5.10+가 정규식을 실행하지 않고 즉시 실패한다는 것을 알고 있습니다. 나는 그것이하는 검색의 양을 줄이기 위해 개행의 위치를 사용하고 있다고 생각합니다. 위의 모든 경우 /\s*\n/에 대해 관련된 역 추적을 영리하게 줄이는 것 같습니다 (일반적으로 공백 문자열에 대해 지수 시간이 소요됨). 누구든지 \s+버전이 훨씬 빠른 이유에 대한 통찰력을 제공 할 수 있습니까 ?

또한 \s*?속도 향상을 제공하지 않습니다.

\s+패턴의 시작 부분에 "플러스"노드 (예 :)가 있고 노드가 일치하지 않으면 정규식 엔진은 실패 지점으로 건너 뛰고 다시 시도합니다. 와 \s*, 다른 한편으로, 엔진은 한 번에 하나 개의 문자를 진행시킨다.

Yves Orton은이 최적화를 여기에서 잘 설명합니다 .

시작 클래스 최적화에는 "모든 유효한 시작 위치 시도"(doevery) 및 "플립 플롭 모드"(! doevery)의 두 가지 모드가 있습니다. 여기서 시퀀스의 첫 번째 유효한 시작 위치 만 시도합니다.

/ (\ d +) X / 및 문자열 "123456Y"를 고려해보십시오. 이제 "123456"과 일치 한 후 X를 일치시키지 않으면 "23456"이후에도 일치하지 않을 것임을 알 수 있습니다 (사악한 속임수가 없다고 가정하면 어쨌든 최적화를 비활성화하는 것입니다), 그래서 우리는 확인 / fails / 때까지 앞으로 건너 뛰고 나서야 실제 일치를 찾기 시작할 수 있습니다. 이것은 플립 플롭 모드입니다.

/\s+/플립 플롭 모드를 트리거합니다. /\s*/, /\s\s*/및 /\s\s+/하지 마십시오. 이 최적화는 \s*0 개의 문자와 일치 할 수 있기 때문에 "별표"노드에 적용 할 수 없습니다 . 따라서 시퀀스의 한 지점에서 발생한 오류는 나중에 동일한 시퀀스에서 오류를 나타내지 않습니다.

각 정규식에 대한 디버그 출력에서이를 확인할 수 있습니다. 건너 뛴 문자를 ^. 이것을 비교하십시오 (한 번에 4 자 건너 뛰기) :

$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d+x/'
   ...
   0 <> <123 456 78>         |  1:PLUS(3)
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   4 <123 > <456 789 x>      |  1:PLUS(3)
      ^^^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   8 <23 456 > <789 x>       |  1:PLUS(3)
         ^^^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...

여기에 (한 번에 하나 또는 두 문자 건너 뛰기) :

$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d*x/'
   ...
   0 <> <123 456 78>         |  1:STAR(3)
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   1 <1> <23 456 789>        |  1:STAR(3)
      ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
   2 <12> <3 456 789 >       |  1:STAR(3)
       ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
   4 <123 > <456 789 x>      |  1:STAR(3)
        ^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   5 <123 4> <56 789 x>      |  1:STAR(3)
          ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
   6 <23 45> <6 789 x>       |  1:STAR(3)
          ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
   8 <23 456 > <789 x>       |  1:STAR(3)
           ^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   9 <23 456 7> <89 x>       |  1:STAR(3)
             ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
  10 <23 456 78> <9 x>       |  1:STAR(3)
              ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
  12 <23 456 789 > <x>       |  1:STAR(3)
               ^^
                                  POSIXD[\d] can match 0 times out of 2147483647...
  12 <23 456 789 > <x>       |  3:  EXACT <x>(5)
  13 <23 456 789 x> <>       |  5:  END(0)

는 패턴의 시작 부분이 아니기 /\s\s+/때문에 최적화가에 적용 \s+되지 않습니다. 그러나 /\s\s+/(논리적으로는 /\s{2,}/)와 /\s\s*/(논리적으로는 /\s+/) 모두 최적화 될 수 있습니다. perl5 포터 에게 둘 중 하나가 노력할만한 가치가 있는지 묻는 것이 합리적 입니다.

_{관심이있는 경우 PREGf_SKIP컴파일 할 때 정규식에 플래그를 설정하여 "플립 플롭 모드"를 활성화합니다 . 5.24.0 소스의 regcomp.c 에서 줄 7344 및 7405와 regexec.c 에서 줄 1585 주변의 코드를 참조하십시오 .}

첫째, 결과 정규식 같은 의미를 유지하지 않더라도의가 정규 표현식에 감소하자 \s*0및 \s+0사용 (" " x 4) . "_0"입력으로. 회의론자들에게는 지연이 여전히 존재한다는 것을 여기서 볼 수 있습니다 .

이제 다음 코드를 살펴 보겠습니다.

$x = (" " x 4) . "_ 0";
$x =~ /\s*0/; # The slow line 
$x =~ /\s+0/; # The fast line

조금만 파면 use re debugcolor;다음과 같은 결과가 나옵니다 .

Guessing start of match in sv for REx "\s*0" against "    _0"
Found floating substr "0" at offset 5...
start_shift: 0 check_at: 5 s: 0 endpos: 6 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s*0" against "    _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against "    _0" (6 bytes)
   0 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 4 times out of 2147483647...
                                  failed...
   1 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 3 times out of 2147483647...
                                  failed...
   2 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 2 times out of 2147483647...
                                  failed...
   3 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 1 times out of 2147483647...
                                  failed...
   5 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 0 times out of 2147483647...
   5 <    _0>|  3:  EXACT <0>(5)
   6 <    _0>|  5:  END(0)
Match successful!

-----------------------

Guessing start of match in sv for REx "\s+0" against "    _0"
Found floating substr "0" at offset 5...
start_shift: 1 check_at: 5 s: 0 endpos: 5 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+0" against "    _0"
Matching stclass POSIXD[\s] against "    _" (5 bytes)
   0 <    _0>|  1:PLUS(3)
                                  POSIXD[\s] can match 4 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed

Perl은 실패에 최적화 된 것 같습니다 . 먼저 상수 문자열 (O (N) 만 소비 함)을 찾습니다. 여기에서 다음을 찾습니다 0.Found floating substr "0" at offset 5...

그런 다음 시작하자 변수 정규식, respectivly의 일부 \s*및 \s+확인 전체 최소 문자열에 대하여 :

Matching REx "\s*0" against "    _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against "    _0" (6 bytes)
Matching REx "\s+0" against "    _0"
Matching stclass POSIXD[\s] against "    _" (5 bytes) # Only 5 bytes because there should be at least 1 "\s" char

그 후 stclass요구 사항을 충족하는 첫 번째 위치 ( 여기 위치 0)를 찾습니다 .

\s*0:
- 0에서 시작하여 4 개의 공백을 찾은 다음 실패합니다.
- 1에서 시작하여 3 개의 공백을 찾은 다음 실패합니다.
- 2에서 시작하여 2 개의 공백을 찾은 다음 실패합니다.
- 3에서 시작하여 1 개의 공백을 찾은 다음 실패합니다.
- 4에서 시작하여 0 개의 공백을 찾은 다음 실패하지 않습니다 .
- 정확한 찾기 0
\s+0:
- 0에서 시작하여 4 개의 공백을 찾은 다음 실패합니다. 최소 공백 수가 일치하지 않으므로 정규식이 즉시 실패합니다.

Perl 정규식 최적화를 즐기고 싶다면 다음 정규식 / *\n과 / * \n. 언뜻보기에는 똑같이 보이고 같은 의미를 가지고 있습니다.하지만 (" " x 40000) . "_\n"첫 번째 것과 비교 하면 모든 가능성을 확인하고 두 번째는 " \n"즉시 찾아서 실패합니다.

최적화되지 않은 바닐라 정규식 엔진에서 두 정규식은 모두 패턴이 충돌 할 때 다시 시도해야하기 때문에 치명적인 역 추적을 일으킬 수 있습니다. 그러나 위의 예에서 두 번째는 Perl로 최적화 되었기 때문에 실패하지 않습니다.find floating substr "0%n"

Jeff Atwood의 블로그 에서 다른 예를 볼 수 있습니다 .

이 문제에 대해 아님을 유의하십시오 \s고려 그러나 어떤 패턴 xx*대신에 사용되는 x+참조 0으로 예를 또한 정규식 폭발 수량 어

이처럼 짧은 예제에서는 동작이 "찾기 가능"하지만 복잡한 패턴으로 플레이하기 시작하면 찾기가 쉽지 않습니다. 예 : 정규식이 프로그램을 중단합니다 (CPU 사용량 100 %).

는 \s+\n앞의 문자가 있어야 \n입니다 SPACE.

use re qw(debug)컴파일 에 따르면 \n입력에서 처음 확인되는 부분 문자열까지 알려진 수의 공백의 직선 문자열이 필요하다는 것을 설정합니다 . 그런 다음 입력의 나머지 부분에 대해 고정 길이 공간 전용 하위 문자열을 확인하여 _. 입력에 얼마나 많은 공간이 있는지에 관계없이 확인할 수있는 단일 가능성입니다. (더 많은 _\n경우 디버그 출력마다 똑같이 실패하는 것으로 확인됩니다.)

이런 식으로 보았을 때, 다소 구체적인 검색 패턴을 활용하고이 입력으로 운이 좋은 것으로 거의 기대할 수있는 최적화입니다. 분명히 이런 종류의 분석을 수행하지 않는 다른 엔진과 비교할 때를 제외하고.

With \s*\n this is not the case. Once the \n is found and the previous character is not a space, the search hasn't failed since \s* allows nothing (zero characters). There are no fixed-length substrings either, and it's in the backtracking game.

I am not sure of the internals of the regular expression engine, but it looks like it does not recognize that \s+ is in some way the same as \s\s*, since in the second one it matches a space, and then tries to match ever growing numbers of spaces, while in the first, it immediately concludes that there is no match.

The output using use re qw( Debug ); clearly shows this, using a much shorter string:

test_re.pl

#!/usr/bin/env perl
use re qw(debug);

$x=(" " x 10) . "_\n";
print '-'x50 . "\n";
$x =~ /\s+\n/;
print '-'x50 . "\n";
$x =~ /\s\s*\n/;
print '-'x50 . "\n";

Output

Compiling REx "\s+\n"
Final program:
    1: PLUS (3)
    2:   SPACE (0)
    3: EXACT <\n> (5)
    5: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE plus minlen 2
Compiling REx "\s\s*\n"
Final program:
    1: SPACE (2)
    2: STAR (4)
    3:   SPACE (0)
    4: EXACT <\n> (6)
    6: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE minlen 2
--------------------------------------------------
Guessing start of match in sv for REx "\s+\n" against "          _%n"
Found floating substr "%n" at offset 11...
    start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+\n" against "          _%n"
Matching stclass SPACE against "          _" (11 bytes)
   0 <> <          >         |  1:PLUS(3)
                                  SPACE can match 10 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Guessing start of match in sv for REx "\s\s*\n" against "          _%n"
Found floating substr "%n" at offset 11...
    start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s\s*\n" against "          _%n"
Matching stclass SPACE against "          _" (11 bytes)
   0 <> <          >         |  1:SPACE(2)
   1 < > <         _>        |  2:STAR(4)
                                  SPACE can match 9 times out of 2147483647...
                                  failed...
   1 < > <         _>        |  1:SPACE(2)
   2 <  > <        _>        |  2:STAR(4)
                                  SPACE can match 8 times out of 2147483647...
                                  failed...
   2 <  > <        _>        |  1:SPACE(2)
   3 <   > <       _%n>      |  2:STAR(4)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
   3 <   > <       _%n>      |  1:SPACE(2)
   4 <    > <      _%n>      |  2:STAR(4)
                                  SPACE can match 6 times out of 2147483647...
                                  failed...
   4 <    > <      _%n>      |  1:SPACE(2)
   5 <     > <     _%n>      |  2:STAR(4)
                                  SPACE can match 5 times out of 2147483647...
                                  failed...
   5 <     > <     _%n>      |  1:SPACE(2)
   6 <      > <    _%n>      |  2:STAR(4)
                                  SPACE can match 4 times out of 2147483647...
                                  failed...
   6 <      > <    _%n>      |  1:SPACE(2)
   7 <       > <   _%n>      |  2:STAR(4)
                                  SPACE can match 3 times out of 2147483647...
                                  failed...
   7 <       > <   _%n>      |  1:SPACE(2)
   8 <        > <  _%n>      |  2:STAR(4)
                                  SPACE can match 2 times out of 2147483647...
                                  failed...
   8 <        > <  _%n>      |  1:SPACE(2)
   9 <         > < _%n>      |  2:STAR(4)
                                  SPACE can match 1 times out of 2147483647...
                                  failed...
   9 <         > < _%n>      |  1:SPACE(2)
  10 <          > <_%n>      |  2:STAR(4)
                                  SPACE can match 0 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Freeing REx: "\s+\n"
Freeing REx: "\s\s*\n"

ReferenceURL : https://stackoverflow.com/questions/38431931/why-is-s-so-much-faster-than-s-s-in-this-perl-regex

'programing' 카테고리의 다른 글

ES6 모듈을 사용하여 단위 테스트에 대한 종속성을 모의하는 방법 (0)	2020.12.31
Babel 6을 ES5 자바 스크립트로 컴파일하려면 어떻게해야합니까? (0)	2020.12.31
변수가 두 값 중 하나와 같은지 테스트 (0)	2020.12.31
사이트 배경으로 비디오? (0)	2020.12.31
이 두 파이썬 shebangs의 차이점은 무엇입니까 (0)	2020.12.31

현재글이 Perl 정규식에서`\ s +`가`\ s \ s *`보다 훨씬 빠른 이유는 무엇입니까?

nasanasa

이 Perl 정규식에서`\ s +`가`\ s \ s *`보다 훨씬 빠른 이유는 무엇입니까?

이 Perl 정규식에서`\ s +`가`\ s \ s *`보다 훨씬 빠른 이유는 무엇입니까?

'programing' 카테고리의 다른 글

'programing'의 다른글

티스토리툴바

이 Perl 정규식에서`\ s +`가`\ s \ s *`보다 훨씬 빠른 이유는 무엇입니까?

이 Perl 정규식에서`\ s +`가`\ s \ s *`보다 훨씬 빠른 이유는 무엇입니까?

'programing' 카테고리의 다른 글

'programing'의 다른글

관련글

티스토리툴바