Pourquoi` s+ `est-il beaucoup plus rapide que` ss* ' dans ce regex Perl?

D'abord, même si le regex résultant ne garde pas la même signification, réduisons regexes à \s*0 et \s+0 et utilisons (" " x 4) . "_0" comme entrée. Pour les sceptiques, vous pouvez voir ici que le décalage est toujours présent.

considérons maintenant le code suivant:

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

creuser un peu avec use re debugcolor; nous obtenons la sortie suivante:

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 semble à être optimisé pour la défaillance . Il cherchera d'abord les chaînes constantes (qui ne consomment que O(N)). Ici, il cherchera 0 : Found floating substr "0" at offset 5...

puis il va commencer avec la variable partie de la regex, respectivly \s* et \s+ , contre la chaîne de minimum entier à vérifier:

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

après cela il cherchera la première position rencontrant le stclass exigence, ici à la position 0.

• \s*0 :
  • commence à 0, trouve 4 espaces puis échoue;
  • commence à 1, trouve 3 espaces puis échoue;
  • commence à 2, trouve 2 espaces puis échoue;
  • commence à 3, trouve 1 espaces puis échoue;
  • commence à 4, Trouver 0 espaces puis n'échoue pas ;
  • trouver un exact 0
• \s+0 :
  • commence à 0, trouve 4 espaces puis échoue. Comme le nombre minimum d'espaces ne correspond pas, le regex échoue instantanément.

si vous voulez vous amuser avec L'optimisation Perl regex, vous pouvez considérer les regexes suivants / *\n et / * \n . À première vue, ils ont la même apparence, la même signification... Mais si vous exécutez son contre (" " x 40000) . "_\n" le premier vérifiera toutes les possibilités tandis que le second cherchera " \n" et échouera immédiatement.

dans un moteur de regex vanille et non optimisé, les deux regex peuvent causer un retour en arrière catastrophique, puisqu'ils ont besoin de réessayer le modèle au fur et à mesure qu'il rebondit. Cependant, dans L'exemple ci-dessus, le second ne tombe pas en panne avec Perl car il a été optimisé pour find floating substr "0%n"

---

Vous pouvez voir un autre exemple sur le blog de Jeff Atwood .

noter également que la question ne concerne pas \s considération mais tout modèle où xx* est utilisé au lieu de x+ voir exemple avec 0s et aussi quantificateurs d'explosifs regex

avec un exemple aussi court le comportement est "findable", mais si vous commencez à jouer avec des modèles compliqués, il est loin d'être facile à repérer, par exemple: Expression régulière accroche le programme (utilisation 100% CPU)

le \s+\n exige que le caractère précédant le \n soit un SPACE .

selon use re qw(debug) la compilation établit qu'il a besoin d'une chaîne droite d'un nombre connu d'espaces, jusqu'à la sous-chaîne \n , qui est vérifiée en premier lieu dans l'entrée. Ensuite, il vérifie la sous-couche de longueur fixe de l'espace seulement par rapport à la partie restante de l'entrée, en cas de défaillance en ce qui concerne _ . C'est une seule possibilité de vérifier, indépendamment de la façon dont de nombreux espaces de l'entrée. (Lorsqu'il y a plus de _\n , chaque défaut est trouvé aussi directement, par sortie de débogage.)

L'a regardé de cette façon, c'est une optimisation que vous attendez presque, en utilisant un modèle de recherche plutôt spécifique et lucking out Avec cette entrée. Sauf en comparaison avec d'autres moteurs, qui ne font pas ce genre d'analyse.

Avec \s*\n ce n'est pas le cas. Une fois l' \n est trouvé et le caractère précédent n'est pas un espace, la recherche n'a pas échoué depuis \s* ne permet rien (zéro caractères). Il n'y a pas non plus de sous-chaînes de longueur fixe, et c'est dans le jeu de backtracking.

Je ne suis pas sûr des internes du moteur d'expression régulier, mais il semble qu'il ne reconnaît pas que \s+ est en quelque sorte le même que \s\s* , puisque dans le second il correspond à un espace, et tente ensuite de correspondre à un nombre toujours croissant d'espaces, tandis que dans le premier, il conclut immédiatement qu'il n'y a pas de correspondance.

la sortie utilisant use re qw( Debug ); le montre clairement, en utilisant un chaîne plus courte:

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";

Sortie

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"