لماذا هو \ '+ أسرع بكثير من `\ s \ s*` في هذا Perl regex؟




regex-greedy (3)

لماذا يؤدي استبدال \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 regex البطيء في التعليمات البرمجية الخاصة بي - عند إعطاء ملف إدخال بحجم 450 كيلوبايت يتكون من الكثير من المساحات مع وجود عدد قليل من المساحات هنا وهناك وهناك سطر جديد نهائي على النهاية - معلقة ريكس ولم تنته.

لقد استبدلت بشكل بديهي regex بـ s/\s+\n/\n/g; s/\n\s+/\n/g; 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+ سيفشل على الفور في regex (بدون تشغيله) إذا لم يكن هناك سطر جديد. أظن أنه يستخدم موقع السطر الجديد لتقليل حجم البحث الذي يقوم به. بالنسبة لجميع الحالات المذكورة أعلاه ، يبدو أنه يقلل بذكاء من التراجع المتداخل (عادة /\s*\n/ مقابل سلسلة من المساحات سيستغرق وقتًا أسيًا). هل يمكن لأي شخص أن يقدم نظرة ثاقبة لماذا إصدار \s+ أسرع بكثير؟

لاحظ أيضًا أن \s*? لا تقدم أي تسريع.


أولاً ، حتى إذا لم يحتفظ regex الناتج بالمعنى نفسه ، فلنقلّ من regexes إلى \s*0 و \s+0 ونستخدم (" " x 4) . "_0" (" " x 4) . "_0" كمدخل. بالنسبة للمتشككين ، يمكنك أن ترى here أن الفجوة ما زالت قائمة.

الآن لننظر في الكود التالي:

$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

يبدو أن بيرل هو الأمثل للفشل . سيبحث أولاً عن سلاسل ثابتة (التي تستهلك فقط O (N)). هنا ، سيبحث عن 0 : Found floating substr "0" at offset 5...

بعد ذلك سيبدأ بالجزء المتغير من regex ، 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 عن الموضع الأول الذي stclass متطلبات الفئة ، هنا في الموضع 0.

  • \s*0 :
    • يبدأ من 0 ، ابحث عن 4 مسافات ثم تفشل ؛
    • يبدأ من 1 ، ابحث عن 3 مسافات ثم تفشل ؛
    • يبدأ في 2 ، والعثور على 2 مسافات ثم تفشل.
    • يبدأ في 3 ، والعثور على 1 مسافات ثم تفشل.
    • يبدأ في 4 ، والعثور على 0 مسافات ثم لا تفشل ؛
    • العثور على 0 بالضبط
  • \s+0 :
    • يبدأ من 0 ، ابحث عن 4 مسافات ثم أخفق. نظرًا لعدم مطابقة الحد الأدنى لعدد المسافات ، تفشل عملية إعادة التسجيل على الفور.

إذا كنت ترغب في الاستمتاع بتحسين Perl regex ، فيمكنك التفكير في regexes التالية / *\n و / * \n . للوهلة الأولى ، يبدوان متشابهين ، لهما نفس المعنى ... ولكن إذا واجهته (" " x 40000) . "_\n" (" " x 40000) . "_\n" أول واحد سوف يتحقق من كل الاحتمالات بينما الثاني سوف يبحث عن " \n" وسيفشل على الفور.

في محرك regex الفانيليا غير المُحسّن ، يمكن أن يتسبب كلا regex في التراجع الكارثي ، حيث إنهما يحتاجان إلى إعادة محاولة محاكاة النمط لأنه يتعثر. ومع ذلك ، في المثال أعلاه ، لا يفشل الثاني مع Perl لأنه تم تحسينه find floating substr "0%n"

يمكنك مشاهدة مثال آخر على مدونة Jeff Atwood .

لاحظ أيضًا أن المشكلة لا تتعلق بالبحث ولكن أي نمط يتم فيه استخدام xx* بدلاً من x+ راجع المثال مع 0s وأيضًا إعادة استخدام الكميات المتفجرة

