From: chintan rao (chintanraoh_at_[hidden])
Date: 2008-03-25 08:15:24
Finally some bad discovery was made.........
There seems to be a PATRICIA trie implementation in libstdc++ in 4.3
Please suggest modifications to my application.
Chintan Rao H
On Tue, Mar 25, 2008 at 8:41 AM, chintan rao <chintanraoh_at_[hidden]> wrote:
> On Tue, Mar 25, 2008 at 7:29 AM, Scott McMurray <me22.ca+boost_at_[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:
> > http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk