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

do góry

W dniu 2012-10-14 23:43, kenobi pisze:

>>
> histogramy maka tu po 256KB wiec o jakich 40MB mowa,

Na tablice pomocniczą.

unsigned int * temp = new unsigned int [n];

Sortowanie pozycyjne wymaga n dodatkowej pamięci.

a n było 10 000 000

> jest to poniekad przypuszczam algorytm najszybszy
> z wszystkich omawianych :U

Ale nie jest to algorytm uniwersalny.


A, jednak istnieją wersje sortowania pozycyjnego
dziające się w odwrotnej kolejności.
Ale nadal dziwnie przypominają kubełkowe.



pzdr
bartekltg

do góry

W dniu poniedziałek, 15 października 2012 00:01:17 UTC+2 użytkownik bartekltg
napisał:
> W dniu 2012-10-14 23:43, kenobi pisze:
>
>
>
> >>
>
> > histogramy maka tu po 256KB wiec o jakich 40MB mowa,
>
>
>
> Na tablice pomocniczą.
>
>
>
> unsigned int * temp = new unsigned int [n];
>
>
>
> Sortowanie pozycyjne wymaga n dodatkowej pamięci.
>
>
>
> a n było 10 000 000
>
>
>
> > jest to poniekad przypuszczam algorytm najszybszy
>
> > z wszystkich omawianych :U
>
>
>
> Ale nie jest to algorytm uniwersalny.
>
>
>
>
>
> A, jednak istnieją wersje sortowania pozycyjnego
>
> dziające się w odwrotnej kolejności.
>
> Ale nadal dziwnie przypominają kubełkowe.
>
>
>
>
>
wyniki moich pomiarow w stosunku do qsorta z clib

//tab_size qsort komb-hist

//100 20 u 800 u
//1 tys 250 u 1000 u
//10 tys 3.3 m 1.2 m
//100 tys 40 m 20 m
//1 mln 600 m 350 m
//10 mln 6.2 s 3.9 s

niecale 2 razy szybsze :/ no ale to jest
wersja kombinowana, oryginalna na podstawowym
zakresie (ktory nie jest taki maly do miliona
uciagnie itp) pewnie bylaby ze 4 razy szybsza
wiec ogolnie z 10 razy szybsza od quicksorta

do góry

W dniu 2012-10-15 00:43, kenobi pisze:

> wyniki moich pomiarow w stosunku do qsorta z clib
>
> //tab_size qsort komb-hist

Nie napisałeś, czym jest komb-hist.
Jakiś kod, skoro już się bawimy.

>
> //100 20 u 800 u
> //1 tys 250 u 1000 u
> //10 tys 3.3 m 1.2 m
> //100 tys 40 m 20 m
> //1 mln 600 m 350 m
> //10 mln 6.2 s 3.9 s
>
> niecale 2 razy szybsze :/ no ale to jest

Jakby było uniwersalne (czyli wersja "kombinowana")
i 20 razy szybsze, byłoby w bibliotekach.

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 23:28:06 UTC+2 użytkownik bartekltg napisał:
>
> Dopiero co się szkicem tego algorytmu zachwycałeś.
> Od szkicu do implementacji droga wiedzie przez
> nieraz upierdliwe szczegóły;)
A czasem takze przez długie lata :) Wiele razy zdarzylo mi sie wpasc w
pulapke, gdy bazowalem na glownej ideii algorytmu, a szczegoly wydawaly
sie oczywiste :)

do góry

W dniu poniedziałek, 15 października 2012 00:54:24 UTC+2 użytkownik bartekltg
napisał:
> W dniu 2012-10-15 00:43, kenobi pisze:
>
>
>
> > wyniki moich pomiarow w stosunku do qsorta z clib
>
> >
>
> > //tab_size qsort komb-hist
>
>
>
> Nie napisałeś, czym jest komb-hist.
> Jakiś kod, skoro już się bawimy.
>
>
komb-hist czyli kombinowany kasperski, (kasperki
kombinowany 2-pozycyjnie)

ten sam kod

