Re: [code] [for discussion] map-trie

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.
Received on Tue Jun 03 2014 - 20:12:10 MDT