regex compléxité, optimisation

Version imprimable

Bonjour, j'ai écrit la regex suivante pour reconnaître un nombre en python:
Code:

1 2 3 model = r"((?:0b(?:[01]+(?:_[01]+)*)+)|(?:0o(?:[0-7]+(?:_[0-7]+)*)+)|(?:0x(?:[0-9a-fA-F]+(?:_[0-9a-fA-F]+)*)+)|(?:(?:\.(?:[0-9]+(?:_[0-9]+)*)+)|(?:(?:[0-9]+(?:_[0-9]+)*)+\.(?:[0-9]+(?:_[0-9]+)*)*))(?:e[\+\-]?(?:[0-9]+(?:_[0-9]+)*)+)*|(?:(?:[0-9]+(?:_[0-9]+)*)+(?:e[\+\-]?(?:[0-9]+(?:_[0-9]+)*)+)*))j?" recherche = re.match(model, chaine[start_rank:].lower())
Cela fonctionne très bien sauf pour des nombres grand, par exemple 121623452345213467809856784, met une dizaine de secondes à être compris...
Il suffit de rajouter une décimal, et là le temps n'est plus acceptable!

Comment faire pour l'optimiser? 8O

10/01/2020, 19h28
wiztricks

Salut,

Citation:

Envoyé par robinechuca

Comment faire pour l'optimiser? 8O

Faire une seule regex pour parser un nombre qu'il soit binaire, octal, hexadécimal ou décimal, çà fait juste un pattern illisible où vous allez devoir encoder des conditions, mettre des lookahead.

Déjà si vous testiez les deux premiers caractères pour trouver la base puis faire bosser int serait plus de la programmation Python (que l'optimisation de pattern de regexp qui n'a rien de trop spécifique à Python).

- W
10/01/2020, 22h17
flapili

Est ce que le regex est obligatoire?
Si non une boucle avec try int except et voilà (int à un argument facultatif base)
11/01/2020, 15h31
disedorgue

Tu es sur que ta regex peut différencier tous les cas, comme par exemple "0x123450b111000" ?
Ici, c'est que de l'hexa ou une partie hexa et une partie binaire ?
Ce qui nous manque ici, c'est un sample pour savoir ce que peut contenir une chaine en entrée.

D'une manière générale et quelque soit le langage, une optimisation de regex se fait en connaissant la forme de la chaine que l'on parse.

