4 ms·
"chances are, if you're about to look something up, you've recently read it from somewhere and it's going to be hot in the cache" So a very common scenario for
by optimiz3 13y ago
"chances are, if you're about to look something up, you've recently read it from somewhere and it's going to be hot in the cache"
So a very common scenario for TRIEs/K-ary trees is for high-speed parsing - basically every byte read off the input transfers you to another state in the state machine.
Cache is moot as the state machine/tree is almost always in cache. The key (ha!) is input doesn't need to be cached, nor is any precomputed data required on the input side to be performant.
- nly 13y agoWhat would you be looking up in a radix tree while parsing? I don't think I've ever written one where prefix operations have been useful.
- optimiz3 13y agoJSON/BSON parsing for one, you use the field name to walk the tree, then the node contains a function pointer for what to do with the member. Any scenario where you decode {k,v} pairs benefits from this.
- nly 13y agoWhy do you need prefixes for that? Sounds like the perfect usecase for a hash table or a precomputed perfect hash function.
- optimiz3 13y agoYou pay for computing a hash function over directly walking to the next node. EDIT: Here you go. Some work I contributed a while ago when we were using Mongo. Replace hash table with a TRIE, deserialization performance goes up 40%. Because you don't need to decode a string, hash it, and then hit a hash table. https://github.com/mongodb/mongo-csharp-driver/commit/0b78790af8f510d588a2b7d5478f75290a649bf7 https://github.com/mongodb/mongo-csharp-driver/commit/0b7879...
- nly 13y agoPerfect hash functions are ridiculously cheap. Completely different beasts to those designed to operate as good hashers for all inputs.
- optimiz3 13y agoHow so? Perfect hash functions only work when all possible inputs are known.
- sp332 13y agoSomething odd about that commit message... You know that O(m) is equivalent to 5 * O(m) right? Any constant multiplier will have the same big-O value.
- optimiz3 13y agoWhile it is true that asymptotically 5 * O(m) equals O(m), in practice 5 * O(m) is still 5x slower. EDIT (reply threshold): "That's not how big-O notation works. It only applies to asymptotic behavior. It makes sense to say that iterating over the whole list 5 times is slower than just doing it once, but it's O(m) either way." Now you're just being pedantic.
- sp332 13y agoThat's not how big-O notation works. It only applies to asymptotic behavior. It makes sense to say that iterating over the whole list 5 times is slower than just doing it once, but it's O(m) either way.
- eloff 13y agoYeah, that will work, if everything is hot in cache there won't be a big difference between a radix style tree and a hash table. Obviously python doesn't fit that description usually.