W dniu niedziela, 14 października 2012 01:08:13 UTC+2 użytkownik bartekltg napisał:
> Pamiętaj, że aby zadziałało należy
> zadbać, aby nasza podprocedura robiąca
> sortowanie przez zliczanie na wybranych bitach
> sortowaniem stabilnym. A zaczynać od najmniej
> znaczących bitów.

Tez by sie dalo od najbardziej znaczacych i
potem rekurencyjne dla dwoch pod-tablic.
Pozdrawiam

do góry

W dniu niedziela, 14 października 2012 00:54:35 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-13 23:56, PK pisze:
>
> > On 2012-10-13, M.M. <m...@g...com> wrote:
>
> >> Algorytmy sortowania o asymptotycznej zlozonosci n^2 moga byc szybsze
>
> >> od n*log(n) dla malych n, a to z powodu stalego narzutu. Jesli w petelce
>
> >> trzeba posortowac np. miliard razy po 20 liczb, to warto sprawdzic czy
>
> >> algorytm kwadratowy nie wypadnie lepiej.
>
> >
>
> > Jeśli trzeba posortować miliard razy 20 liczb, to lepiej napisać
>
> > optymalny sort dla 20 liczb.
>
>
>
> Na pewno stosuje się (albo teoretykom wydaje się, że
>
> się stosuje, tzw matematyka stosowana) taki spacjalizowany
>
> algorytm dla 5. Dużo ifów:)
>
> Dlaczego dla 5? Bo w mamy algorytm magicznych piątek;)
>
>
>
> Dla 20 byłby już zbyt skomplikowany. Za duży.
>
>
>
> No, chyba, że miałeś na myśli coś typu insertionsort
>
> skompilowany na stale na 30, czy 5 razy posoruj
>
> piątki i 3 razy 'merge'.
>

a ma ktos moze jawny kod z ifami dla
pieciu liczb? przydaloby mi sie to -
ostatnio pisalem nawet cos takiego
przy sortowaniu wierzcholkow trojkata/quada
dla potrzeb rasteryzacji i nie bylo to mile -
przydaloby sie miec taki szablon dla paru liczb

do góry

W dniu niedziela, 14 października 2012 01:03:07 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 00:59, PK pisze:
>
> > On 2012-10-13, bartekltg <b...@g...com> wrote:
>
> >> Na pewno stosuje się (albo teoretykom wydaje się, że
>
> >> się stosuje, tzw matematyka stosowana) taki spacjalizowany
>
> >
>
> > Stosuje się w praktyce - zapewniam :).
>
> >
>
> >> algorytm dla 5. Dużo ifów:)
>
> >> Dlaczego dla 5? Bo w mamy algorytm magicznych piątek;)
>
> >>
>
> >> Dla 20 byłby już zbyt skomplikowany. Za duży.
>
> >
>
> > Duży to kwestia względna. Napisanie (wygenerowanie) nie kosztuje
>
> > zupełnie nic. Pozostaje kwestia rozmiaru programu, ale to nie
>
> > zawsze jest problem.
>
>
>
> Ale dla 20? Bez sztuczek to nam się nie tylko w cache,
>
> ale i w RAMie nie zmieści.
>
>
>
> Możesz powiedzieć coś więcej o tych praktycznych zastosowaniach,
>
> jak wygląda implementacji i do jakich liczb to się stosuje?
>
>
hehe, mi sie tez kojarzy jako if z 20ma poziomami zaglebbienia i 2^20 'klauzulami' na
koniec ;-) No ale nie wiem jak wygladalaby
(ile wierszy) optymalizowana wersja takiego ifu

do góry

W dniu niedziela, 14 października 2012 02:14:10 UTC+2 użytkownik Edek Pienkowski
napisał:
> Dnia Sat, 13 Oct 2012 16:25:09 -0700, M.M. napisal:
>
>
>
> > W dniu niedziela, 14 października 2012 00:59:41 UTC+2 użytkownik PK napisał:
>
> >> > algorytm dla 5. Dużo ifów:)
>
> >> > Dlaczego dla 5? Bo w mamy algorytm magicznych piątek;)
>
> >> > Dla 20 byłby już zbyt skomplikowany. Za duży.
>
> >> Duży to kwestia względna. Napisanie (wygenerowanie) nie kosztuje
>
> >> zupełnie nic. Pozostaje kwestia rozmiaru programu, ale to nie
>
> >> zawsze jest problem.
>
> > Moim zdaniem, na wspolczesnych procesorach, ktore maja duza roznica pomiedzy
>
> > dostepem do danych w cache i poza cache, bedzie jednak stanowilo problem.
>
> > Strzelam ze bedzie 3krotne spowolnienie liniowe z powodu rozmiaru programu.
>
> > Pozdrawiam
>
> > PS.
>
> > 20 danych to 512k instrukcji if i tyle samo instrukcji else?
>
>
>
> Pewnie w hardware nie ma tego typu problemu. Było wspomniane.
>
>
>
> A skoro mowa o wywoływanym miliard razy sortowaniu, mówimy o L1
>
> i branch prefiction. Procesor powinien mieć co najmniej kolejny
>
> poziom jak nie kilka już zasysany albo do L1 albo już wykonywany
>
> w core. Trzeba zmierzyć, ale L1<->L2 dzisiaj to lepiej niż 1e11 B/s,
>
> bo tyle to ma RAM. Policzyć tez by można:
>
> - przepustowośc to tak pi razy oko 1e6/1e12 = 5e-7
>
> - instrukcje n(n-1)/2 ot nie lepiej niż 20*19/2 / 3e9 =~ 200/3e9 ~= 6e-8
>
>

