News for hackers. Stuff that matters.
Re:Fast request routing using regular expressions by skj on Thursday February 20, 2014 @07:37AM (#7270424)
Or, O(n^2) vs O(n log n).
Re:Fast request routing using regular expressions by skj on Thursday February 20, 2014 @07:40AM (#7270433)
Now that I read the article, seems like they're merging all the regexps into one, which really could be O(n). However, the trie will not be O(log n). You have to at least look at every character in the input, so there's a hard O(n) lower bound.
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.
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.)
Re:Fast request routing using regular expressions by sjtgraham on Thursday February 20, 2014 @07:44AM (#7270455)
No