Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: endight . (endight_at_[hidden])
Date: 2015-03-05 11:21:36

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
>