No więc dopracowałem drzewko czerwono czarne. Może jeszcze zostały
jakieś błędy, ale chodziło kilkadziesiąt godzin na testach i nie
wywaliło się.

Porównałem wydajność trzech struktur:
QMap<uint>
std::set<uint>
RBTree<uint>

Programy wykonywały 10 głównych pętli. W głównej pętli było 10
podrzędnych pętli. W pętli podrzędnej program dodawał 200tys
elementów (uintów), potem próbował usunąć 100tys. Na końcu
próbował wyszukać pół miliona elementów. Po wykonaniu pętli
podrzędnych program wywoływał metodę clear. Czyli w sumie
program liczy czas dla około 20mln insertów, 10mln usunięć,
50mln wyszukiwań i 10 operacji clear.

Czas dla struktury QMap był najgorszy, wynosił około 1:23s.
Dla std::set był minimalnie lepszy, wynosił około 1:22s.
Natomiast dla mojej, jeszcze nie wyżyłowanej, implementacji
drzew czerwonoczarnych czas wynosił tylko 54 sekundy, więc
różnica jest wyraźna.

Zaczęliśmy rozmawiać w poprzednim wątku o sortowaniu, i
przyznaję, że Bartek zadał mi w pewnym momencie klina.
Straciłem pewność, czy można posortować w miejscu,
czyli w tej samej zaalokowanej pamięci, bez konieczności
odbudowywania drzewka. Okazuje się że jednak można,
czas takiego sortowania w dodatku jest liniowy.

Wrzuciłem do testów wersję drzewa z tym sortowaniem.
Program sortował przed każdym wyszukiwaniem, czyli łącznie
sortował 100 razy. Pomimo czasu niezbędnego na sortowanie,
łączny czas wykonania programu spadł jeszcze o 10 sekund,
do około 44 sekund.

Moja implementacja ma jeszcze kilka miejsc na optymalizację.
Nie próbowałem używać pól bitowych na oznaczenie koloru,
nie próbowałem typu uint16 dla drzewek o rozmiarze do 64k,
nie próbowałem dobierać wartości pewnej stałej w wyszukiwaniu
binarnym, ani próbowałem wywalić kilku ifów które chyba
są chyba zbędne. Jednym słowem, można moją implementację
jeszcze przynajmniej trochę przyspieszyć. Przypuszczam, że
można w takim teście zejść do np. 35-40 sekund. Podsumowując,
można napisać swoją strukturę rb-tree opartą o wektor,
która będzie działała dwa razy szybciej niż struktury
biblioteczne oparte o wskaźniki obudowane iteratorami.
Oczywiście, jest to możliwe tylko wtedy, gdy operacje na
drzewach są dominującymi operacjami w całym czasie
wykonania programu.

Poniżej kompilacja, zrzuty ekranu i kod testujący.

Pozdrawiam

####################################################
#######################
Kompilacja i zrzuty z konsoli
####################################################
#######################

#HELP
./rb00
use
rb00 test loop subloop size_i size_r size_f range seed
Przerwane (core dumped)

#Kompilacja 1
g++ -c -m64 -pipe -O2 -std=c++0x -Wall -W -D_REENTRANT -fPIE -DQT_NO_DEBUG
-DQT_CORE_LIB -I/usr/lib/x86_64-linux-gnu/qt5/mkspecs/linux-g++-64 -I../../rb00
-I/usr/include/qt5 -I/usr/include/qt5/QtCore -I. -I. -o main.o ../main.cpp
g++ -m64 -Wl,-O1 -o rb00 main.o -lQt5Core -lpthread

#Wyniki
time ./rb00 testSet 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 1m23.583s
user 1m23.574s
sys 0m0.032s
time ./rb00 testMap 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 1m25.635s
user 1m25.652s
sys 0m0.008s
time ./rb00 testRB 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 1m0.057s
user 1m0.062s
sys 0m0.012s
time ./rb00 testRbSort 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 0m46.619s
user 0m46.627s
sys 0m0.004s

#Kompilacja 2 (minimalnie pomaga)
g++ -c -m64 -pipe -O3 -std=c++0x -Wall -W -D_REENTRANT -fPIE -DQT_NO_DEBUG
-DQT_CORE_LIB -I/usr/lib/x86_64-linux-gnu/qt5/mkspecs/linux-g++-64 -I../../rb00
-I/usr/include/qt5 -I/usr/include/qt5/QtCore -I. -I. -o main.o ../main.cpp
g++ -m64 -Wl,-O1 -o rb00 main.o -lQt5Core -lpthread

time ./rb00 testSet 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 1m23.691s
user 1m23.695s
sys 0m0.020s
time ./rb00 testMap 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 1m25.699s
user 1m25.700s
sys 0m0.024s
time ./rb00 testRB 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 0m57.353s
user 0m57.363s
sys 0m0.008s
time ./rb00 testRBSort 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 0m46.104s
user 0m46.109s
sys 0m0.008s


#Kompilacja jak wyżej, tylko z -march=native (niewiele pomogła)
time ./rb00 testSet 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 1m23.412s
user 1m23.419s
sys 0m0.016s
x@x:~/Dokumenty/c/rb_tree/rb00/release$ time ./rb00 testMap 10 10 200000 100000
500000 2000000 123
sum:3126348450315581004

real 1m25.281s
user 1m25.275s
sys 0m0.032s
x@x:~/Dokumenty/c/rb_tree/rb00/release$ time ./rb00 testRB 10 10 200000 100000 500000
2000000 123
sum:3126348450315581004

real 0m58.496s
user 0m58.502s
sys 0m0.012s
x@x:~/Dokumenty/c/rb_tree/rb00/release$ time ./rb00 testRBSort 10 10 200000 100000
500000 2000000 123
sum:3126348450315581004

real 0m46.433s
user 0m46.434s
sys 0m0.012s


#kompilacja jak wyżej, ale z -fprofile-user - trochę poprawiła wyniki.

time ./rb00 testSet 10 10 200000 100000 500000 2000000 123
sum:3126348450315581004

real 1m22.991s
user 1m22.993s
sys 0m0.020s
x@x:~/Dokumenty/c/rb_tree/rb00/release$ time ./rb00 testMap 10 10 200000 100000
500000 2000000 123
sum:3126348450315581004

real 1m23.761s
user 1m23.761s
sys 0m0.024s
x@x:~/Dokumenty/c/rb_tree/rb00/release$ time ./rb00 testRB 10 10 200000 100000 500000
2000000 123
sum:3126348450315581004

real 0m54.865s
user 0m54.853s
sys 0m0.028s
x@x:~/Dokumenty/c/rb_tree/rb00/release$ time ./rb00 testRBSort 10 10 200000 100000
500000 2000000 123
sum:3126348450315581004

real 0m44.654s
user 0m44.647s
sys 0m0.020s


