Le graphique est parlant, mais il prend un cas pathologique qui ne correspond pas à une regexp qui ait du sens. C'est rare de faire des recherches sur a?a?a?a?a?a?a?a?a.
Je m'étais un peu interessé à cette histoire de regexp via DFA qui serait plus rapide que les implementations usuelles à base de NFA après avoir lu la page de russ cox il y a quelques temps, j'avais même fait l'effort d'en implementer un pour finalement constater que ça allait notablement moins vite que pcre sur les classes de regexp "utiles". Au final on perd beaucoup de souplesse (bye bye les backreferences, et les {n} coutent chers puisqu'il faut ajouter n etats dans l'automate) pour gagner la garantie que le temps de calcul n'explosera pas exponentiellement dans des cas merdiques.
[^] # Re: comparatif graphique
Posté par Troy McClure (site web personnel) . En réponse à la dépêche Google libère la bibliothèque d'expressions rationnelles RE2. Évalué à 8.
Je m'étais un peu interessé à cette histoire de regexp via DFA qui serait plus rapide que les implementations usuelles à base de NFA après avoir lu la page de russ cox il y a quelques temps, j'avais même fait l'effort d'en implementer un pour finalement constater que ça allait notablement moins vite que pcre sur les classes de regexp "utiles". Au final on perd beaucoup de souplesse (bye bye les backreferences, et les {n} coutent chers puisqu'il faut ajouter n etats dans l'automate) pour gagner la garantie que le temps de calcul n'explosera pas exponentiellement dans des cas merdiques.