Re: [boost] Boost Trie

From: chintan rao (chintanraoh_at_[hidden])
Date: 2008-03-25 12:22:27

Hi,
Sorry took libstdc++ as a standard..
my mistake :(.
Regards,
Chintan Rao H

On Tue, Mar 25, 2008 at 6:28 PM, chintan rao <chintanraoh_at_[hidden]> wrote:

>
>
> On Tue, Mar 25, 2008 at 5:45 PM, chintan rao <chintanraoh_at_[hidden]>
> wrote:
>
> > Hi,
> > Finally some bad discovery was made.........
> >
> > http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html
> >
> > There seems to be a PATRICIA trie implementation in libstdc++ in 4.3 and
> > 4.2 implementations
> > Please suggest modifications to my application.
>
> Is there some way this can still sustain?
>
> >
> >
> > Regards,
> > 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]> wrote:
> > >
> > > > 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
> > > >
> > >
> > >
> >
>