Re: [boost] [stl_ext_adv] ] Interest in advanced data structures

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2011-12-01 08:42:42

On Thu, Dec 1, 2011 at 10:45 PM, Andrii Sydorchuk <
sydorchuk.andriy_at_[hidden]> wrote:

> >
> > You are right, if you mean the cost of construction of an advanced data
> > structure, it is O(N log N). As soon as the required data have been
> written
> > the sum and mean value of any consecutive elements can be found in O(log
> N)
> > time. Please, have a look at performance tests of the fast algorithm
> > accumulate() in the section:
>
> The next solution works in O(1) and requires only O(N) for construction
> step:
> template <typename T>
> class accumulator {
> public:
>  void init(std::vector<T> &elems) {
>     sum.reserve(elems.size() + 1);
>     sum.push_back(0);
>     for (std::vector<T>::iterator it = elems.begin(); it != elems.end();
> ++it) {
>       sum.push_back(sum.back() + *it);
>     }
>  }
>
>  T operator()(T first, T last) const {
>    return sum[last+1] - sum[first];
>  }
>
> private:
>  std::vector<T> sum;
> };
> I guess this solution is slightly better for those math targets you
> mentioned above. It also works with any associative operation.
>
> Andrii

This is the best possible approach provided that data are not modified or
updated. Unfortunately, in practical data analysis, data fitting and
approximation this is a relatively rare case. For large and huge data sets
the cost of vector update operations will be quite significant and often
prohibitive.

It is also interesting to note that if the same solution was based on
container sequence<bp_tree_idx> from the proposed library then it would
efficiently support update operations for container elements. However, it
would have linear cost of updating the sum data. The best possible
performance for a user algorithm which requires a wide set of operations
can be achieved with sequence<bp_tree_idx_acc>. The constant cost of
summation similar to this example is possible, but not implemented yet.
This is discussed in section "Iterators and accumulators".

Thank you,
Vadim