W dniu niedziela, 14 października 2012 23:28:06 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 22:57, kenobi pisze:
>
> > W dniu niedziela, 14 października 2012 22:51:46 UTC+2 użytkownik kenobi napisał:
>
> >> ...użytkownik kenobi napisał:
>
>
>
>
>
> >>> co tu robi to --h ? jest na pewno dobrze?
>
>
>
> Na pewno jest dobrze.
>
>
>
> W h trzymasz liczbę wystąpień.
>
>
>
> Pod h[0] masz liczbę zer, pod h[1] liczbę jedynek
>
>
>
> Robisz sumy częściowe
>
> teraz pod h[0] nadal masz liczbę zer,
>
> ale pod h[1] liczbę zer i jedynek. pod h[2] liczbe zer,
>
> jedynek i dwójek.
>
>
>
> Ta na co pokazuje temp[ h[2] ] ?
>
> pokazuje na pierwsze miejsce _po_ ostatniej dwójce.
>
> Czyli ostatnia dwójka powinna znaleśc się na miejscu
>
> o jeden wcześniej.
>
> Robimy --h[2], pod wynikiem wkłądamy co trzeba.
>
>
>
> h pełni rolę _ruchomych_ wskaźników pokazujących,
>
> gdzie układać daną liczbę.
>
>
>
> Ok, przyznaje, nie jest to wersja edukacyjna,
>
> i zawiera trochę 'chackierskich przedwczesnych
>
> optymalizacji' i skrótowe konstrukcje.
>
> Dopiero co się nimi zachwysałeś
>
>
>
> być może
>
> temp[--h[(unsigned short)tab[j]]]=tab[j];
>
> ->
>
> kategoria = (unsigned short)tab[j];
>
> --h[kategoria]; //przesuwamy wskażnik tablicy dla elementow kategorii
>
> kategoria
>
> indeks = h[kategoria];
>
> temp[indeks] = tab[j]
>
>
>
> byłaby czytelniejsza;)
>
>
>
>
>
> >> nie rozumiem tego zlozenia, jak sortowanie tego
>
> >>
>
> >> co bylo posortowane po niskiej polowie po wysokiej czesci zlozy sie tak by
wszystko bylo ok?
>
>
>
> _Sortowanie stabilne_. Jeśli w drugim sortowaniu dwa elementy są takie
>
> same, to ich względna kolejność pozostanie taka sama jak po pierwszym.
>
>
>
> > w kazdym razie jesli to nie ma bledu i dziala
>
>
>
> Nie ma, działa.
>
>
>
> > to jest to sprytny kawalek kodu - dziwne jednak jakoby to mialo byc tylko 2-3
razy szybsze,
>
>
>
> Bo tu przelatujemy po dużej tablicy 6 razy, a w qsorcie
>
> log(N) razy. Log2(10^7) = 23 (tak naprawdę mniej, bo
>
> końcówkę robi się inaczej, a do tego działa się bardziej
>
> 'lokalnie', co jest szybsze).
>
>
>
> Dopiero co się szkicem tego algorytmu zachwycałeś.
>
> Od szkicu do implementacji droga wiedzie przez
>
> nieraz upierdliwe szczegóły;)
>
>
>
> Drzewa AVL są w idei super. Ale weź na szybko zaimplementuj
>
> równoważenie.
>
>
>
> > new mona wyrzucic i zrobic histogramy na statycznych tablicach
>
>
>
> Statyczna tablica na 40MB?
>
>
>
> To nie jest nawet zły pomysł. To głupi pomysł.
>
>
>
> Zrobiłem wersję z dodatkowym parametrem, buforem tworzonym
>
> raz na zewnątrz (poza licznikiem czasu) i przekazywanym do środka.
>
> Różnice były zbyt małe by warto było o nich wspominać,
>
> więc nawet nie pisałem.
>
>
histogramy maka tu po 256KB wiec o jakich 40MB mowa,
szkoda ze tylko 2-3 razy szybsze :/ oryginalna pojedyncza
wersja dla mniejszych zakrezsow np do miliona pewnie
wiecej szybsza,
jak to dziala a chyba dziala (testuje wlasnie ) to jest
wlasnie to o czym mowilem i to o co mi chodzilo nawet
lepiej jak mowilem sklecone niz myslalem - tak ze
jest to poniekad przypuszczam algorytm najszybszy
z wszystkich omawianych :U