Dans l'état actuelle des choses, ta pattern est illisible. On va donc commencer par utiliser le flag re.VERBOSE qui permet d'ignorer les espacements et d'ajouter des commentaires inline tout en indentant pour faire apparaître la structure de la pattern. Je vais utiliser la méthode re.compile non pas pour influer sur les performances (car ça ne change rien), mais juste pour que la pattern et les flags soient au même endroit:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 pat = re.compile(r''' ( # binary (?:0b(?:[01]+(?:_[01]+)*)+) | # octal (?:0o(?:[0-7]+(?:_[0-7]+)*)+) | # hexadecimal (?:0x(?:[0-9a-fA-F]+(?:_[0-9a-fA-F]+)*)+) | # decimal (?: (?:\.(?:[0-9]+(?:_[0-9]+)*)+) | (?:(?:[0-9]+(?:_[0-9]+)*)+\.(?:[0-9]+(?:_[0-9]+)*)*) ) # exponant (optional) (?:e[\+\-]?(?:[0-9]+(?:_[0-9]+)*)+)* | # integer (?: (?:[0-9]+(?:_[0-9]+)*)+ # exponant (optional) (?:e[\+\-]?(?:[0-9]+(?:_[0-9]+)*)+)* ) )j?''', re.VERBOSE)
Ensuite on enlève ce qui est inutile dont des groupes, des échappements qui n'ont pas lieu d'être, les lettres majuscules:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 pat = re.compile(r''' ( # binary 0b (?: [01]+ (?:_[01]+)* )+ | # octal 0o (?: [0-7]+ (?:_[0-7]+)* )+ | # hexadecimal 0x (?: [0-9a-f]+ (?:_[0-9a-f]+)* )+ | # decimal (?: \. (?: [0-9]+ (?:_[0-9]+)* )+ | (?: [0-9]+ (?:_[0-9]+)* )+ \. (?: [0-9]+ (?:_[0-9]+)* )* ) # exponant (optional) (?: e [+-]? (?: [0-9]+ (?:_[0-9]+)* )+ )* | # integer (?: [0-9]+ (?:_[0-9]+)* )+ # exponant (optional) (?: e[+-]? (?: [0-9]+ (?:_[0-9]+)* )+ )* )j?''', re.VERBOSE)
On y voit déjà plus clair, et c'est là qu'on remarque qu'il y a des constructions bizarres répétées un peu partout avec un mésusage des quantificateurs + (1 ou plus) et * (0 ou plus). Prenons par exemple la première branche, celle des nombres binaires: 0b (?: [01]+ (?:_[01]+)* )+
Tu utilises le groupe répété (?: ... )+ pour t'assurer qu'il y a au moins un chiffre après le b. C'est inutile, [01]+ le garantit déjà. Donc on peut supprimer ce groupe répété et écrire simplement 0b [01]+ (?:_[01]+)*
C'est cette construction qui est la principale cause de la lenteur de ta pattern, car elle s'apparente à la pattern pathologique (a*)*b (qui en l'absence de b va essayer tous les découpages possibles et imaginables du groupe répété avant d'échouer). (Faire des recherches sur le mécanisme de Backtracking).

Même type d'erreur pour la partie décimale des nombres ou l'exposant qui sont optionnels avec (?: ... )*. * signifie 0 ou plus, or tu ne vas pas répéter une partie décimale ou un exposant 25 fois! Le quantificateur approprié est plutôt ? (0 ou 1) ou encore {0,1}:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 pat = re.compile(r''' ( # binary 0b [01]+ (?:_[01]+)* | # octal 0o [0-7]+ (?:_[0-7]+)* | # hexadecimal 0x [0-9a-f]+ (?:_[0-9a-f]+)* | # decimal (?: \. [0-9]+ (?:_[0-9]+)* | [0-9]+ (?:_[0-9]+)* \. (?: [0-9]+ (?:_[0-9]+)* )? ) # exponant (optional) (?: e [+-]? [0-9]+ (?:_[0-9]+)* )? | # integer [0-9]+ (?:_[0-9]+)* # exponant (optional) (?: e [+-]? [0-9]+ (?:_[0-9]+)* )? )j?''', re.VERBOSE)
Occupons-nous maintenant des branches.

Tu as trois branches (entiers et nombres décimaux mis à part) qui commencent toutes par un 0. Dans l'état actuel de ta pattern ça signifie que si la chaîne ne commence pas par 0, ces trois branches vont échouer et le 0 sera testé 3 fois pour rien. En mettant ce 0 en facteur on réduit le nombre d'échecs à 1.

Idem avec les décimaux et les entiers, en rendant la partie décimale optionnelle, on peut se passer de la branche des entiers.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 pat = re.compile(r''' ( 0 (?: # binary b [01]+ (?:_[01]+)* | # octal o [0-7]+ (?:_[0-7]+)* | # hexadecimal x [0-9a-f]+ (?:_[0-9a-f]+)* ) | # decimal (?: \. [0-9]+ (?:_[0-9]+)* | [0-9]+ (?:_[0-9]+)* (?: \. (?: [0-9]+ (?:_[0-9]+)* )? )? ) # exponant (?: e [+-]? [0-9]+ (?:_[0-9]+)* )? )j?''', re.VERBOSE)
Avec ces factorisations on fait passer le nombre de points d'entrée de 6 à 3. À contrario, une factorisation après plusieurs branches, si elle réduit la taille de la pattern, ne change pas le nombre de points d'entrée, comme c'est le cas avec l'exposant. On peut le distribuer pour gagner un niveau d'imbrication:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 pat = re.compile(r''' ( # binary octal hexadecimal 0 (?: b [01]+ (?:_[01]+)* | o [0-7]+ (?:_[0-7]+)* | x [0-9a-f]+ (?:_[0-9a-f]+)* ) | # decimal \. [0-9]+ (?:_[0-9]+)* (?: e [+-]? [0-9]+ (?:_[0-9]+)* )? | [0-9]+ (?:_[0-9]+)* \.? (?: [0-9]+ (?:_[0-9]+)* )? (?: e [+-]? [0-9]+ (?:_[0-9]+)* )? )j?''', re.VERBOSE) recherche = pat.match(chaine[start_rank:].lower())
Voilà qui devrait réduire considérablement le temps d'exécution de la pattern et la rendre lisible. Néanmoins, mon petit doigt me dit qu'elle ne doit pas être seule en cause.

NB: si tu choisis d'utiliser re.compile comme dans l'exemple, assures-toi que celui-ci n'est exécuté qu'une seule fois pour tout le script (donc pas dans une boucle ni dans une fonction). Dans le cas contraire, n'oublie pas de passer le flag re.VERBOSE en paramètre de re.match.

Citation:
Envoyé par robinechuca
Bonjour, j'ai écrit la regex suivante pour reconnaître un nombre en python:
Code:

1 2 3 model = r"((?:0b(?:[01]+(?:_[01]+)*)+)|(?:0o(?:[0-7]+(?:_[0-7]+)*)+)|(?:0x(?:[0-9a-fA-F]+(?:_[0-9a-fA-F]+)*)+)|(?:(?:\.(?:[0-9]+(?:_[0-9]+)*)+)|(?:(?:[0-9]+(?:_[0-9]+)*)+\.(?:[0-9]+(?:_[0-9]+)*)*))(?:e[\+\-]?(?:[0-9]+(?:_[0-9]+)*)+)*|(?:(?:[0-9]+(?:_[0-9]+)*)+(?:e[\+\-]?(?:[0-9]+(?:_[0-9]+)*)+)*))j?" recherche = re.match(model, chaine[start_rank:].lower())
Cela fonctionne très bien sauf pour des nombres grand, par exemple 121623452345213467809856784, met une dizaine de secondes à être compris...
Bonjour,

Peut-on avoir l'ensemble des tests ?

Merci de définir un peu plus le contexte, d'où vient chaîne ? Ont-elles été traitées préalablement par d'autres outils, fonctions, etc... ?

C'est beaucoup trop flou pour rendre quelque chose de générique, d'ailleurs ce qui serait intéressant, c'est que ça ne réponde qu'aux tests que vous avez défini avant de coder.

@CosmoKnacki

+1 pour le taf !

12/01/2020, 08h31
tyrtamos

Bonjour,

@CosmoKnacki => bravo pour le boulot! Je trouve aussi que "re.VERBOSE" est pratique, voire indispensable, pour mettre au point les motifs regex complexes.

Salut,

@CosmoKnacki: jolie démonstration. Il faut juste ajouter des ^ et des $ pour que çà ne matche pas des "0b1012". En Python, çà pourrait s'écrire:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 def is_number(s): bases = { '0b':2, '0o':8, '0x':16 } if (base := bases.get(s[:2])): f = lambda: int(s[2:], base) else: f = lambda: (float if '.' in n else int)(s) try: f() except: return False return True
un poil moins rapide (çà fabrique un entier ou un float pour le jeter).

- W

14/01/2020, 12h56
CosmoKnacki

@tyrtamos: C'est pareil et plus ça va plus j'ai tendance à l'utiliser même sur des patterns courtes. À noter que c'est devenu le mode par défaut en Perl 6.

@Wiztricks: Je ne l'ai pas ajouté car je ne sais pas trop ce qu'il veut en faire (validation ou extraction) et parce que la pattern est déjà ancrée au début (utilisation de la méthode re.match sur une sous-chaîne) et a un groupe de capture (ce qui me fait plutôt pencher vers une extraction).
S'il s'agit d'une validation de chaîne complète il faut utiliser re.fullmatch (si disponible) ou juste ajouter l'ancre de fin $ à la pattern, dans tous les cas l'ancre de début de chaîne est inutile.
14/01/2020, 13h38
wiztricks

Salut,

Citation:

Envoyé par CosmoKnacki

@Wiztricks: Je ne l'ai pas ajouté car je ne sais pas trop ce qu'il veut en faire (validation ou extraction) et parce que la pattern est déjà ancrée au début (utilisation de la méthode re.match sur une sous-chaîne) et a un groupe de capture (ce qui me fait plutôt pencher vers une extraction).

Moi je dis çà parce que j'ai "testé" avant de mesurer les performances des 2 moutures et que j'ai eu cette surprise...

- W
14/01/2020, 22h46
robinechuca

Merci beaucoup, vos réponses m'ont beaucoup appris :ccool:

La mise en contexte, c'est pour faire un code qui "comprend" le python, et donc qui soit capable d'identifier des éléments de syntaxe.
Je pense qu'un code est plus parlant qu'une grande explication:
https://framagit.org/robinechuca/rai...er/pyreader.py
plus particulièrement dans def jump(self,...) vers la ligne 1780 pour l’exemple du sujet de la discutions.

Si vous y voyez d'autres abérations, n'hésitez pas à critiquer, je suis preneur de tout!

Robin RICHARD

Comme promis, me voila de retour!

j'ai enlevé le ".lower()" et j'ai rajouté à la place l'attribut re.IGNORECASE.

voila ce que ça donne:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
>>> import regex as re
>>> model = re.compile(r"""^\s*
...                       (?P<flotant>
...                       \. [0-9]+ (?:_[0-9]+)*
...                       (?: e [+-]? [0-9]+ (?:_[0-9]+)* )?
...                     | [0-9]+ (?:_[0-9]+)* \.? (?: [0-9]+ (?:_[0-9]+)* )?
...                       (?: e [+-]? [0-9]+ (?:_[0-9]+)* )?
...                       )
...                     \s*$""", re.VERBOSE, re.IGNORECASE)
>>> re.fullmatch(model, "1e1")
<regex.Match object; span=(0, 3), match='1e1'>
>>> re.fullmatch(model, "1E1")
>>>

Bref ça prend en compte la case, pourquoi?

19/01/2020, 00h55
CosmoKnacki

Parce qu'entre deux flags on met un pipe | pas une virgule. Il y a 2 t à flottant
19/01/2020, 08h21
robinechuca
Merci, ça fonctionne mieux tout a coup!
Curieusement, la fonction "compile" du module regex n'a pas la même entête que celle du module re.
Code:

1 2 3 4 5 6 7 >>> import re >>> help(re.compile) compile(pattern, flags=0) >>> import regex >>> help(regex.compile) compile(pattern, flags=0, ignore_unused=False, **kwargs)
J'ai cherché sur internet un comparatif des 2 modules et je n'ai rien trouvé. Mis a part que certaines entêtes sont différentes, il y a t-il des différence en terme de performance?
19/01/2020, 17h14
CosmoKnacki

Citation:

il y a t-il des différences en terme de performance?

La plupart du temps le module pypi/regex est plus rapide pour une même pattern sur la même chaîne, parce que son auteur c'est fait un point d'honneur à combler les faiblesses du module re, mais il n'y a pas de différences fondamentales entre les deux modules, ce sont tous les deux des moteurs à backtracking, ce qui signifie que le temps d'exécution suit une courbe exponentielle.
Bien que les moteurs de regex actuels de ce type soient agrémentés d'optimisations, il revient donc au programmeur à faire en sorte d'éviter les situations critiques, en d'autres termes, le programmeur ne peut pas toujours se contenter de décrire ce qu'il cherche, il doit aussi anticiper la manière dont le moteur va s'y prendre, pour rester dans la partie acceptable en temps d'exécution de la courbe exponentielle.
L'intérêt du module pypi/regex est de proposer des fonctionnalités qui manquent au module re. Si certaines sont justes des fonctionnalités "de confort", d'autres au contraire permettent de composer des patterns plus efficaces (comme les groupes atomiques, les quantificateurs possessifs, les verbes de contrôle du backtracking). La stratégie générale de composition des patterns avec ce genre de moteurs est de faire en sorte que l'échec de la pattern soit rapide.

Autre type de moteur disponible sous Python: pyre2.
Là le fonctionnement est différent et le temps d'exécution évolue de manière linéaire. L'utilisateur n'a pas trop à se soucier de comment il écrit sa pattern (dans la mesure où celle-ci représente bien ce qu'il recherche). Par contre, ce type de moteur propose en comparaison très peu de fonctionnalités (adieu les quantificateurs paresseux, les lookarounds, ...), et impose sa propre loi: c'est la plus grande correspondance qui gagne. (alors que pour les précédents c'est la première alternative qui réussie).
Ce type de moteur est idéal pour les recherches sur de très longues chaînes. (C'est notamment ce qu'utilisent les utilitaires comme grep, awk, sed ou le sgbd MySQL).

Maintenant je ne sais pas exactement ce que tu mijotes avec ton script, mais peut-être qu'il serait préférable que tu jettes un œil au module ast.
19/01/2020, 18h44
robinechuca

Je tiens à tous vous remercier, vous m'avez beaucoup appris et fait bien avancer sur les expressions régulières! ;)