بمثل هذا المثال الأقصر ، يكون السلوك "قابلاً للاكتشاف" ، لكن إذا بدأت باللعب بأنماط معقدة ، فليس من السهل تحديد موقعه ، على سبيل المثال: برنامج تعليق التعبير العادي (استخدام وحدة المعالجة المركزية بنسبة 100٪)


عندما يكون هناك عقدة "زائد" (على سبيل المثال \s+ ) في بداية النموذج وتفشل العقدة في التطابق ، يتخطى مشغل regex للأمام إلى نقطة الفشل ويحاول مرة أخرى ؛ مع \s* ، من ناحية أخرى ، يتقدم المحرك حرفًا واحدًا في كل مرة.

يشرح إيف أورتن هذا التحسين بشكل جيد here :

يشتمل تحسين فئة البداية على وضعين ، "حاول كل موضع بدء صالح" (doevery) و "flip flop mode" (! doevery) حيث تحاول فقط وضع البداية الصالحة الأول في تسلسل.

ضع في اعتبارك / (\ d +) X / والسلسلة "123456Y" ، والآن نعلم أننا إذا فشلنا في مطابقة X بعد مطابقة "123456" ، فسوف نفشل أيضًا في المطابقة بعد "23456" (على افتراض عدم وجود حيل شريرة ، التي تعطل التحسين على أي حال) ، لذلك نحن نعرف أننا يمكن أن نتخطى إلى الأمام حتى الشيك / فشل / وعندها فقط البدء في البحث عن تطابق حقيقي. هذا هو وضع التقليب.

/\s+/ مشغلات وضع التقليب ؛ /\s*/ ، /\s\s*/ ، و /\s\s+/ لا. لا يمكن تطبيق هذا التحسين على العقد "النجمية" مثل \s* لأنها يمكن أن تتطابق مع أحرف صفرية ، وبالتالي فإن الفشل في نقطة واحدة في تسلسل لا يشير إلى الفشل لاحقًا في نفس التسلسل.

يمكنك رؤية ذلك في إخراج التصحيح لكل regex. لقد أبرزت الأحرف التي تم تخطيها بـ ^ . قارن هذا (يتخطى أربعة أحرف في المرة الواحدة):

$ 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-porters عما إذا كان أي منهما يستحق هذا الجهد.

في حالة اهتمامك ، يتم تمكين "وضع التقليب" عن طريق تعيين علامة PREGf_SKIP على regex عندما يتم تجميعها. راجع الكود حول الأسطر 7344 و 7405 في regcomp.c والخط 1585 في regexec.c في مصدر 5.24.0.


يتطلب \s+\n أن الحرف الذي يسبق \n هو SPACE .

وفقًا use re qw(debug) البرمجي أنه يحتاج إلى سلسلة مستقيمة من عدد معروف من المسافات ، حتى السلسلة الفرعية \n ، والتي يتم التحقق منها أولاً في الإدخال. ثم يقوم بالتحقق من السلسلة الفرعية ذات الطول الثابت فقط مقابل الجزء المتبقي من الإدخال ، مع فشله في ذلك. إنها إمكانية واحدة للتحقق ، بغض النظر عن عدد المساحات التي يحتوي عليها الإدخال. (عندما يكون هناك عدد أكبر من _\n تم العثور على فشل كل على قدم المساواة بشكل مباشر ، لكل إخراج تصحيح.)

نظرنا إليه بهذه الطريقة ، إنه تحسين تتوقعه تقريبًا ، ويستخدم نمط بحث محددًا إلى حد ما ويحظي بهذا الإدخال. باستثناء عند مقارنتها بمحركات أخرى ، من الواضح أنها لا تفعل هذا النوع من التحليل.

مع \s*\n هذا ليس هو الحال. بمجرد العثور على \n والحرف السابق ليس مسافة ، لم يفشل البحث لأن \s* لا يسمح بأي شيء (صفر أحرف). لا توجد سلاسل فرعية ذات طول ثابت أيضًا ، وهي في لعبة التراجع.





regex-greedy