Hacker News Reader

Comment by sjtgraham | Hacker News Reader

Are regular expressions are good choice for routing? A trie seems like a better choice than a sequence of regexps. O(n) vs O(log n).

View on HN

It depends on your regex engine. The author here is concatenating all of the paths into a single pattern, an automata based engine would ideally compile away the disjunction and offer performance linear with the input path length.

It's funny that people are coming up with these libraries while comparing performance to the Symfony routing component, yet Symfony does exactly what you describe (dumping the routes to more or less a trie structure) if you activate caching, which is done in the standard framework distribution.

Not that I'm slagging off their efforts, in fact I plan to use FastRoute in one of my projects.

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. -- Jamie Zawinski in 1997

Or, O(n^2) vs O(n log n).

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.

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.

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.

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.)

Reply on news.ycombinator.com