[code] [for discussion] map-trie

From: Kinkie <gkinkie_at_gmail.com>
Date: Tue, 3 Jun 2014 16:40:42 +0200

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

Received on Tue Jun 03 2014 - 14:40:50 MDT

This archive was generated by hypermail 2.2.0 : Wed Jun 04 2014 - 12:00:13 MDT