Re: [boost] Boost Trie

From: Scott McMurray (me22.ca+boost_at_[hidden])
Date: 2008-03-24 21:59:14

On Mon, Mar 24, 2008 at 9:30 PM, chintan rao <chintanraoh_at_[hidden]> wrote:
>
>  PATRICIA Tries optimize space. I don't know about how much it improves  the
>  time efficiency over normal tries as one could be using TST in it to
>  conserve space. But as far i remember a person #boost channel reported some
>  thing like 2x speed over std::map.
>

(I use PATRICIA to mean joining chains of nodes with only one outbound
link.  Whether that's right not no, I don't know.)

I expect the time efficiciency improvement isn't significant.  It's
probably similar to the difference between iterating list and vector,
in that the memory locality is better.  It's essential, as far as I'm
concerned, though, to keep the node space overhead from getting
excessive, particularly since it does not worsen the time costs.

And that "person in #boost" was likely me.  I got roughly a 2x speed
up for 2x the memory cost, in a non-generic, proof-of-concept
tst-patricia-trie.