Wibowit

  1. Senior Scala Developer
Wibowit
2014-04-17 19:16

Mój nowy projekt (mam nadzieję, że nie umrze szybko :) ):
https://github.com/tarsa/SortingAlgorithmsBenchmark

Celem jest porównanie wydajności różnych algorytmów sortujących i ich wariacji. Porównanie ma brać pod uwagę różne rodzaje sortowań (przez porównania i/ lub klasyfikację), różne charakterystyki danych wejściowych (wraz z różnymi stopniami powtarzalności kluczy), różne typy danych (szybkie lub długie do porównania), różną wielkość danych wejściowych (mieszczące się w L1, L2, L3, całym RAMie), itd Docelowo wyniki wydajności mają być zebrane i wyplute w JSONie, który potem ma być wejściem dla innego programu przerabiającego go na ludzką postać.

Jak na razie zacząłem od sortowania przez kopcowanie. Zaimplementowałem między innymi "sklastrowany" heapsort, czyli duży kopiec z małych kopców. Motywacją było zmniejszenie ilości osobnych dostępów do pamięci RAM. W sumie to się chyba udało, ale za to problemem jest zwiększona ilość obliczeń, wobec czego zysk wydajnościowy jest mizerny albo jest nawet regres. Obecnie pracuję nad hybrydową wersją heapsorta, czyli klasyczny kopiec o względnie małym rozmiarze (co powinno zmniejszyć mocno narzut obliczeniowy) + reszta danych ułożona w klastrach na niższych poziomach (co powinno zachować niską ilość osobnych dostępów do RAMu). Do tego klastry mają mieć rozmiar będący potęgą dwójki co ma zmniejszyć narzut obliczeniowy.

Jeszcze skopiuję komentarz który napisałem dla @MSM:
jest dużo do zrobienia zanim zrobi się z tego coś ciekawego. jak na razie siedzę nad sortowaniem przez kopcowanie. w kolejce są wariacje quicksorta, mergesorta, radixsorta, etc mam pewne pomysły dotyczące np mergesorta N-drożnego z kopcem wierzchołków czy np sortowanie kubełkowe na samych porównaniach elementów (przez wstępne sklasyfikowanie elementów rzutując je na jeden z N przedziałów, przez co potem można sortować przedziały i zagłębić się rekurencyjnie). lub np insertion sort z wykorzystaniem instrukcji wektorowych

vpiotr

@Wibowit: przenieś liczenie czasu trochę wyżej, cout w środku może powodować niemiarodajne wyniki (clock() - clockz).