Re: [boost] [countertree] New Version

Subject: Re: [boost] [countertree] New Version
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2011-05-02 17:11:44

Response to Rene Rivera :

 You are right. I wrote the documentation in that format only by time
economy. I wrote in a final format instead of do an intermediate format. I
will do a first page of the documentation where indicate it is a preliminary
library ,not accepted, and not part of the boost library.

 The idea about the namespace is right too. I willl change the boost
namespace by other dependant of it.

 About the idea of the rank tree, it is very easy and fast to implement with
the countertree library. The idea is very similar to the exposed in the
previous message.

 You have the data stored in a vector, or a file or any other container. You
have a “reference” to access to each elements. You implement the index as
map or multimaps with pairs (Value, ”Reference”).

 Imagine you have several index. You make the query with upper_bound and
lower_bound. With the countertree map and multimap you can know the size of
every query in a O(log N) operation.

 In a countertree vector_tree, you insert only the “References” of the range
with less elements. With the “Reference” , access to each element and check
if the values of the others index are in the rank desired, if not , delete
it of the vector_tree (It is a O(log N) operation). At the end of the
process, in the vector_tree you have the valid “References” .

 I used this in a 3D locator in a simulator of silicon doping , and it was
really fast, with the additional problem of a continuous creation and
destroy of elements.

 In my opinion, if you have an easy way to implement it, it is unnecessary
create a complex data structure in order to manage it.

 Response to Marsh Ray

 In all the containers of countertree, all the insertion or deletion
operation are O(log N). The operation with the first and last elements are
slighty faster , because there are pointers to them.

 But depending of the cost of the comparison, you can expect several
millions of operations per second with 1 core, even with data structures of
millions of elements. In my computer 1000000 of insertions and deletions in
a vector_tree with 1000000 elements spend 0.631 seconds in win32 and 2.23
seconds with GCC 4.5 64 bits

 Response to Scott McMurray

 The splay tree must be rebalanced for to optimize the access. The most
significant disadvantage is that the height of the splay tree can be linear.

 The countertree is fast, but if you need more speed, you can build a small
cache over the tree, but must be carefully if you store too the position ,
because if you insert or delete in a previous position to the element stored
in the cache, the position of the element change too.

 In my opinion, the red-black tree make outdated the splay trees, except ,
perhaps in a very limited environment.