5 ms·

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

Gigablah 13y ago
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.
skj 13y ago
Or, O(n^2) vs O(n log n).
- skj 13y ago
  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.
  - sjtgraham 13y ago
    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.
    - amalcon 13y ago
      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.
      - jerf 13y ago
        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.)
- sjtgraham 13y ago
  No
pjmlp 13y ago
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. -- Jamie Zawinski in 1997
tcwc 13y ago
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.

Gigablah 13y ago

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.

skj 13y ago

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

skj 13y ago
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.
- sjtgraham 13y ago
  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.
  - amalcon 13y ago
    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.
    - jerf 13y ago
      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.)
sjtgraham 13y ago
No

pjmlp 13y ago

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

tcwc 13y ago

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.