On Sun, 24 Oct 2010, Graham Leggett wrote:
I'm not keen to change the semantics at all, I'd rather like to speed up the
array lookup from the linear search we do now.
I went on a hunt for efficient string prefix matching algorithms, but that's
led me into some heavy computer science theory where the bulk of the work was
on prefix matching IP addresses rather than strings (which seems to be a
problem that's received more attention).
I think the hashtable approach would be reasonable, given that we have the
option to pre-create the index at startup post_config.
I am probably missing the obvious, but how do you intend to do the hash
lookup? Given that <Location /app> also matches the dir /application, you
may have to do N lookups for an url of length N.
Have you considered using a trie or a binary search tree?
