> W dniu 07.05.2011 13:44, kenobi pisze:
> > jak rozumiem musialbym co ramke robic trzy sorty x,y,z i trzymac
> > wyniki w oodzielnych tablicach indeksow - a jaki to sort? quicksort?
> > ktos wie w ile milisekund da rade wyrobic sie z trzema sortami
> > tablicy np 10000 struktur ?
> Opłaca się sortować same wskaźniki - zamieniasz wtedy tylko pojedyncze
> słowa procesora a nie całe struktury.
>

no wiem - w moim przypadku inty-indeksy w tablicach - mysle
ze moze byc dosyc szybko, zobacze w swoim czasie

> Tu masz sprawozdanie, które popełniłem z kumplem na pierwszym roku:
> http://prowizorka.da.ru/~michoo/sprawozdanie.pdf
> Przy okazji na końcu masz porównanie o ile udało mi się ulepszyć
> heapsort kompilując go ręcznie - zajęło mi to 'tylko' ~tydzień
> projektowania "przy okazji" i 3 godziny kodowania w pociągu. A
> optymalizacje obejmowały m.i. testowania które zmienne i w jakiej
> kolejności umieścić pod [esp], [esp+4], [esp+8].

no super, aczkolwiek tam jest napisane ze quicksort wymaga
duzo pamieci, co chyba wogole nie jest prawda, nie pamietam
dokladnie, ale na co mialby wykorzystywac te pamiec, o ile
slabo pamietam nie potrzebuje jej prawie wcale

quicksort dzieli 'logarytmicznie' tak ze nawet poziomow
zaglebien w wywolaniach na stosie nie jest tak duzo: log2(N)

>

> --

> Pozdrawiam

> Michoo



--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

>
> quicksort dzieli 'logarytmicznie' tak ze nawet poziomow
> zaglebien w wywolaniach na stosie nie jest tak duzo: log2(N)
>
> >
>
tzn 'srednio' fakt zapomnialem o niewygodnych przypadkach

--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

W dniu 07.05.2011 21:52, g...@p...onet.pl pisze:
>>
>> quicksort dzieli 'logarytmicznie' tak ze nawet poziomow
>> zaglebien w wywolaniach na stosie nie jest tak duzo: log2(N)
>>
>>>
>>
> tzn 'srednio' fakt zapomnialem o niewygodnych przypadkach
>
Nie pamiętam już dokładnie - to było 3 lata temu, ale implementacja oidp
miała być "podręcznikowa z rekurencją" a ta wersja używa n dodatkowego
miejsca. W takiej sytuacji można użyć mergesort, który jest równie
złożony pamięciowo a stabilny i dobrze się zrównolegla. Dla porównania
heapsort, którego bardzo lubię, działa w miejscu.

--
Pozdrawiam
Michoo

do góry

> >> quicksort dzieli 'logarytmicznie' tak ze nawet poziomow
> >> zaglebien w wywolaniach na stosie nie jest tak duzo: log2(N)
> >>
> >>
> > tzn 'srednio' fakt zapomnialem o niewygodnych przypadkach
> >
> Nie pamiętam już dokładnie - to było 3 lata temu, ale implementacja oidp
> miała być "podręcznikowa z rekurencją" a ta wersja używa n dodatkowego
> miejsca. W takiej sytuacji można użyć mergesort, który jest równie
> złożony pamięciowo a stabilny i dobrze się zrównolegla. Dla porównania
> heapsort, którego bardzo lubię, działa w miejscu.
jak sie zastanowic quicksort nie jest
wcale taki dobry i defakto mozna by
przynajmniej poprobowac z liniowym
sortem na histogramie) - dla 10 tys log2 jest
13 (czyli jest to x13 wolniej) do tego jest
to dla rownomiernych podzialow a nie
wiem jak w przypadkach realnych wypaczen
moze jest jeszcze ze 2x wolniej) czyli
x20 powiedzmy - w liniowym trzebaby
pozaokraglac wspolrzedne i ograniczyc
przedzial np do 50 tys jest tez problem
ze skladowaniem zderzonych w histogramie
indeksow jako list no i pozniej z przeleceniem
histogramu ale powinno byc kilka razy
szybciej - choc problem z tym zawezonym
polem - moze metoda kombinowana sektory
i histogramsort


--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

> x20 powiedzmy - w liniowym trzebaby
> pozaokraglac wspolrzedne i ograniczyc
> przedzial np do 50 tys jest tez problem
> ze skladowaniem zderzonych w histogramie
> indeksow jako list no i pozniej z przeleceniem
> histogramu ale powinno byc kilka razy
> szybciej - choc problem z tym zawezonym
>zakresem

w sumie poniewaz w quicksorcie jest duzo
kosztownych swapow nie zdziwilbym sie
jakby bylo >10 razy szybciej - ale trzeba
poczekac az sprawdze - no i nie mozna
detektowac calej przestrzeni na floatach
tylko jakis sektor rzedu 20tys x 20tys x 20 tys


--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

> w sumie poniewaz w quicksorcie jest duzo
> kosztownych swapow nie zdziwilbym sie
> jakby bylo >10 razy szybciej - ale trzeba
> poczekac az sprawdze - no i nie mozna
> detektowac calej przestrzeni na floatach

ciekawe spostrzezenie ze z grubsza te
wszystkie log we wzorkach mozna
przetlumaczyc jako x15 (wolniej)
czyli ni jest to tak malo

(wlasnie sie zastanawiam kiedy ja
w zyciu ostatni raz czulem sie naprawde
(jako tako) fizycznie dobrze - w lipcu 2008 - przed tym
cholernym kleszczem - czy te czasy kiedys
wroca... bo od 3 lat pieklo pociecia i stalych
wewnetrznych jakby paralizow i poparzen)
mam totalnie przerabane


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

> w sumie poniewaz w quicksorcie jest duzo
> kosztownych swapow nie zdziwilbym sie
> jakby bylo >10 razy szybciej - ale trzeba
> poczekac az sprawdze - no i nie mozna
> detektowac calej przestrzeni na floatach

ciekawe spostrzezenie ze z grubsza te
wszystkie log we wzorkach mozna
przetlumaczyc jako x15 (wolniej)
czyli ni jest to tak malo

(wlasnie sie zastanawiam kiedy ja
w zyciu ostatni raz czulem sie naprawde
(jako tako) fizycznie dobrze - w lipcu 2008 - przed tym
cholernym kleszczem - czy te czasy kiedys
wroca... bo od 3 lat pieklo pociecia i stalych
wewnetrznych jakby paralizow i poparzen)
mam totalnie przerabane


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

nie, to byl lipiec 2007, swietnie mi sie
mieszkalo w poznanskiej dzielnicy ogrody
- 4 lata meki a to ciagle nie mija

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry