Re: [boost] new proposal: order statistics tree

Subject: Re: [boost] new proposal: order statistics tree
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-01-08 04:13:57

On Tue, Jan 8, 2013 at 7:47 AM, Szymon Wojciechowski <sw10_at_[hidden]>wrote:

> I implemented augmented red-black tree which doesn't check the uniqueness
> of values. I have conducted a simple survey: I prepared 5 input files with
> unique 2,7*10e7 integers. The first data set has sorted values as other has
> randomized. I repeated 7 times on every input. A simple program reads from
> input integers and puts it to set (maybe I should use multiset) from
> VisualStudio or my order statistics tree. After that I measured time. Then
> program erases values from data structure in ordered way (from 0, 1, 2...).
> After that I also measured how much time it takes. I uploaded the results
> here: http://wyslijto.pl/plik/q5om39aoua - it's a little bit strange.
> What kind of performance test would you think about?
>

Did you implement or is it possible to implement for this augmented red
black tree split, join and splice operations with logarithmic computational
complexity?

As for tests, there are a number of performance tests of basic container
operations in the following projects:

1. For augmented dynamically allocated B+ trees:
https://github.com/vstadnik/stl_ext_adv

I have added this link, since this project has results of performance tests
for Boost.MultiIndex.

2. For augmented array based B+ trees:
https://github.com/vstadnik/stl_ext_adv_review

This project is prepared for Boost review. It compares performance of new
containers with standard containers and Boost.Container.
The file "boost_performance.cpp" uses Boost.Chrono timer. If your
containers are STL compliant you should not have any problem with this test
code.

Regards,
Vadim Stadnik