Discussion :

[robinechuca]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

[wiztricks]

Salut,

Comment faire pour l'optimiser?

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

[flapili]

Est ce que le regex est obligatoire?
Si non une boucle avec try int except et voilà (int à un argument facultatif base)

[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.

[CosmoKnacki]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[fred1599]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

[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.

[wiztricks]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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.

[wiztricks]

Salut,

@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