-
X-Received: by 10.31.54.206 with SMTP id d197mr65449vka.26.1503003873221; Thu, 17 Aug
2017 14:04:33 -0700 (PDT)
X-Received: by 10.31.54.206 with SMTP id d197mr65449vka.26.1503003873221; Thu, 17 Aug
2017 14:04:33 -0700 (PDT)
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.cyf-kr.edu.pl!news.nask
.pl!news.nask.org.pl!news.unit0.net!peer03.am4!peer.am4.highwinds-media.com!pee
r03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!border1.nntp.dca1.
giganews.com!nntp.giganews.com!s6no1982000qtc.1!news-out.google.com!n39ni9692qt
f.1!nntp.google.com!v49no1275177qtc.0!postnews.google.com!glegroupsg2000goo.goo
glegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Thu, 17 Aug 2017 14:04:32 -0700 (PDT)
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=159.205.37.107;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 159.205.37.107
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <6...@g...com>
Subject: ciąg dalszy drzewa czerwono-czarne
From: "M.M." <m...@g...com>
Injection-Date: Thu, 17 Aug 2017 21:04:33 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 404
X-Received-Bytes: 14474
X-Received-Body-CRC: 927735712
Xref: news-archive.icm.edu.pl pl.comp.programming:211170
[ ukryj nagłówki ]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;
}
Następne wpisy z tego wątku
Najnowsze wątki z tej grupy
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
Najnowsze wątki
- 2025-01-31 kupujmy części
- 2025-01-30 pogromca ksiezy
- 2025-01-30 Warszawa => Data Engineer (Tech Lead) <=
- 2025-01-30 Czy WYNIESIENIE UE-posła Brauna z sali obrad UE-parlamentu stanowiło naruszenie jego immunitetu i godności?
- 2025-01-30 drukarka potrzebna
- 2025-01-30 Warszawa => QA Engineer (Quality Assurance) <=
- 2025-01-30 Łódź => Programista NodeJS <=
- 2025-01-30 Jest Trump prezydent jest Meta/FBook/Instagram ugoda za 25 mln. USD
- 2025-01-30 Gdańsk => Solution Architect (Java background) <=
- 2025-01-30 Zielona Góra => Senior Field Sales (system ERP) <=
- 2025-01-30 Błonie => Analityk Systemów Informatycznych (TMS SPEED) <=
- 2025-01-30 DeepSeek nie lubi gadać o polityce
- 2025-01-30 Błonie => Administrator systemów <=
- 2025-01-30 Gliwice => Business Development Manager - Network and Network Security
- 2025-01-30 Warszawa => Programista Full Stack (.Net Core) <=