####################################################
#######################
Kod testujący (bez kodu drzewka
####################################################
#######################

#include "../rb_tree.h"

#include <QStringList>
#include <QRegExp>
#include <QTextStream>
#include <set>
#include <QMap>

typedef int ityp;
typedef const ityp cityp;

typedef unsigned int utyp;
typedef const utyp cutyp;

typedef long long ltyp;
typedef const long long cltyp;

typedef unsigned long long ultyp;
typedef const unsigned long long cultyp;

class Empty {};

void testSet( cityp loop , cityp subloop , cityp size_i , cityp size_r , cityp
size_f, cltyp range , cltyp seed ) {
QTextStream out(stdout);
std::mt19937_64 rnd(seed);
ultyp sum = 1;
ultyp m = 1;
std::set<utyp> set;
for( ityp i=0 ; i<loop ; i++ ) {
for( ityp j=0 ; j<subloop ; j++ ) {
for( ityp k=0 ; k<size_i ; k++ ) {
set.insert(rnd() % range);
}
for( ityp k=0 ; k<size_r ; k++ ) {
set.erase( rnd() % (range*32/31) );
}
// out << "size:" << set.size() << " " << i << " " << j << endl;
sum += set.size();
for( int k=0 ; k<size_f ; k++ ) {
const auto node = set.find( rnd() % (range*32/31) );
if( node != set.cend() ) {
sum += *node * m;
m += rnd() % 1024;
}
}
}
set.clear();
}
out << "sum:" << sum << endl;
}


void testMap( cityp loop , cityp subloop , cityp size_i , cityp size_r , cityp
size_f, cltyp range , cltyp seed ) {
QTextStream out(stdout);
std::mt19937_64 rnd(seed);
ultyp sum = 1;
ultyp m = 1;
QMap<utyp,Empty> map;
for( ityp i=0 ; i<loop ; i++ ) {
for( ityp j=0 ; j<subloop ; j++ ) {
for( ityp k=0 ; k<size_i ; k++ ) {
map.insert(rnd() % range,Empty());
}
for( ityp k=0 ; k<size_r ; k++ ) {
map.remove( rnd() % (range*32/31) );
}
// out << "size:" << set.size() << " " << i << " " << j << endl;
sum += map.size();
for( int k=0 ; k<size_f ; k++ ) {
const auto key = map.find( rnd() % (range*32/31) );
if( key != map.cend() ) {
sum += key.key() * m;
m += rnd() % 1024;
}
}
}
map.clear();
}
out << "sum:" << sum << endl;
}


void testRB( cityp loop , cityp subloop , cityp size_i , cityp size_r , cityp size_f,
cltyp range , cltyp seed ) {
QTextStream out(stdout);
std::mt19937_64 rnd(seed);
ultyp sum = 1;
ultyp m = 1;
RBTree<utyp> rb;
for( ityp i=0 ; i<loop ; i++ ) {
for( ityp j=0 ; j<subloop ; j++ ) {
for( ityp k=0 ; k<size_i ; k++ ) {
rb.insert(rnd() % range);
}
for( ityp k=0 ; k<size_r ; k++ ) {
const auto node = rb.search( rnd() % (range*32/31) );
if( ! rb.isNull(node) )
rb.remove(node);
}
// out << "size:" << set.size() << " " << i << " " << j << endl;
sum += rb.size();
for( int k=0 ; k<size_f ; k++ ) {
const auto node = rb.search( rnd() % (range*32/31) );
if( ! rb.isNull(node) ) {
sum += rb.cData(node) * m;
m += rnd() % 1024;
}
}
}
rb.clear();
}
out << "sum:" << sum << endl;
}


void testRBSort( cityp loop , cityp subloop , cityp size_i , cityp size_r , cityp
size_f, cltyp range , cltyp seed ) {
QTextStream out(stdout);
std::mt19937_64 rnd(seed);
ultyp sum = 1;
ultyp m = 1;
RBTree<utyp> rb;
for( ityp i=0 ; i<loop ; i++ ) {
for( ityp j=0 ; j<subloop ; j++ ) {
for( ityp k=0 ; k<size_i ; k++ ) {
rb.insert(rnd() % range);
}
for( ityp k=0 ; k<size_r ; k++ ) {
const auto node = rb.search( rnd() % (range*32/31) );
if( ! rb.isNull(node) )
rb.remove(node);
}
rb.sort();
// out << "size:" << set.size() << " " << i << " " << j << endl;
sum += rb.size();
for( int k=0 ; k<size_f ; k++ ) {
const auto node = rb.sortSearch( rnd() % (range*32/31) );
if( ! rb.isNull(node) ) {
sum += rb.cData(node) * m;
m += rnd() % 1024;
}
}
}
rb.clear();
}
out << "sum:" << sum << endl;
}


int main(int argc, char *argv[])
{
QTextStream out(stdout);
if( argc != 9 ) {
out << "use\nrb00 test loop subloop size_i size_r size_f range seed" << endl;
abort();
}

const QString test = argv[1];
cityp loop = QString(argv[2]).toInt();
cityp subloop = QString(argv[3]).toInt();
cityp size_i = QString(argv[4]).toInt();
cityp size_r = QString(argv[5]).toInt();
cityp size_f = QString(argv[6]).toInt();
cltyp range = QString(argv[7]).toLongLong();
cltyp seed = QString(argv[8]).toLongLong();

if( test.toLower() == "testset" )
testSet( loop , subloop , size_i , size_r , size_f , range , seed );
else if( test.toLower() == "testmap" )
testMap( loop , subloop , size_i , size_r , size_f , range , seed );
else if( test.toLower() == "testrb" )
testRB( loop , subloop , size_i , size_r , size_f , range , seed );
else if( test.toLower() == "testrbsort" )
testRBSort( loop , subloop , size_i , size_r , size_f , range , seed );
else if( test.toLower() == "profile") {
testSet( loop , subloop , size_i , size_r , size_f , range , seed );
testMap( loop , subloop , size_i , size_r , size_f , range , seed );
testRB( loop , subloop , size_i , size_r , size_f , range , seed );
testRBSort( loop , subloop , size_i , size_r , size_f , range , seed );
}

return 0;
}