3 ms·
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 a
by 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 agoIn 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 agoWhich 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.)