Boost logo

Boost :

From: chintan rao (chintanraoh_at_[hidden])
Date: 2008-03-24 23:11:43

On Tue, Mar 25, 2008 at 7:29 AM, Scott McMurray <[hidden]>

> 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.

Must have been you. You had spoken about tst patricia trie. :).

> _______________________________________________
> Unsubscribe & other changes:

Boost list run by bdawes at, gregod at, cpdaniel at, john at