☰

정규식: Perl의 정규식은 매우 느립니다. 최적화하는 방법은 무엇입니까?

tag-icon • tag-icon regular-expression perl
정규식: Perl의 정규식은 매우 느립니다. 최적화하는 방법은 무엇입니까?

이것:

echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  perl -pe '/^(.*?B(?:A.*?B){30})A/'

내 컴퓨터에서는 무려 8초가 걸렸습니다. 나는 그것이 최대 몇 밀리초 정도 걸릴 것이라고 생각했습니다.

10ms 미만이 소요됩니다.

echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
   perl -pe '/^(.*?B(?:A.*?B){30})A/'

첫 번째 작업을 더 빠르게 진행하려면 어떻게 해야 하나요?

정규 표현식이 되려면 A와 B가 필요합니다. 즉, 이들은 단순한 단일 문자가 아닙니다.

답변1

음수 예측 합계 사용 .:

perl -pe '/^((?:(?!BA).)*?B(?:A(?:(?!BA).)*?B){30})A/'

예쁘지는 않지만 효과적입니다.

답변2

사용행복하다(이전 Perl_6)

Raku로 변환된 위의 Perl Regex는 매우 느렸습니다(여전히 매우 느렸습니다. 테스트는 2번 반복되었습니다).

~ % echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  time raku -pe '/ ^ [ .*? B [A .*? B] ** 30 ] A /;'
BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA
raku -pe '/ ^ [ .*? B [A .*? B] ** 30 ] A /;'  49.44s user 0.41s system 100% cpu 49.791 total

~ % echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  time raku -pe '/ ^ [ .*? B [A .*? B] ** 30 ] A /;'
BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA
raku -pe '/ ^ [ .*? B [A .*? B] ** 30 ] A /;'  52.92s user 0.42s system 100% cpu 53.269 total

단일 :문자를 추가하여 Raku 속도를 대폭 향상합니다(로컬 역추적 방지, 2회 반복 테스트).

~ % echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  time raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'
BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA
raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'  0.22s user 0.04s system 138% cpu 0.185 total

~ % echo BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA |
  time raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'
BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BBBBBBBBBBBBBBBBBBBBBBBBBBBBA
raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'  0.21s user 0.04s system 139% cpu 0.177 total

Raku에는 역추적을 끄는 여러 가지 방법이 있습니다. 역추적은 :ratchet(또는) 부사를 사용하여 전체적으로 끌 수 있습니다 :r. 위 코드에서는 30Regex 엔진이 원자 인스턴스를 검색하는 위치에서 역추적이 로컬로 꺼집니다.

[A .*? B] ** 30 ~이 되다 [A .*? B] **: 30

최종적으로 가장 성능이 좋은 Raku 정규식(및 관련 참조)은 다음과 같습니다.

raku -pe '/ ^ [ .*? B [A .*? B] **: 30 ] A /;'

https://docs.raku.org/언어/regexes.html#Preventing_backtracking:_:
https://docs.raku.org/언어/regexes.html#Ratchet
https://docs.raku.org/언어/regexes.html

관련 정보