10 ms·
> It it is non-trivial (not possible?) to do this in O(1) for routes that use matching / wildcards I'd be impressed if they did it consistently in O(1) for sta
by herge 12y ago
> It it is non-trivial (not possible?) to do this in O(1) for routes that use matching / wildcards
I'd be impressed if they did it consistently in O(1) for static routes. I think they were looking for O(log(number of different routes)) instead of O(n).
- azinman2 12y agoIf the paths have some kind of non crazy Regex leading up to what gets munched for path variables (eg /path1 versus /path2) then you could at least build a tree of maps at each level, which would be roughly constant time for the most common cases.
- herge 12y ago> roughly constant time for the most common cases. For small values of n ;) A tree of maps would be consistently log(n), like any map. Even a hashtable would hash to buckets eventually, and are log(n).
- TheLoneWolfling 12y agoNot if you're using a Cuckoo hashmap. Honestly, I have no idea why people aren't taught Cuckoo-maps by default. It's simple, has true O(1) worst-case lookup, and has easy deletion. About the only problem is trying to prove insertion time.