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

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Thijs (M.A.) van den Berg (thijs_at_[hidden])
Date: 2011-11-30 06:17:35

> On Wed, Nov 30, 2011 at 9:06 PM, Thijs (M.A.) van den Berg
> <thijs_at_[hidden]>wrote:
> 
>>> The examples demonstrate how to improve the computational complexity from
>>> O(N) to O(log N) in the following applications and problems:
>>> 
>>> - numerical integration.
>>> - calculation of mean value and standard deviation;
>>> - calculation of weighted mean value;
>> 
>> I think O(log N) is misleading.
>> Problem:  I  want to estimate the mean of N numbers in a file on my disk.
>> Clearly I should al least present all of the number in that file al least
>> once  (O(N)) to a black box algorithm that computes the mean?
>> 
>> Thank you for this comment.
> 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:
> 
> 
> http://dl.dropbox.com/u/51041088/stl_ext_adv_doc/doc/performance.html
> 
> 
> Also, you can use example or test code to notice the difference in the
> performance of standard and fast algorithms accumulate().
> 
Thank Vadim. For certain applications your container clearly outperforms other. The hierarchical accumulation is particularly interesting if you need to calculate many more accumulations than you need to do inserts.
 To get a better view of both pros and potential cons, can you also add a comparison for *push_back inserts* (like you did in the multiset) in a std::vector besides the worst case 'before the middle'?

An interesting project!