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?
-- Francesco
This archive was generated by hypermail 2.2.0 : Wed Jun 04 2014 - 12:00:13 MDT