On 06/03/2014 08:40 AM, Kinkie wrote: > Hi all, > as an experiment and to encourage some discussion I prepared an > alternate implementation of TrieNode which uses a std::map instead of > an array to store a node's children. > > The expected result is a worst case performance degradation on insert > and delete from O(N) to O(N log R) where N is the length of the > c-string being looked up, and R is the size of the alphabet (as R = > 256, we're talking about 8x worse). > > The expected benefit is a noticeable reduction in terms of memory use, > especially for sparse key-spaces; it'd be useful e.g. in some lookup > cases. > > Comments?
To evaluate these optimizations, we need to know the targeted use cases. Amos mentioned ESI as the primary Trie user. I am not familiar with ESI specifics (and would be surprised to learn you want to optimize ESI!), but would recommend investigating a different approach if your goal is to optimize search/identification of strings from a known-in-advance set. Cheers, Alex.