I have read the Policy- Based Data Structures of GCC and the Boost Accumulator library. I think the problem is the same for the two. The statistical operations are done over current data structures as arrays, vectors, map , hash... Each data structure have some advantages and several problems. The problem is the number of operations over the data structure. If you need obtain a statistical value over a collection of data, and need to obtain only a few times, many data structure can satisfy you requirements. The problem is when you need to do a lot of times, by example, you have intervals, and you need to detect the intersection between them in order to calculate a collision, in a particle simulation. With that problem, the solution to the problem pass for to redesign the data structure used. The augmented trees are a possible solution of many of these problems. But it is complex. 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 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. 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. If you design the process to do with your augmented information for all the operations of the catalog, you can create your augmented balanced tree mixing the pointer and color operations with your code for each operation. You can have augmented trees with several concepts, like the position, accumulators and statistical operations as are defined in the Policy Based Data Structures and in the Boost Accumulator library. In the node operation you mix the pointers and color operations with the process of the catalog for all the augmented informations added. I am working now on the concurrent version of the countertree. When finish with this , I will begin with the augmented data trees. The solution exposed can be combined with the concurrent process, which can improve a lot the speed of these accumulators, statistical operations or any other idea. If you are interested, when I have something useful , I will comment and offer to you. Sincerely yours Francisco 2012/11/22 Andrii Sydorchuk <sydorchuk.andriy@gmail.com>
Hi Francisco,
First of all I think that your library will be a great addition to Boost. To make it even better I will suggest to make CounterTree more generic:
1) Expand CounterTree implementation to RangeTree (the name might be different). RangeTree is a data structure that supports any operation on its nodes that is associative ((a*b)*c = a*(b*c)) and commutative (a*b = b*a). The examples of such an operation are: addition, multiplication, gcd, xor, bit count, etc. RangeTree allows to execute the following operations in logarithmic time: a) insertion / removal / lookup of the new element by key; b) operation evaluation on the tree nodes within the given key range.
2) Considering above, expand RangeTree to support any type of operation argument (I call it property). E.g. for the CounterTree this is an integer representing number of elements in a subtree, for the ColourTree this can be node colour and operation defined as mixing all the colours in the subtree.
3) Considering 1) and 2), it will be possible to implement CounterTree as specialization of RangeTree. Augmented tree, recently requested by Phil Endecott for dynamic text width querying, can be implemented as specialization of the RangeTree data structure as well.
4) Summarizing all of the above the RangeTree declaration will look like: template <class Key, class Compare, class Property, class Operation, class Allocator> class RangeTree; Property RangeTree::query(const Key& left, const Key& right); // basic query interface
The CounterTree specialization: template <class Key, class Compare, class Allocator> class CounterTree : RangeTree<Key, Compare, int, addition<int>, Allocator>;
And even more, the CounterRangeTree specialization: template <class Key, class Compare, class Property, class Operation, class Allocator> class CounterRangeTree : RangeTree<Key, Compare, pair<int, Property>, operation< addition<int>, Operation >, Allocator>; Property CounterRangeTree::query(int start_index, int end_index); // counter query interface
Such a design will widely expand application area of the library and will allow to use it for the large number of live updating/querying systems.
Regards, Andrii
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost