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.

do góry