[xyz333]

#programowanie #cpp

Mam do wykonania pewien projekt i muszę użyć w nim bottom-up merge sorta.
Kiedy już wszystko napisałem, okazało się, że dzieję się coś dziwnego.

Kod obrazujący problem:
http://wklej.org/id/2252010/

Output:
http://wklej.org/id/2248991/
http://wklej.org/id/2252048/

I tutaj moje pytanie - dlaczego pierwsze sortowania wykonują się dłużej niż pozostałe?
Czasami jest to tylko pierwsze, czasami kilka, a czasami tak jak w wynikach podanych powyżej, ale zawsze, przynajmniej to pierwsze sortowanie zajmie więcej czasu. Wiem, że tablica może przypadkowo zostać wypełniona tak, że merge sort wolniej ją posortuje, ale tak się dzieje za każdym razem ( ͡° ʖ̯ ͡°)

[sylwke3100]

@xyz333: Tak swoją drogą czemu nie używasz biblioteki random?

[m.....r]

@xyz333: Bardzo dobry opis Mergesorta. Masz błąd w implementacji
for (left_start=0; left_start<n-1; left_start += 2*curr_size) zamiast for (int i = 0; i < N-n; i += n+n). Dodatkowo możesz wprowadzić CUTOFF czyli sortować małe tablice wydajniejszym algorytme np. insertion sort.

[xyz333]

@mackar O której linijce mówisz? Nie rozumiem też, czym w for (int i = 0; i < N-n; i += n+n) jest N?
edit: dzięki za opis

[m.....r]

@xyz333: W opisie masz plik MergeBU.java. Linijka 59 u ciebie powinna brzmieć for (left_start=0; left_start<n-curr_size; left_start += 2*curr_size)

[xyz333]

@mackar Dzięki, nie zdążyłem jeszcze całego przeczytać. Zmieniłem, ale nie dostrzegam praktycznej różnicy, czas wykonania po ustabilizowaniu to nadal ~3000µs

edit: output po edycji: http://wklej.org/id/2252970/

[m.....r]

@xyz333: Próbowałeś może flag kompilatora do optymalizacji? g++: -Ofast -O3

[xyz333]

@mackar Nie próbowałem wcześniej.
output po edycji: http://wklej.org/id/2253291/
tl;dr czas wykonywania spadł o ~1000µs, ale pierwsze sortowania nadal wykonują się dłużej od reszty

W outputach, które załączałem czas stabilizuje się po kilkunastu iteracjach. Czasami następuje to szybciej, ale jak pisałem, zawsze przynajmniej pierwszy wynik jest znacznie wyższy od pozostałych.

[m.....r]

@xyz333: Może wynika to z zarządzania pamięcią przez system. Ale muszę powiedzieć że i tak wyciągasz świetne czasy. U mnie minimalne czasy są na poziome 6000ms (╯︵╰,) No, ale zachciało się laptopa.

[xyz333]

@mackar

Też laptop, z niskonapięciowym prockiem na dodatek ( ͡° ʖ̯ ͡°)


I wygląda na to, że jest tak jak piszesz, nic innego nie przychodzi mi do głowy. Na stacku też cisza, ktoś wspomniał o https://en.wikipedia.org/wiki/Branch_predictor ale nie wiem jak to ma się do mojego problemu.
Dzięki za pomoc w każdym razie mirku ( ͡º ͜ʖ͡º)