3 ms·

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