The chunking seems like a missed opportunity. It still uses a loop, so it's still O(n) in the number of routes. That is, 200 routes will take twice as long. 1000 routes will take 10 times as long. But maybe 100 routes is all we ever see in reality?
Regardless, it's a small leap from that to using a tree. I would like to have seen timings for that, and for larger numbers of routes.
Building a trie from a list of strings is trivial. Building one from a list of regexes is not. But you don't need the complexity of inspecting or interpreting the regexes.
With a regular binary tree, you'll need to compile multiple regexes. The root is a regex with all urls in only two groups: (a|b|c|d)|(e|f|g|h). If the first group is non-empty, then you move to the next node: (a|b)|(c|d). If the second group is non-empty, then you try (c)|(d). If the first group of that is non-empty, then the url was c. That should be O(k * log n) where k is the length of the url and n in the number of urls.
The grouping method requires 10 regex matches for 100 routes. 2^10 == 1024, so the tree method can do 10 times more routes in about the same amount of work. A million routes with a tree is only twice as hard as a thousand, or twice as hard as a hundred with chunking. A million routes with chunking in 10,000 times harder than a hundred.
On the other hand, the tree requires O(n * log n) memory, where n chunks of constant size requires only O(n) memory. Perhaps that's significant.
edit: misplaced asterisks triggered italics.
edit2: Actually, you don't even need to add or check groups. At each node you only need to combine half the regexes into one with no outer group. For example, the top node regex from above could be just a|b|c|d. If it matches, go to the left node (which is just a|b). If it doesn't match, go to the right node (which is just e|f). As an edge case, the right-most tip node will all need to have a regex to distinguish between it and non-matching urls. This also makes it easier to dynamically add routes without recompiling the whole tree. Just add the route to the right side of each node, which requires no work until you get to the rightmost tip. Occasionally rebalance. Is dynamically modifying the routes something that people do?
Or how about this: a single regex, but with groups that you can walk like a tree:
(((a)|(b))|((c)|(d))) | (((e)|(f))|((g)|(h)))
The number of groups will be O(n * log n). So 10-20 times the number of urls at most. It's certainly not quadratic.
The groups will in depth-first order. It's slightly complicated by the fact that the regexes contain capturing groups themselves, but you can precompute an offset table that accounts for them.
If you use names like that, walking the tree is easy. Just concatenate "0" or "1" to the current node node to find the child nodes. Also, the final matching group name is a binary number corresponding to matching route's index into the list of routes. For example, url "e" has the name "100". That's a binary 4, which is url "e"'s position in the list.
No results.
The chunking seems like a missed opportunity. It still uses a loop, so it's still O(n) in the number of routes. That is, 200 routes will take twice as long. 1000 routes will take 10 times as long. But maybe 100 routes is all we ever see in reality?
Regardless, it's a small leap from that to using a tree. I would like to have seen timings for that, and for larger numbers of routes.
Building a trie from a list of strings is trivial. Building one from a list of regexes is not. But you don't need the complexity of inspecting or interpreting the regexes.
With a regular binary tree, you'll need to compile multiple regexes. The root is a regex with all urls in only two groups: (a|b|c|d)|(e|f|g|h). If the first group is non-empty, then you move to the next node: (a|b)|(c|d). If the second group is non-empty, then you try (c)|(d). If the first group of that is non-empty, then the url was c. That should be O(k * log n) where k is the length of the url and n in the number of urls.
The grouping method requires 10 regex matches for 100 routes. 2^10 == 1024, so the tree method can do 10 times more routes in about the same amount of work. A million routes with a tree is only twice as hard as a thousand, or twice as hard as a hundred with chunking. A million routes with chunking in 10,000 times harder than a hundred.
On the other hand, the tree requires O(n * log n) memory, where n chunks of constant size requires only O(n) memory. Perhaps that's significant.
edit: misplaced asterisks triggered italics.
edit2: Actually, you don't even need to add or check groups. At each node you only need to combine half the regexes into one with no outer group. For example, the top node regex from above could be just a|b|c|d. If it matches, go to the left node (which is just a|b). If it doesn't match, go to the right node (which is just e|f). As an edge case, the right-most tip node will all need to have a regex to distinguish between it and non-matching urls. This also makes it easier to dynamically add routes without recompiling the whole tree. Just add the route to the right side of each node, which requires no work until you get to the rightmost tip. Occasionally rebalance. Is dynamically modifying the routes something that people do?