Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Jacek Marcin Jaworski Newsgroups: pl.comp.lang.c,pl.comp.programming,pl.comp.os.linux.programowanie Subject: testy-wyd-sort - Podsumowanie Followup-To: pl.comp.lang.c Date: Sun, 11 Aug 2024 23:24:53 +0200 Organization: Energo Kod Lines: 189 Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: individual.net MC4fXMCK5XCNkYkEFbx+1ww8nDi6J7P4sluejMQVMWk6dgkQ/d Cancel-Lock: sha1:kQawtDmRKTzsbNXwFZu3PLsL6i0= sha256:iahPBOCvPxl6bf/L8ubvO05/bPbb2UR2NBHrHLTvfrk= User-Agent: Mozilla Thunderbird Content-Language: pl-PL Xref: csiph.com pl.comp.lang.c:28832 pl.comp.programming:35001 pl.comp.os.linux.programowanie:2286 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.