Co to dokladniej za obliczenia?
Ile obecne kompy maja zwykle L1 cache na
dane i kod ? ja na starym p4 mam 8 KB czyli
jest to bardzo malo,

do góry

W dniu niedziela, 14 października 2012 08:15:43 UTC+2 użytkownik kenobi napisał:
> hehe, mi sie tez kojarzy jako if z 20ma poziomami zaglebbienia i 2^20 'klauzulami'
na koniec ;-) No ale nie wiem jak wygladalaby
>
> (ile wierszy) optymalizowana wersja takiego ifu

Moze inspiracji nalezy szukac w sekcji "Optymalne sortowanie"
http://pl.wikipedia.org/wiki/Sie%C4%87_sortuj%C4%85c
a
Pozdrawiam

do góry

W dniu niedziela, 14 października 2012 03:47:00 UTC+2 użytkownik M.M. napisał:
> 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 :)
>
> To sie oplaca!!
>
> A jaki wydajny jest sort z stla...
>
>
>
> 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
>
> 873 859 809 800 667 561 440 421 260 148
>
> sort10 time 0.280000s
>
> 873 859 809 800 667 561 440 421 260 148
>
> qsort time 0.560000s
>
> 148 260 421 440 561 667 800 809 859 873
>
> stl::qsort time 0.280000s
>

:/ wywal wypalnianie tablicy i assert poza
petle i poza timer i podaj te wyniki dla
samych sortow w milionie petli - to bedzie
mowic znacznie wiecej

do góry

W dniu niedziela, 14 października 2012 09:56:16 UTC+2 użytkownik kenobi napisał:
> :/ wywal wypalnianie tablicy i assert poza
> petle i poza timer i podaj te wyniki dla
> samych sortow w milionie petli - to bedzie
> mowic znacznie wiecej
Wywalilem, niewiele to zmienilo, prawie nic.
Pozdrawiam.

do góry

W dniu niedziela, 14 października 2012 10:03:06 UTC+2 użytkownik M.M. napisał:
> W dniu niedziela, 14 października 2012 09:56:16 UTC+2 użytkownik kenobi napisał:
>
> > :/ wywal wypalnianie tablicy i assert poza
>
> > petle i poza timer i podaj te wyniki dla
>
> > samych sortow w milionie petli - to bedzie
>
> > mowic znacznie wiecej
>
> Wywalilem, niewiele to zmienilo, prawie nic.
>

jak nic jak milion razy odpalasz inicjowanie
i milion razy asserta - wywal _na pewno_
(sortowanie mozna raczej odpalac milion razy
na tych samych danych wejsciowych - zamiast
build moze wstaw tam na stale
tab[0]=78, tab[1]=925
itd by nie wplywalo na wyniki za bardzo )
- i podaj wyniki to pomysle nad tym :/

do góry

tak wogole ten sort10 to mi wyglada
na zahardkodowana wersje boubla,
zreszta ten twoj bouble to jest
bouble niejako optymalizowany
(i to chyba dwojako i przez to
ze urywa returnem i ze leci po
trojkacie

ja znam bouble w prymitywnej
formie typu

10 razy:
swipe_all_left()

do góry

W dniu 2012-10-14 05:38, M.M. pisze:
> W dniu niedziela, 14 października 2012 01:08:13 UTC+2 użytkownik bartekltg napisał:
>> Pamiętaj, że aby zadziałało należy
>> zadbać, aby nasza podprocedura robiąca
>> sortowanie przez zliczanie na wybranych bitach
>> sortowaniem stabilnym. A zaczynać od najmniej
>> znaczących bitów.
>
> Tez by sie dalo od najbardziej znaczacych i
> potem rekurencyjne dla dwoch pod-tablic.


Dwóch? liczymy porcjami powiedzmy po 8 bitów.
256 tablic w drugim kroku. 65536 w trzecim,
16777216 w czwartym (jeśli to inty, ostatnim).

Nie, to nie jest dobry pomysł;)

pzdr
bartekltg

do góry