2 ms·
It's small, but unfortunately due to how ? is implemented with recursive backtracking (look at how matchQuestion() tries both alternatives), has an exponential
by userbinator 9y ago
It's small, but unfortunately due to how ? is implemented with recursive backtracking (look at how matchQuestion() tries both alternatives), has an exponential worst-case runtime. Fortunately, the algorithm to do it in linear time is pretty simple too:
https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html (previously discussed at https://news.ycombinator.com/item?id=466845 https://news.ycombinator.com/item?id=466845)
- erickj 9y agoHere is the reference implementation for Russ Cox's work: https://github.com/google/re2 https://github.com/google/re2
- zoner14 9y agoI actually don't think this is the case (I definitely might be wrong). Although the matchQuestion function has the pattern that typically resembles a function of exponential runtime (where a function invokes itself recursively multiple times), there is a slight difference in our scenario. If you look at matchQuestion's invocations of match, you'll notice that on both sides of the OR, the pattern is stripped of two characters (the "_?"). This means that the recursive invocation of match will never invoke matchQuestion a second time, unless there is a second '?', in which case it's entirely appropriate.
- userbinator 9y agounless there is a second '?', in which case it's entirely appropriate. That's precisely where the exponential behaviour comes from; consider e.g. matching the pattern "a?a?a?aaa" against "aaa". It will try matching "a?" against the first "a", which succeeds, leading to a recursive call to match "a?a?aaa" with "aa". That eventually fails, so it tries matching "a?a?aaa" against "aaa"; and inside those two branches, it also splits into two depending on whether to match the "a?", etc. The result is, for each "a?" and "a" added, the total amount of work involved in matching doubles, so it is exponential.