eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programming › ciąg dalszy drzewa czerwono-czarne
Ilość wypowiedzi w tym wątku: 4

  • 1. Data: 2017-08-17 23:04:32
    Temat: ciąg dalszy drzewa czerwono-czarne
    Od: "M.M." <m...@g...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;
    }


  • 2. Data: 2017-08-18 10:51:31
    Temat: Re: ciąg dalszy drzewa czerwono-czarne
    Od: bartekltg <b...@g...com>

    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


  • 3. Data: 2017-08-18 11:11:41
    Temat: Re: ciąg dalszy drzewa czerwono-czarne
    Od: "M.M." <m...@g...com>

    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



  • 4. Data: 2017-08-21 13:30:56
    Temat: Re: ciąg dalszy drzewa czerwono-czarne
    Od: "M.M." <m...@g...com>

    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-zr
    odowy-c-drzewa-czerwono-czarne.html

    Pozdrawiam

strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: