Subject: Re: [boost] new proposal: order statistics tree
From: Szymon Wojciechowski (sw10_at_[hidden])
Date: 2013-01-07 15:47:37
"Vadim Stadnik" <vadimstdk_at_[hidden]> pisze:
> On Thu, Jan 3, 2013 at 7:46 AM, Szymon Wojciechowski wrote:
>
> >
> > I would like to propose to add new data structure - order statistics tree.
> > Briefly, it is container which allows logarithmic inserting, searching and
> > erasing as in set, but additionally it permits to access elements via
> > numerical value - key order. I have some ready implementation with all
> > appropriate functions (without their all overloaded forms) with gtest
> > regression list, but the code isn't boostified. The regression passes on
> > gcc 4.6.3 and vs2010.
> >
> > Is there anybody interested in?
> >
> >
> Yes, I am interested.
> What kind of tree did you implement?
> Did you measured performance of basic container operations and compared
> with the standard set and/or multiset?
>
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?
Best regards,
Szymon Wojciechowski