Re:Fast request routing using regular expressions
by sjtgraham on Thursday February 20, 2014 @07:43AM
(#7270450)
You're confusing n size of route set, with k length of the path to be matched. With a trie the worst case running time to match a route grows O(log n) with an array of regexps it's O(n). The length of a path string to be matched is independent of how many routes are in the route set.
[ Parent
| on HN ]
Re:Fast request routing using regular expressions
by amalcon on Thursday February 20, 2014 @08:15AM
(#7270559)
In theory, the combined regex could be O(1) in the size of the route set.
Of course, in practice it's not. PCRE is backtracking-based rather than automaton-based, so increasing the complexity of the regex does have an effect on runtime.
Re:Fast request routing using regular expressions
by jerf on Thursday February 20, 2014 @01:22PM
(#7272572)
Which probably means we should be using a NFA-based engine for routing, rather than PCRE, because I don't think "don't backtrack" is a very serious restriction for routing. (Yes, of the hundreds of developers who may read this, one of them may have used backtracking in a routing expression. But in general I don't think it's that serious a restriction.)