4 ms·
In my experience, the exponential time thing isn't really a big deal. I've used Perl regular expressions on a very regular basis for about 16 years now. Exponen
by flogic 10y ago
In my experience, the exponential time thing isn't really a big deal. I've used Perl regular expressions on a very regular basis for about 16 years now. Exponential time has been an issue only once. Obviously if I were accepting regular expressions from random people, I'd use RE2. But for my day to day purposes, it's pretty much a complete non issue.
- kbenson 10y ago> Obviously if I were accepting regular expressions from random people, I'd use RE2. And if you're using Perl, it's not hard to do so[1]. Pluggable regex engines FTW. :) 1: https://metacpan.org/pod/re::engine::RE2 https://metacpan.org/pod/re::engine::RE2
- kmike84 10y agore2 is not only about exponential time: matching of regexes like a|b|c is O(N) in backtracking engines and O(1) in DFA-based engines like re2. It can make a big difference in practice for generated regexes - e.g. if you want to check if an URL has one of the thousand substrings in it (think adblock-like use cases). With backtracking regex or with a loop it'd be O(N) regarding the number of options, but with DFA it is O(1) regarding the number of options. I've seen 1000x speedups for similar use cases with re2 vs re from Python stdlib.