4 ms·
I wouldn't call that computationally efficient. It is possible to make routing an O(log n) operation; your routing solution, like all routers that use regexes d
by orlandu63 15y ago
I wouldn't call that computationally efficient. It is possible to make routing an O(log n) operation; your routing solution, like all routers that use regexes directly, is O(n).
- tabbyjabby 15y agoI'm curious; what data structure and algorithm are you using to achieve O(log n) routing?
- k4st 15y agoIf n is the number of routes, and they are sorted (e.g. implicitly through a prefix tree) and evenly distributed accordingly then then the claim might be plausible by doing log n prefix comparisons of increasingly smaller suffixes of the route to be resolved. I find this line of reasoning unusual and misleading though. The lower bound is linear in the length of the route if all routes participate in your regular expression and if you have it pre-compiled to, for example, a DFA or an LL parser ahead of time.
- troels 15y agoTechnically, yes. What I was referring to was more mundane though. The difference between writing a parser/interpreter partially in PHP or minimizing the php code to a loop and then push all the hard stuff down to preg is significant. Optimizing it further is probably futile, compared to what else goes on in a typical http req-res cycle. It's a red herring anyway, so I sort of regret bringing it up. Much more important is the other point - that this is a standard tool, rather than a tailored one.