Thread View: pl.comp.lang.c
1 messages
1 total messages
Started by Jacek Marcin Jaworski
Sun, 11 Aug 2024 21:24
testy-wyd-sort - Podsumowanie
Author: Jacek Marcin Jaworski
Date: Sun, 11 Aug 2024 21:24
Date: Sun, 11 Aug 2024 21:24
189 lines
10625 bytes
10625 bytes
testy-wyd-sort - Podsumowanie
autor: Jacek Marcin Jaworski
pseudonim: Energo Koder Atlant
utworzono: 2022-12-25
wersja: 290 z dnia: 2024-08-11
miejsce: Pruszcz Gd.
system: Linux (distro: Kubuntu)
program: LibreOffice
Spis treści
1 Streszczenie....................................................... 2
2 Wstęp.............................................................. 2
3 Porównanie wydajności alg. sort.................................... 2
4 Podsumowanie....................................................... 4
1 Streszczenie
Okazuje się, że w ks. p. Piotra Wróblewskiego pt. „Alg. i
struk. danych i techniki prog.”, wyd. 6, Helion, Gliwice,
2019r. przedstawił on implementację alg. sort. szybkiego (w j.
ang. quicksort) która jest bezużyteczna w realnym świecie. Moja
implementacja alg. sort. przez scalanie jest szybka jednak dla
liczb całkowitych działa wolniej od qSort i std::sort.
Natomiast przy porównywaniu napisów alg. gNormSort (z
rozpoznawaniem znaków Unicode i liczb) mój wielowątkowy alg.
enpro::gSortPrzezScalanie działa najszybciej spośród badanych
przeze mnie alg. sort.!
2 Wstęp
W ks. aut. Piotra Wróblewskiego przedstawiono kilka alg. sort.
Generalnie są one kl. O(N^2) lub O(N log N). Oczywiście
najciekawsze są te drugie, jednak nawet alg. kl. O(N^2) może
się przydać do sort. małych zbiorów danych jako rodz. opt. alg.
kl. O(N log N).
W ww. ks. w grupie alg. O(N log N) był zaprezentowany alg.
sort. szybkiego, alg. sort. przez kopcowanie i, alg. sort.
przez scalanie. Po za tym w bibl. w sys. Linuks dla j. C++ są
dostępne alg. sort.: Qt::qSort (bibl. Qt5) oraz std::sort (w
bibl. STL). Pojawia się zatem pyt.: Który z tych alg. jest
najszybszy i w czym jest on najszybszy? Poza tym wiedziałem, że
sort. szybkie jest wrażliwe na pewne dane wej. (potrafi się
zdegenerować do O(N^2)), natomiast sort. przez kopcowanie i
sort. przez scalanie dla każdych danych wej. gwarantuje O(N log
N). Aby wyjaśnić te sprawy zakodowałem gen-dane-test i
testy-wyd-sort.
3 Porównanie wydajności alg. sort.
Na podst. ks. p. Piotra Wróblewskiego zakodowałem alg.:
1. enpro::gSortPrzezWstawianie: nie ma go w poniższym
porównaniu, ale używają go enpro::gSortPrzezScalanieOpt i
enpro::gSortSzybkieOpt do sort. podtab. <= 5el.;
2. enpro::gSortPrzezScalanieOpt działający jednowątkowo, ale
do sort małych podtab. stosuje enpro::gSortPrzezWstawianie.
Metodą prób i błędów stwierdziłem, że stosowanie w nim
enpro::gSortPrzezWstawianie daje największe korzyści gdy
podtab. Jest <= 5el.;
3. enpro::gSortPrzezScalanie działający w wątkach dla zbiorów
pow. 1k el., wew. używa on enpro::gSortPrzezScalanieOpt;
4. enpro::gSortPrzezKopcowanie: działający jednowątkowo;
5. enpro::gSortSzybkie: działający jednowątkowo;
6. enpro::gSortSzybkieOpt: działający jednowątkowo, ale do
sort małych stosuje enpro::gSortPrzezWstawianie. Przyjąłem
taką samą wielk. podtab. Jak w alg.
enpro::gSortPrzezScalanieOpt czyli <= 5el. Jednak opt. alg.
enpro::gSortPrzezWstawianie miało niewielki wpływ na
wyniki.
Pow. alg. (z wyj. enpro::gSortPrzezWstawianie) porównałem z
dostarczanymi alg. Qt::qSort i std::sort.
Testy obejmowały sort. tab. liczb 64bit. (10k el.) i napisów
Unicode (kl. enpro::Napis pochodna od Qt::QString) (również 10k
el). UWAGA: Do sort. napisów używałem f. porównania
enpro::gNormSort która oprócz znaków Unicode uwzględnia liczby
(coś takiego było wprowadzone przez M$ w Internet Explorer 6).
Były 4 zestawy danych: tą samą powtarzającą się wart,
uporządkowane rosnąco, uporządkowane malejąco, nie
uporządkowane (przypadkowe).
Po uruchomieniu prog. testowego uzyskałem takie wyniki (% obl.
w Libre Office Calc):
cTabTakichSamychLiczb (10000el.): ms. %
enpro::gSortPrzezScalanieOpt (jednowątkowo) 12 400,00%
enpro::gSortPrzezScalanie (w wątkach) 5 166,67%
enpro::gSortPrzezKopcowanie 3 100,00%
enpro::gSortSzybkie 2025 67500,00%
enpro::gSortSzybkieOpt 2053 68433,33%
Qt::qSort 3 100,00%
std::sort 3 100,00%
cTabPosortLiczb (10000el.):
enpro::gSortPrzezScalanieOpt (jednowątkowo) 11 550,00%
enpro::gSortPrzezScalanie (w wątkach) 5 250,00%
enpro::gSortPrzezKopcowanie 46 2300,00%
enpro::gSortSzybkie 1992 99600,00%
enpro::gSortSzybkieOpt 2068 103400,00%
Qt::qSort 2 100,00%
std::sort 2 100,00%
cTabPosortOdwLiczb (10000el.):
enpro::gSortPrzezScalanieOpt (jednowątkowo) 12 600,00%
enpro::gSortPrzezScalanie (w wątkach) 8 400,00%
enpro::gSortPrzezKopcowanie 44 2200,00%
enpro::gSortSzybkie 3934 196700,00%
enpro::gSortSzybkieOpt 3982 199100,00%
Qt::qSort 2 100,00%
std::sort 2 100,00%
cTabPrzypadkLiczb (10000el.):
enpro::gSortPrzezScalanieOpt (jednowątkowo) 14 466,67%
enpro::gSortPrzezScalanie (w wątkach) 6 200,00%
enpro::gSortPrzezKopcowanie 49 1633,33%
enpro::gSortSzybkie 16 533,33%
enpro::gSortSzybkieOpt 15 500,00%
Qt::qSort 3 100,00%
std::sort 4 133,33%
cTabTakichSamychNapisow (10000el.):
enpro::gSortPrzezScalanieOpt (jednowątkowo) 344 312,73%
enpro::gSortPrzezScalanie (w wątkach) 110 100,00%
enpro::gSortPrzezKopcowanie 161 146,36%
enpro::gSortSzybkie 262107 238279,09%
enpro::gSortSzybkieOpt 266002 241820,00%
Qt::qSort 250 227,27%
std::sort 226 205,45%
cTabPosortNapisow (10000el.):
enpro::gSortPrzezScalanieOpt (jednowątkowo) 145 207,14%
enpro::gSortPrzezScalanie (w wątkach) 70 100,00%
enpro::gSortPrzezKopcowanie 613 875,71%
enpro::gSortSzybkie 56688 80982,86%
enpro::gSortSzybkieOpt 57064 81520,00%
Qt::qSort 178 254,29%
std::sort 171 244,29%
cTabPosortOdwNapisow (10000el.):
enpro::gSortPrzezScalanieOpt (jednowątkowo) 270 300,00%
enpro::gSortPrzezScalanie (w wątkach) 90 100,00%
enpro::gSortPrzezKopcowanie 666 740,00%
enpro::gSortSzybkie 73097 81218,89%
enpro::gSortSzybkieOpt 73107 81230,00%
Qt::qSort 179 198,89%
std::sort 165 183,33%
cTabPrzypadkNapisow (10000el.):
enpro::gSortPrzezScalanieOpt (jednowątkowo) 231 235,71%
enpro::gSortPrzezScalanie (w wątkach) 98 100,00%
enpro::gSortPrzezKopcowanie 816 832,65%
enpro::gSortSzybkie 416 424,49%
enpro::gSortSzybkieOpt 412 420,41%
Qt::qSort 146 148,98%
std::sort 154 157,14%
4 Podsumowanie
W przypadku testu sortowania przypadkowej tab. liczb 64Bit
wygrywa qSort jest on szybszy o 1/4 od kol. w zestawieniu alg.
std::sort.
W przypadku testu sortowania przypadkowych napisów wygrywa mój
alg. enpro::gSortPrzezScalanie (w wątkach) – działa on prawie
1/3 krócej niż kol. w zestawieniu Qt::qSort. W przypadku
sortowania złośliwych tab. napisów mój alg.
enpro::gSortPrzezScalanie jest nawet jeszcze szybszy od
konkurencji.
Alg. enpro::gSortPrzezKopcowanie działa wolniej niż najszybsze
alg., ale przynajmniej nie jest wrażliwy na złośliwe dane.
Alg. enpro::gSortSzybkie kompletnie się degeneruje dla tab.
takich samych wart. i dla posortowanych rosnąco. A dla wart.
posortowanych malejąco ten alg. działa 2x dłużej niż dla
posortowanych rosnąco. Oznacza to, że alg. sort. szybkiego ma
znaczenie jedynie akademickie i w realnych prog. jest nie do
zaakceptowania.
Alg. biblioteczne (Qt::qSort i std::sort) działają szybko na
typach prostych (takich jak liczby 64bit.), natomiast gdy f.
porównawcza jest złożona (tak jak w przyp. enpro::gNormSort)
ich wydajność spada.
Mój alg. enpro::gSortPrzezScalanie (w wątkach) jest wyraźnie
wolniejszy niż alg. bibl. w przypadku liczb 64bit, ale za to
wygrywa przy sort. napisów.
Moim zdaniem wysoka wyd. Qt::qSort i std::sort oznacza, że
działają one w wątkach.
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads