Re: [boost] Countertree

Subject: Re: [boost] Countertree
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-11-22 16:26:41

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