Re: [boost] Countertree

Subject: Re: [boost] Countertree
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-11-23 15:03:02

When you design a tree, you must develop a balanced algorithm in order to
prevent a degenerate tree ( Tree like a linked list). You have several
types of balanced trees ( mainly Red-Black and AVL ).  The balancing of a
tree can be done in several ways. That decisions have influence on the
quality of the balance and the speed of the tree.

 You have an excellent description with code in “Introduction to
Algorithms”. When I decided add the counter to the nodes for the design of
the CounterTree, I tried to use that code, but was very complex with the
counters, and decide design my own balanced algorithm based on the 234Tree.
The result is the actual version of CounterTree. It is 15% more or less
slower than the GCC implementation, but is logic , because must manage the
pointers and the counters.

 Looking for a way for to improve the speed , I examined others
implementations of Red-Black trees, several books an mainly with the
experience obtained with the Suballocator. I decided to change several
things of the algorithm and the implementation, pursuing to improve the
speed. I have this design done on paper.

 At that time , appear on Boost comments about the problem of the augmented
trees, in order to do many others things with the trees. I study my design
on paper, and decompose all the internal process of the tree in a “catalog”
of small operations like:

   -

   Insert/delete a node in the right/left pointer of a node.
   -

   All the rotations with nodes
   -

   Swap of nodes directly linked and not directly linked

 With the new design, if you want build your own augmented tree, you need :

   -

   Design the information to insert in the node
   -

   Design the process to do with your node information in all the
   operations of the “catalog”

 With this you can compile your own augmented tree, obtaining the maximum
speed.

 The concurrent countertree is a cover over the tree, which permit many
process work concurrently with the tree in a safe mode. If you design your
own augmented tree, and use this cover you can have your own concurrent
augmented tree.

In the same way than using the suballocator , you can improve the speed,
and the memory management of your tree.

 For many statistical function , you can implement directly over the
CounterTree. In the same way you can implement an efficient
PriorityQueueusing it. But the best solution is to include the
information and the
process inside the tree. With this, you can customize your tree and obtain
the maximum speed.

 I know that in the design process they will appear a lot of problems , but
I expect resolve them in a satisfactory way. Actually I am working in the
concurrent version. When finish I will begin with the augmented trees.
Sorry by the delay, but I don't have more free time for to work on it.

 Thanks by your interest, your ideas and suggestions. You help me to
improve it and to be useful to the Boost community.

Sincerely yours

 Francisco Tapia

2012/11/22 Andrii Sydorchuk <sydorchuk.andriy_at_[hidden]>

> Francisco,
>
> Thanks for your reply. Please let me know if I misunderstood one of your
> comments.
>
> On Thu, Nov 22, 2012 at 2:11 PM, Francisco José Tapia <fjtapia_at_[hidden]
> >wrote:
>
> >  The countertrees are augmented data structures. I redesign the insertion
> > deletion and balanced algorithms. The actual version is around 10% - 15%
> > slower than the GCC version of red-black
> > trees.
> >
>
> I don't quite understand what you mean by redesign. Ideally those
> operations
> should be implemented completely in the same way as for red-black tree
> implementation (std::map, std::set), except that additional processing of
> augmented data is required. But that sounds more like extension, as all of
> the core logic that manipulates with tree nodes and colors should be
> completely
> the same. At least I don't see the reason it shouldn't.
>
>  I have designed on paper a new algorithms for to insert, delete and
> > balance the countertree, in order to improve the speed. In the new
> version
> > you have a catalog of operations with the nodes. All the insertion,
> > deletion and balancing can be done combining operations of this catalog.
> >
>
> It sounds unreasonable for me to limit the set of allowed operations
> to some catalog. Basically any function that satisfies commutative and
> associative properties should work. Thus it makes sense to pass such
> a functor as a template argument to the Tree data structure,
> to be not limited to any catalog of predefined operations.
>
>
> > The node operations have two parts, the pointers and the node color, and
> > the augmented information.In the countertree the augmented information
> are
> > the node counters.
> >
>
> Sure, and the logic that deals with pointers and node colors
> should be completely the same as for the std::map or std::set.
>
>
> > I am working now on the concurrent version of the countertree. When
> finish
> > with this , I will begin with the augmented data trees.
> >
>
> I am not sure what exactly "concurrent countertree" means?
> I don't see how insertion/deletion or lookup can be parallelized even for
> BST,
> probably because lack of my knowledge in the area.
> Thus simple example of speedup using any of the above operations with two
> threads will be perfect.
>
> Thanks,
> Andrii
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>