Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Kenneth Adam Miller (kennethadammiller_at_[hidden])
Date: 2015-03-05 11:34:03

Are there any already made outlined plans? Because I need to use a
specialized radix tree (or caching trie) for a very highly performance
critical task and I was wondering if I could somehow get my code into boost
so that the code can be reused. The Trie type itself could be an NVI
interface, and the specializations mere exchangable templates.

What do you think?

On Thu, Mar 5, 2015 at 11:21 AM, endight . <endight_at_[hidden]> wrote:

> Is there place for one more contributor (for me) ? Should i someshow prove
> my skills?
>
> 2015-03-05 10:15 GMT+03:00 Antony Polukhin <antoshkka_at_[hidden]>:
>
> > 2015-03-05 2:55 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca_at_[hidden]>:
> >
> > > Hello,
> > >
> > > I have modified the directory strucure. I think it's ok right now.
> > >
> > > > Another significant and hard  task:
> > > > trie_node structure looks too heavy: there are too many member
> > variables.
> > > > Try to simplify trie_node and value_list_node structures. Think of a
> > > > possible optimizations of the trie_node structure for
> > > trie_set|trie_map|trie_multiset|trie_multimap.
> > > > For example all the sets do not require values, so pointers to value
> > list
> > > nodes can be removed from trie_set in that case.
> > >
> > > I have thought of this task too. I will share with you some ideas in
> > order
> > > to get some feedback about them.
> > >
> > > 1. Value = void specialization for trie_node which would remove
> pointers
> > to
> > > value_list_head/tail, self_value_count.
> > >
> >
> > +1
> >
> >
> > > 2. Another specialization or something like this would be ok for
> trie_map
> > > also. The map_node should only contain a member
> > > value_type value. value_list_head/tail, self_value_count should be
> > removed
> > > in this case to but I don't know how to specialize the template (for
> > which
> > > key, value) type.
> > >
> >
> > +1
> >
> > How about adding aditional template parameter to map node. Something like
> >
> > template <class Key, class Value, bool IsMulty>
> > class map_node;
> >
> >
> > >
> > > 3. Considering 2, trie_multiset could be easily implemented in terms of
> > > trie_map<key, int>, maybe using private inheritance. The int would keep
> > > track of the frequency of the key prefix.
> >
> >
> > +1
> >
> >
> > > 4. value_count could be completely removed but this would greatly
> reduce
> > > the performance of count_prefix function. In my opinion this shouldn't
> be
> > > removed.
> > >
> >
> > This is discussable. Let's solve this some time later.
> >
> >
> > > I don't know too much about pred_node, next_node, and the
> > > child_iter_of_parrent. I need to take some more time to look at those
> > > things to see if any of them could be removed. I see that pred_node and
> > > next_node are used in trie_iterator and child_iter_of_parrent is used
> to
> > > maintain the values of pred_node and next_node. However, I don't know
> > which
> > > would be the tradeofs of the removal for each of them.
> > >
> >
> > Let's eat an elephant part by part. There's more than enough tasks right
> > now, even without *_node and child_iter_of_parrent.
> >
> >
> > > Looking forward to your feedback about the ideas above.
> > >
> >
> > Good progress! Trie library becoming better and better.
> >
> > --
> > Best regards,
> > Antony Polukhin
> >
> > _______________________________________________
> > Unsubscribe & other changes:
> > http://lists.boost.org/mailman/listinfo.cgi/boost
> >
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>