Hacker News Reader

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

View on HN

Technically, 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.

I'm curious; what data structure and algorithm are you using to achieve O(log n) routing?

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

Reply on news.ycombinator.com