On Tue, Jan 8, 2013 at 7:47 AM, Szymon Wojciechowski <sw10@interia.pl>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