ciąg dalszy drzewa czerwono-czarne

Newsgroups	pl.comp.programming
Date	2017-08-17 14:04 -0700
Message-ID	<60e0ed10-a616-48b1-bbd4-e56027e82a85@googlegroups.com> (permalink)
Subject	ciąg dalszy drzewa czerwono-czarne
From	"M.M." <mmarszik@gmail.com>

Show all headers | View raw

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;
}

Back to pl.comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

ciąg dalszy drzewa czerwono-czarne "M.M." <mmarszik@gmail.com> - 2017-08-17 14:04 -0700
  Re: ciąg dalszy drzewa czerwono-czarne bartekltg <bartekltg@gmail.com> - 2017-08-18 01:51 -0700
    Re: ciąg dalszy drzewa czerwono-czarne "M.M." <mmarszik@gmail.com> - 2017-08-18 02:11 -0700
    Re: ciąg dalszy drzewa czerwono-czarne "M.M." <mmarszik@gmail.com> - 2017-08-21 04:30 -0700

csiph-web