Après avoir lu sur RE / NFA et DFA, il semble que la recherche d'une sous-chaîne au sein d'une chaîne pourrait réellement être asymptotiquement plus rapidement à l'aide d'un re plutôt que d'une force brute O (mn). Mon raisonnement est qu'un DFA maintiendrait réellement l'état et éviterait de traiter chaque caractère dans la "foin" plus d'une fois. Par conséquent, les recherches dans de longues chaînes peuvent réellement être beaucoup plus rapides si elles sont effectuées avec des expressions régulières.
Bien sûr, ceci est valable uniquement pour les matchers de la NFA en DFA.
Quelqu'un a-t-il eu une meilleure performance des chaînes dans la vie réelle lorsque vous utilisez Re plutôt qu'un correspondeur de force brute?
3 Réponses :
Si vous examinez la documentation pour la plupart des langues, cela mentionnera que si vous n'avez pas besoin de pouvoir le pouvoir de Regex, vous devez utiliser la version non-REGEX pour des raisons de performance ... Exemple: http://www.php.net/manual/fr/function.preg-split.php états: "Si vous n'avez pas besoin de la puissance des expressions régulières, vous pouvez choisir des alternatives plus rapides (bien que simples) telles que exploser () ou Str_split ()."
Ceci est un compromis qui existe partout. C'est la solution la plus flexible et la plus riche, une solution est la plus faible de ses performances.
Les expressions les plus régulières utilisées dans la pratique sont PCRE (expressions régulières compatibles Perl), qui sont plus larges que la langue normale et ne peuvent donc pas être exprimées avec une grammaire régulière. PCRE a des choses comme des assertions positives / négatives de regards / regards à la recherche et même de récursivité, de sorte que l'analyse peut nécessiter de traiter certains caractères plus d'une fois. Tout résulter de la mise en œuvre particulière: s'il est optimisé si les expressions restent dans les limites de la grammaire ordinaire ou non.
Personnellement, je n'ai pas fait de comparaisons de performances entre les deux. Cependant, dans mon expérience, je n'ai jamais eu de problèmes de performance avec la force brute de trouver et de remplacer, alors que je devais faire face à des goulots d'étranglement de la performance à plus d'une occasion.
Oui, convenu. J'étais plus préoccupé par la correspondance d'une sous-chaîne avec une nouvelle (/ sieste /). Et oui, il faudrait être en C parce que je suppose que c'est la seule langue dont le moteur convertit vers la DFA.
Tout d'abord, je vous recommanderais de lire l'article sur les internes d'expressions régulières en plusieurs langues: La correspondance d'expression régulière peut être simple et rapide .
Parce que Regexps dans de nombreuses langues ne correspond pas uniquement à la correspondance, mais également à la possibilité de capturer le groupe et de référencement de retour, presque toutes les implémentations utilisent appelé "retour à l'arrière" lors de l'exécution de la NFA construite à partir de la REGEXP donnée. Et cette mise en œuvre a une complexité de temps exponentielle (dans le pire des cas).
Il pourrait y avoir une mise en œuvre à travers la DFA (avec capture de groupe), mais elle a une surcharge (voir le papier de Laurikari NFA avec des transitions marquées, leur conversion vers des automates déterministes et une application à des expressions régulières ).
Pour une simple recherche de sous-chaînes Vous pouvez utiliser Knuth- Morris-Pratt Algorithme, qui construit DFA pour rechercher la sous-chaîne, et il a une complexité optimale O (Len (s)). Mais cela a également dépassé les frais généraux, et si vous testez une approche naïve (O (NM)) contre cet algorithme optimal sur des mots et des phrases du monde réel (qui ne sont pas si répétitifs), vous pouvez trouver que l'approche naïve est meilleure en moyenne.
Pour la recherche exacte de la recherche Vous pouvez également essayer Boyer-Moore Algo, qui a la complexité du pire des cas O (mn), mais travaillait mieux que KMP en moyenne sur des données du monde réel.
Boyer-moore est o (n) ; Cela ne nécessite jamais plus que les comparaisons 3n . Le plus simple Boyer-Moore-Horspool peut nécessiter jusqu'à Mn , mais ce n'est pas le "même" algorithme.