Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #30345 > unrolled thread

ciąg dalszy drzewa czerwono-czarne

Started by"M.M." <mmarszik@gmail.com>
First post2017-08-17 14:04 -0700
Last post2017-08-21 04:30 -0700
Articles 4 — 2 participants

Back to article view | Back to pl.comp.programming

Contents

  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

#30345 — ciąg dalszy drzewa czerwono-czarne

From"M.M." <mmarszik@gmail.com>
Date2017-08-17 14:04 -0700
Subjectciąg dalszy drzewa czerwono-czarne
Message-ID<60e0ed10-a616-48b1-bbd4-e56027e82a85@googlegroups.com>
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;
}

[toc] | [next] | [standalone]

#30355

Frombartekltg <bartekltg@gmail.com>
Date2017-08-18 01:51 -0700
Message-ID<3d99e085-291b-4d20-85d6-6b9cc4d21c2b@googlegroups.com>
In reply to#30345
On Thursday, August 17, 2017 at 11:04:34 PM UTC+2, M.M. wrote:
> 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ę.

Za szybko nie będe mógł poczytać. 
Jak to nie tajne:), wrzuć gdzies całość (włacznie z drzewkiem).

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#30357

From"M.M." <mmarszik@gmail.com>
Date2017-08-18 02:11 -0700
Message-ID<25a77e8b-1065-43a8-be62-3d59f89d18cc@googlegroups.com>
In reply to#30355
On Friday, August 18, 2017 at 10:51:33 AM UTC+2, bartekltg wrote:
> On Thursday, August 17, 2017 at 11:04:34 PM UTC+2, M.M. wrote:
> > 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ę.
> 
> Za szybko nie będe mógł poczytać.
Tak, wymaga przemyślenia, w poprzednim wątku od pisania na szybko
zrobiła się sieczka.
 
> Jak to nie tajne:), wrzuć gdzies całość (włacznie z drzewkiem).
Nic tajnego nie ma, zrobię jakiegoś bloga i wkrótce wrzucę.
Tak ogólnie, to poza sortowaniem, mam wszystko bardzo mocno
wzorowane na Cormenie, tylko zamiast wskaźników mam indeksy.

Sortowania ani w Cormenie, ani w Internecie nie znalazłem, 
musiałem zastanowić się sam. Wrzucam kod, zapewne jest
za dużo ifów, zapewne można to jeszcze zoptymalizować.

Generalnie bardzo polecam to rozwiązanie, szczególnie
gdy ktoś ma bardzo dużo wyszukiwania, przeglądania
od przodu do tyłu, lub od tylu do przodu, gdy
jest dużo operacji upperBound lub lowerBound.


    void sort() {
        for(TNODE node=min(), pos=RBT_NULL+1 ; !isNull(node) ; node=next(node), pos++ ) {
            if( node == pos )
                continue;

            std::swap( nodes[node] , nodes[pos] );

            if( nodes[node].parent == nodes[pos].parent ) {
                std::swap( nodes[nodes[node].parent].left , nodes[nodes[node].parent].right );
                if( nodes[node].left  != RBT_NULL ) nodes[nodes[node].left ].parent = node;
                if( nodes[node].right != RBT_NULL ) nodes[nodes[node].right].parent = node;
                if( nodes[pos ].left  != RBT_NULL ) nodes[nodes[pos ].left ].parent = pos ;
                if( nodes[pos ].right != RBT_NULL ) nodes[nodes[pos ].right].parent = pos ;
            } else if( nodes[node].parent == node ) {
                if( nodes[pos].left == pos ) {
                    std::swap( nodes[pos].left , nodes[node].parent );
                    if( nodes[pos ].right != RBT_NULL ) nodes[nodes[pos ].right].parent = pos ;
                } else {
                    std::swap( nodes[pos].right , nodes[node].parent );
                    if( nodes[pos].left != RBT_NULL ) nodes[nodes[pos].left].parent = pos ;
                }
                if( nodes[node].left  != RBT_NULL ) nodes[nodes[node].left ].parent = node;
                if( nodes[node].right != RBT_NULL ) nodes[nodes[node].right].parent = node;
                if( nodes[pos].parent != RBT_NULL ) {
                    if( nodes[ nodes[pos].parent ].left == node ) {
                        nodes[ nodes[pos].parent ].left = pos;
                    } else {
                        nodes[ nodes[pos].parent ].right = pos;
                    }
                }
            } else if( nodes[pos].parent == pos ) {
                if( nodes[node].left == node ) {
                    std::swap( nodes[node].left , nodes[pos].parent );
                    if( nodes[node].right != RBT_NULL ) nodes[nodes[node].right].parent = node ;
                } else {
                    std::swap( nodes[node].right , nodes[pos].parent );
                    if( nodes[node].left != RBT_NULL ) nodes[nodes[node].left].parent = node ;
                }
                if( nodes[pos].left  != RBT_NULL ) nodes[nodes[pos].left ].parent = pos;
                if( nodes[pos].right != RBT_NULL ) nodes[nodes[pos].right].parent = pos;
                if( nodes[node].parent != RBT_NULL ) {
                    if( nodes[ nodes[node].parent ].left == pos ) {
                        nodes[ nodes[node].parent ].left = node;
                    } else {
                        nodes[ nodes[node].parent ].right = node;
                    }
                }
            } else {
                if( nodes[node].left  != RBT_NULL ) nodes[nodes[node].left ].parent = node;
                if( nodes[node].right != RBT_NULL ) nodes[nodes[node].right].parent = node;
                if( nodes[pos ].left  != RBT_NULL ) nodes[nodes[pos ].left ].parent = pos ;
                if( nodes[pos ].right != RBT_NULL ) nodes[nodes[pos ].right].parent = pos ;
                if( nodes[node].parent != RBT_NULL ) {
                    if( nodes[ nodes[node].parent ].left == pos ) {
                        nodes[ nodes[node].parent ].left = node;
                    } else {
                        nodes[ nodes[node].parent ].right = node;
                    }
                }
                if( nodes[pos].parent != RBT_NULL ) {
                    if( nodes[ nodes[pos].parent ].left == node ) {
                        nodes[ nodes[pos].parent ].left = pos;
                    } else {
                        nodes[ nodes[pos].parent ].right = pos;
                    }
                }

            }

            if( root == node )
                root = pos;
            else if( root == pos )
                root = node;

            node = pos;
        }
    }

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#30388

From"M.M." <mmarszik@gmail.com>
Date2017-08-21 04:30 -0700
Message-ID<e4372bd5-e117-46dc-9dc7-213a0b306cd0@googlegroups.com>
In reply to#30355
On Friday, August 18, 2017 at 10:51:33 AM UTC+2, bartekltg wrote:
> On Thursday, August 17, 2017 at 11:04:34 PM UTC+2, M.M. wrote:
> > 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ę.
> 
> Za szybko nie będe mógł poczytać. 
> Jak to nie tajne:), wrzuć gdzies całość (włacznie z drzewkiem).

Jak obiecałem, wrzuciłem drzewko w wersji tablicowej i z sortowaniem na bloga:

https://drzewa-czerwono-czarne.blogspot.com/p/kod-zrodowy-c-drzewa-czerwono-czarne.html

Pozdrawiam

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web