void sortowanie_histogramowe_kombinowane_2pozycyjnie_test
()
{


for (int i=0; i<histogram_size; i++) histogram[i] = 0;
for (int i=0; i<tab_size; i++) histogram[ tab[i] & 0xffff ] ++;
for (int i=1; i<histogram_size; i++) histogram[i] += histogram[i-1];

for (int i=0; i<tab_size; i++) temp[ --histogram[ tab[i] & 0xffff ] ] =
tab[i];

for (int i=0; i<histogram_size; i++) histogram[i]=0;
for (int i=0; i<tab_size; i++) histogram[ (temp[i]>>shift) ]++;
for (int i=1; i<histogram_size; i++) histogram[i]+=histogram[i-1];

for (int i=tab_size-1; i>=0; i--) tab[--histogram[ temp[i]>>shift ]] =
temp[i];


}


ew probowalem uzyc dwu histogramow i zliczac w jednej petli

for (int i=0; i<tab_size; i++)
{
int w = tab[i];
histogram[ w & 0xffff ] ++;
histogram2[ w >> 16 ] ++;
}

moze bylo drobine (1/40) szybsze (pojedyncze wyniki oscyluja
a nie mierzylem w petli)

a jak z wielokrotnym sortowaniem - np 8-pozycyjnym
dla stringow char[32] ? nie byloby to tez szybsze
dla 'zageszczonych' stringow ?


>
> >
>
> > //100 20 u 800 u
> > //1 tys 250 u 1000 u
> > //10 tys 3.3 m 1.2 m
> > //100 tys 40 m 20 m
> > //1 mln 600 m 350 m
> > //10 mln 6.2 s 3.9 s
>
> >
>
> > niecale 2 razy szybsze :/ no ale to jest
>
>
>
> Jakby było uniwersalne (czyli wersja "kombinowana")
>
> i 20 razy szybsze, byłoby w bibliotekach.
>
>
>
> pzdr
>
> bartekltg

do góry

Warto napisac wiecejpozycyjna metode ktora
by pozortowala struktury po calym sizeofie,
tak dla testu zeby zobaczyc jak to dziala

do góry

W dniu 2012-10-14 04:07, Edek Pienkowski pisze:
> Dnia Sat, 13 Oct 2012 18:46:59 -0700, M.M. napisal:
>
>> W dniu niedziela, 14 października 2012 03:39:26 UTC+2 użytkownik M.M. napisał:
>>> W dniu niedziela, 14 października 2012 03:05:18 UTC+2 użytkownik bartekltg
napisał:
>>> Czyli nawet dla 10 danych nie oplaca sie
>>> rozwinac petli - widac ze algorytm sort10 dziala wolniej
>>> niz selection.
>> Kurde zle zmierzylem czas :)
>
> A zadbałeś o locality kodu? Co ;) ?
> Z benchmarkami tak to już jest, łatwo coś przeoczyć.
>
>> To sie oplaca!!
>> A jaki wydajny jest sort z stla...
>
> A przepraszam, jaką masz opinię o twórcach STLa? Albo raczej
> implementacji czegoś, co ma taki sam interfejs, jak sami twierdzą?
> Przecież za schrzanione kontenery i algorytmy każdy by ich zjadł.
>
>> 873 859 809 800 667 561 440 421 260 148
>> selection time 0.420000s
>> 873 859 809 800 667 561 440 421 260 148
>> insertion time 0.310000s
>> 873 859 809 800 667 561 440 421 260 148
>> boubles time 0.300000s
>
> Ten wynik mnie trochę dziwi. (bubbles).

Heh - no właśnie - na to zwrócił uwagę jeden z prowadzących zajęcia.
Przypomniał najpierw o tym jak wieszał psy na tym sposobie sortowania, a
potem pokazał przewagę "bąbli" na małych ilościach danych. Wyjaśnił to
małym narzutem kodu, oraz faktem, że nawet w pesymistycznych warunkach
złożoność przy małych "n" jest porównywalna....


--
Kaczus
http://kaczus.republika.pl

do góry

przy tym nie daloby sie tego przepisac w wersji
na h++ i z druga petla w przod? (chwilowo troche nie mam humoru sie nad tym
zastanawic :/)

do góry

Ok, zastanowilem sie nat tym --h[] vs h[]++
i widze ze mozna przepisac na h[]++ ale wiazaloby
sie to z obnizaniem indeksu, wiec zapewne troche mniej poreczne

to skladanie sortowan powiedzmy ze tez akceptuje (wlasnie z tym wczesniej mialem
najwiekszy problem)

ale ciagle nie widze z czego wynika odwrocenie kolejnosci przebiegu po i w ostatnim
kopiowaniu?

do góry