en ce qui concerne regex (spécifiquement python re), si nous ignorons la façon dont l'expression est écrite, la longueur du texte est-elle le seul facteur pour le temps requis pour traiter le document? Ou y a-t-il d'autres facteurs (comme la structure du texte) qui jouent aussi des rôles importants?python regex speed
La longueur du texte et son contenu sont tous deux importants.
À titre d'exemple, l'expression régulière a+b ne trouve plus rapidement sur une chaîne contenant un million b s mais plus lentement sur une chaîne contenant un million a s. C'est parce que plus de retour en arrière sera nécessaire dans le second cas.
import timeit
x = "re.search('a+b', s)"
print timeit.timeit(x, "import re;s='a'*10000", number=10)
print timeit.timeit(x, "import re;s='b'*10000", number=10)
Résultats:
6.85791902323
0.00795443275612
Une considération importante peut également être si le texte correspond effectivement à l'expression régulière. Prenez (comme un exemple artificiel) la regex (x+x+)+y de this regex tutorial.
Lorsqu'il est appliqué à xxxxxxxxxxy, il correspond, en prenant le moteur regex 7 étapes. Lorsqu'il est appliqué à xxxxxxxxxx, il échoue (bien sûr), mais il faut 2558 étapes du moteur pour arriver à cette conclusion.
Pour xxxxxxxxxxxxxxy contre xxxxxxxxxxxxxx il est déjà 7 vs 40958 étapes, et ainsi de suite de façon exponentielle ...
Cela se produit surtout facilement avec des répétitions imbriquées ou regexes où le même texte peut être égalée par deux ou plusieurs parties différentes de l'expression régulière, forçant le moteur à essayer toutes les permutations avant de pouvoir déclarer l'échec. Ceci est alors appelé backtracking catastrophique.
''regexp' dans le titre et existe ('Mark Byers')' => 'True'. – OTZ
sont de longs mots qui se répètent dans le texte tels que «spam spam spam ....» significatif? Mon regex cherche essentiellement des onglets et les remplace par des espaces str = re.sub ("\ t", "", str) mais pour ce morceau de texte particulier, cela semble pour toujours. D'après votre réponse, dans mon cas, cela ne devrait pas avoir d'importance. – goh
@goh: Pour cette expression régulière particulière, cela ne fera aucune différence. Cette expression régulière est très simple, donc il n'y a pas beaucoup de retour en arrière. –