4 ms·
The support of fancy features like backtracking does not cause any degradation of performance for simple regular expressions. You are not obliged to use them, b
by reacweb 11y ago
The support of fancy features like backtracking does not cause any degradation of performance for simple regular expressions. You are not obliged to use them, but they do not hurt you when you do not use them. Some other people may love them despite their poor complexity.
- thaumasiotes 11y agoActually, this is false. A lot of regex implementations use a backtracking approach in all cases, causing pathological behavior even on regexes which match a regular language (and so should never take any significant amount of time to process). See https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html, which gives a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (see the backtracking? me neither) as an example.
- reacweb 11y agoYou are right. The support of fancy features like backtracking should not cause any degradation of performance for simple regular expressions. You are not obliged to use them, but they should not hurt you when you do not use them. I am surprised this issue is not fixed in perl.
- lomnakkus 11y agoEDIT: Actually, nevermind. Does not matter in the grand scheme of things.
- mannykannot 11y ago> (see the backtracking? me neither) If I understand the article correctly, the Perl regex evaluator, if given a string consisting of only the minimum required number of 'a's, first matches them to the optional 'a's, and then has to backtrack to match the required 'a's.
- thaumasiotes 11y agoI misspoke a little. The point is that that expression doesn't use backreferences, and therefore doesn't need to use backtracking at all. The fact that it does use backtracking anyway is the focus of the complaint.
- cyphar 11y ago> The support of fancy features like backtracking does not cause any degradation of performance for simple regular expressions. Well, backtracking is how you implement your engine. So "simple" regular expressions that don't use any of the features backtracking provides (like backreferences) will cause exponential complexity, like: a?a?a?a?aaaa for a string "aaaa"