Les regexp, c'est bon, mangez-en
Par Laurentj le mardi, juin 24 2008, 21:37 - Technologies Web - Lien permanent
Sur son billet "utiliser les regex avec modération", Jérôme explique que substr est plus rapide qu'utiliser preg_match. Mon commentaire sur son billet n'est apparement pas encore passé[1], je me permet donc de répondre ici, car sa comparaison est faussée.
$extractedString = substr( $exampleString, 1, -1 );
n'est absolument pas équivalent à
preg_match( '#^\[(\w+)\]$#', $exampleString, $matches );
En effet, dans le premier cas, il n'y a aucune vérification que le premier caractère est bien [ et le dernier ], ni que la chaine à l'intérieur des crochets ne contient que des caractères alphanumérique, contrairement à ce qui se passe dans le deuxième cas avec l'expression régulière.
Aussi, pour avoir une comparaison équitable, il faudrait faire dans le premier cas, au moins ceci :
if(substr($exampleString, 0, 1) =='[' && substr($exampleString, -1) == ']')
$extractedString = substr( $exampleString, 1, -1 );
En conséquence, les résultats des temps d'exécution sont tout autre : le premier cas est de 2 à 5 fois plus long que l'usage de l'expression régulière. Et encore, là, je n'ai pas ajouté de vérification sur le contenu de $extractedString, pour s'assurer qu'il s'agit bien uniquement que de caractères alphanumériques (je vous laisse imaginer le code qu'il faudrait développer sans l'usage d'une expression régulière).
À la limite, l'expression régulière équivalente au premier cas, serait
preg_match( '#^.(.+).$#', $exampleString, $matches );
Et là, effectivement, preg_match est plus lent, mais c'est ici une mauvaise utilisation de preg_match. Pourquoi utiliser une expression régulière si on ne cherche pas à vérifier la syntaxe du contenu ?
Conclusion : n'hésitez pas à utiliser les expressions régulières [2] quand vous voulez extraire des données d'une chaîne et en même temps vérifier l'intégrité du contenu ;-).
Commentaires
Très bon article sur le fond, cependant je pense que tu te trompes sur le début : le pattern /^[(\w+)]$/ ne vérifie pas la présence de crochets en premier et dernier caractère. D'ailleurs, dans son "bench", le preg_match gauffre :-)
Pour s'en convaincre,
<?php echo (preg_match("#^[(\w+)]$#","[test]") ? "MATCH" : "DO NOT MATCH"); ?>
<?php echo (preg_match("#^\[(\w+)\]$#","[test]") ? "MATCH" : "DO NOT MATCH"); ?>
Sa regex est une abomination en elle-même, les crochets entourent des *classes*, les parenthèses assurent la *capture* (ou le regroupement d'alternatives ou les conditionnelles, j'en oublie peut-être). Et capturer ainsi à l'intérieur d'une classe dont on sait de toute façon qu'elle va catcher toute la chaine est complètement absurde, les classes ne sont pas faites pour ça du tout ! Je pense qu'il voulait échapper les crochets au départ. Ca ne change rien, mais ça en dit long sur la promptitude de l'auteur à accuser les regexp de lenteurs :-)
Sur la seconde partie de l'article, complètement OK. Il doit même y avoir moyen de tuner un peu la regex mais je doute que ça change la donne. Et la morale également, j'approuve, ce n'est pas pour ce genre d'usages que les regex sont pertinentes.
Oops, je suis aussi fatigué que vous, au final. "capturer ainsi à l'intérieur d'une classe dont on sait de toute façon qu'elle va catcher toute la chaine" est un non-sens, une classe ne peut catcher qu'un seul caractère a priori. Toutes mes excuses pour le double post, le reste de mon commentaire m'a l'air "cohérent".
Oui effectivement, la regexp est fausse, mais je pense que c'est à cause de dotclear qui a mangé l'anti-slash lors de l'édition :-) Je corrige également mon billet.
Cependant le résultat est le même au niveau des benchs.
Je crois que ce n'est même pas comparable. Quel est l'intérêt d'utiliser une regexp pour récupérer une partie de chaîne (comme dans l'exemple) ?
substr et preg_* n'ont pas les mêmes buts, alors bencher leur utilisation dans des cas ou l'un où l'autre ne convient pas ne sert à rien. Tout comme tirer des conclusions hâtives tel que preg_* est plus lent que substr parce que preg_* met plus de temps pour récupérer une partie de chaîne.
Pour faire un vrai bench il faut plus de cas d'utilisations, et dans beaucoup de ces cas on ne pourrait même pas utiliser substr...
Ce qui est triste, c'est que PHP est tellement lent que la solution optimale écrite en PHP est plus lente qu'une mauvaise solution écrite en C.
@laurentj: ça m'étonne un peu, les backslashes n'apparaissent pas non plus dans l'article original, mais si c'est juste une erreur de mise en forme des deux côtés mon commentaire est caduque :-)
@loufoque: je ne comprends pas bien le sens de ta remarque. Il faudrait écrire ses sites web nativement en C ? oO
@loufoque : franchement, ta remarque mérite explication, parce que là, ça ressemble à un troll gratuit de premier choix.
@pada : dans dotclear, en syntaxe wiki, l'anti-slash permet d'échapper les caractères wiki. Donc si tu met \[, ça va juste afficher [ au lieu d'interpreter le [ comme étant la syntaxe pour les liens en wiki. Donc il faut taper \\[ pour afficher "\[".
C'est pourtant simple: on va utiliser les fonctions preg_* lorsque coder soit même l'automate fini équivalent n'apporte pas d'avantage en terme de concision (pratiquement inéluctable) et de performance (C vs script). Dans l'exemple du billet, utiliser substr coule de source puisqu'on se contre balance d'exprimer une grammaire.
Justement, il n'est dit nulle part dans le billet en question que l'on se contrefout de la grammaire. Et comme son exemple est issue de son travail sur le parsing d'un fichier ini, alors utiliser substr ne coule absolument pas de source.
Mais dans un autre contexte, si on s'en fout de vérifier le contenu de la chaine, alors oui, substr est mieux, c'est son but, et il me semble l'avoir fait remarqué vers la fin de mon billet ;-)
Ceci dit je ne comprend toujours pas la remarque de loufoque, surtout quand il dit que "ce qui est triste", et qu'il semble dire que les regexp sont une mauvaise solution en C.
@Laurentj: Dans le cadre du benchmark présenté dans le billet, l'utilisation de substr... coule de source (pour moi hein;)! C'est ta même conclusion puisque tu démontres par ailleurs que les deux codes ne font pas la même chose. A la lecture du billet initial, j'ai plutôt l'impression qu'une grammaire n'intervient pas dans le problème. Il ne s'agirait que d'index à refiler à substr. Quand Jérôme écrit "Est-ce que j'en ai réellement besoin ?", je ne peux qu'approuver. En revanche, quand il dit "il est généralement plus intéressant d'utiliser la super fonction substr() qui est vraiment bien pratique, et ce en presque toutes occasions", là je ne suis plus d'accord (cf. mon 1er post).
Pour loufoque, je pense qu'il commente ton 3ième code d'exemple dans ton billet, là où il y a les "if".
En effet. Comme il est dit, ce code est "équivalent" à la regex, mais est moins performant. Pourtant, il devrait être bien plus performant, car l'analyse du motif de la regex et la génération d'un parser (non optimal, PCRE ne génère pas des automates), puis son application devrait prendre bien plus de temps.
Personnellement, je n'aime pas que le langage que j'utilise m'empêche d'écrire du code optimal ou aussi performant qu'il pourrait l'être, m'obligeant à devoir faire référence à des bouts écrits dans d'autres langages. De plus, il n'y a pas vraiment d'avantage à utiliser un langage "de script" (surtout un langage-jouet bidon comme PHP) par rapport à C++, par exemple, qui permet parfaitement de recoder une sémantique à la PHP ou Python avec une augmentation de performance non négligeable.
Aucun langage n'est optimal dans ce cas! Stroustrup en personne ne cesse de le répéter dans ses bouquins.
Cette remarque va à l'encontre de l'évolution des langages de programmation de cette dernière décennie. De nos jours, performances et espaces mémoire ne sont plus aussi prioritaires qu'avant, surtout dans le contexte d'internet.
Je ne vois pas en quoi le C++ ne permet pas de décrire de manière portable une opération sur la machine, tout en restant le plus optimal possible. Où Stroustrup dit-il cela ? Quoi qu'il en soit, ce n'est pas une référence.
Le niveau d'abstraction de C lui permet d'être indépendant de la machine en dessous. Tout ce qui lui manque, c'est les exceptions (disponibles en C++), les vecteurs, et un jeu d'instruction atomiques de base. En pratique, les vecteurs et les instructions atomiques sont fournis par les compilateurs, donc on peut pas faire mieux. On a même généralement un accès pour écrire de l'assembleur, au cas où on pense pouvoir faire mieux que le compilateur. Les compilateurs fonctionnent d'ailleurs assez souvent en interne avec une représentation intermédiaire C-like avec ces fonctionnalités supplémentaires.
Il y a tout un tas de domaines différents dans les langages de programmation. L'essor de PHP, Python, Java ou C# n'est qu'une part infime de cette évolution. Et d'ailleurs on voit ce que ça donne... une prolifération de programmes mal conçus, lents et gourmands, et l'arrivée de programmeurs extrêmement mauvais sur le marché.
Les vrais travaux pour les nouveaux langages de programmation, en fait, c'est le genre de trucs que tu vois sur lamba-the-ultimate.org. Des théoriciens qui font de la programmation fonctionnelle dont la sémantique fournit de nombreuses garanties grâce à un typage statique et d'importantes restrictions, mais qui restent des langages garbage collectés parce que contrôler le placement mémoire des objets pourrait amener à du code non sûr.
À côté de ça, y'a C++ qui évolue un peu à part, qui bénéficie déjà d'être implémenté par des compilateurs de qualité, et dont les capacités de programmation générique sont de plus en plus utilisées pour créer de hautes abstractions à hautes performances. Permettant alors de bénéficier à la fois des avantages de langages de haut niveau impératifs, objets et fonctionnels, et de la performance du C. La prochaine version arrive bientôt, solvant certains problèmes importants, ajoutant la déduction automatique, spécifiant le comportement d'un programme multithreadé, ajoutant du sucre pour faire des fonctions en ligne et utiliser du sous-typage structurel, et autres goodies.
Le C++ est selon moi le langage le plus intéressant, après, c'est mon avis personnel. Il souffre d'une mauvaise réputation à cause d'une base de code très importante écrite de manière inélégante, comme Mozilla, mais le C++ d'aujourd'hui est on ne peut plus moderne et permet de réaliser des choses dont les autres langages "populaires" sont incapables.
Par exemple sur son site perso : http://www.research.att.com/~bs/bs_faq.html#Others-do-compare où il dit, je cite : "After all, no language is better than every other in all possible ways."
Pour le reste de l'argumentation, évidemment il y a une part de vrai, mais il y a aussi un manque évident de pragmatisme et des oeillères qui m'empêchent personnellement de discuter plus avant. Bon trolling ;-)
@loufoque :
Je n'ai pas regardé le code utilisé dans ces fonctions preg_*, mais normalement, un algo de résolution de regexp est un algo de validation par dérivation, et donc il n'y a pas d'automate ou de génération de parser.
À part ça, franchement, comme dit pada, je crois que tu as des oeillères plus grosses que toi, qui t'empêche de voir la réalité des choses, et les avantages qu'apportent les langages de scripts.
Crois-tu que si PHP python et cie n'avaient pas existé, on en serait arrivé au web d'aujourd'hui, avec des millions de sites existants ?? (AH AH AH quand je repense à l'époque où on écrivait ces CGI en C, qui prenaient 10 fois plus de temps à coder que le truc équivalent en PHP !!) Et tu crois qu'en écrivant du code en C, on fait forcément du code plus propre ? Je te fais du code pourri en C et C++ quand tu veux, et même plus facilement qu'en PHP, avec des trous de sécurité, des fuites mémoires dans tout les sens, et des plantages du serveur web en deux lignes de code. Quand effectivement on voit certaine appli en PHP codée avec les pieds, je me dis qu'heureusement le développeur n'a pas pris un langage comme le C, ça aurait été catastrophique.
Oui, il y a du code pourri en PHP, mais il y a aussi des trucs bien foutus, et finalement, tout ces scripts pourris n'ont pas empeché des millions de sites de fonctionner. Le PHP et autres sont bien plus simple à utiliser, et tant mieux, ça a permis de démocratiser la programmation, et renvoyer dans leur grotte tout ces programmeux qui se croient des élites parce qu'ils codent en C + asm.
Aller, retourne donc dans ta grotte, continuer à t'auto-persuader qu'avec le C++, on peut faire plein de choses merveilleuses, de manière facile, propre et sécurisée.
J'adore le C et le C++, j'en fais tout les jours, mais contrairement à toi, je crois avoir plus de clairvoyance et de pragmatisme quant à l'usage des langages en fonction de ce que l'on veut faire.
@loufoque: Je lis lamba-the-ultimate.org régulièrement et ce qui me désole un peu, c'est de voir le nombre croissant de participants critiquer et délaisser le C++. Parce que, tu ne t'en doutes peut être pas, mais le C++ est mon langage préféré. Cela ne m'empêche pas, tout de même, de faire preuve d'un minimum de clairvoyance comme le dit Laurentj, à savoir qu'il y a des domaines où le C++ n'est vraiment pas un bon choix.
@Pada
On peut en C++, grâce à la technique des expression templates, définir n'importe quel langage de programmation au sein même de C++ (ce qu'on appelle un DSEL, Domain Specific Embedded Language).
Voir par exemple Boost.Proto, un DSEL pour définir des DSELs, FC++/Boost.Lambda/Boost.Phoenix recodant C++ à l'intérieur de C++ pour écrire des fonctions en ligne, Boost.Spirit qui génère un parser à partir d'une syntaxe EBNF-like qui est en fait une expression C++, Boost.ublas/Blitz++ pour le calcul sur vecteurs... C++ peut donc parfaitement se spécialiser dans un domaine particulier pour en obtenir la meilleure performance.
Après Stroustrup lui-même est loin d'être à la pointe de ce qui se fait en C++, donc ça m'étonnerait pas qu'il ne prenne pas ça en compte.
@Laurentj
Compiler le motif et générer un parser est plus performant que de faire l'analyse du motif à chaque fois.
Quoi qu'il en soit, c'est un problème NP-dur, c'est tout. Il faut faire du backtracking. Ça a donc une complexité exponentielle.
Bref, c'est tout sauf performant.
Prenons un exemple, comment tu vérifies (.*)\1 ? Faut tester tous les cas. C'est une grammaire sensible au contexte.
Pour ce qui est de C++, je parle du vrai C++ moderne, pas du C with classes ou C/C++ avec lequel tu travailles.
Ce sont des dialectes qui n'ont absolument rien à voir. Dans du C++, on peut écrire du code abstrait à haute performance, aussi facilement que du Python mais avec en plus une bien meilleure sûreté.
@quode
Il devrait tout de même y avoir un énergumène qui y parle un peu de C++, un certain Mathias Gaunard...