W dniu niedziela, 14 października 2012 11:58:58 UTC+2 użytkownik bartekltg napisał:
> 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ł;)
>
>

w pierwszym przejsciu liczysz histogram, czyli
256 offsetow, w drugim wstawiasz wzgledem tych
ofsetow i masz zgrubnie posortowane, reszte
podobnie lub ew merge sortem bedzie potezny
speedup ;)

do góry

W dniu 2012-10-14 08:10, kenobi pisze:

> 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
>

http://www.vcskicks.com/five-element-sort2.php [c#]

A, jest w tym kodzie to, o czym mówiłem.
Używamy swapa aby zmniejszyć liczbę gałęzi
do liczby 'topologicznie rożnych'.

Jak wyglądają gałązki, można zobaczyć tutaj
http://wiki.tcl.tk/4118
Ale chyba nie zachęcam d głębszego analizowania;)

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 12:06:34 UTC+2 użytkownik kenobi napisał:
> W dniu niedziela, 14 października 2012 11:58:58 UTC+2 użytkownik bartekltg napisał:
>
> > 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ł;)
>
> >
>
> >
>
>
>
> w pierwszym przejsciu liczysz histogram, czyli
> 256 offsetow, w drugim wstawiasz wzgledem tych
> ofsetow i masz zgrubnie posortowane, reszte
> podobnie lub ew merge sortem bedzie potezny
> speedup ;)

no moze mergem to nie (choc bylby speedup
wzgledem czystego merge'a bo zaoszczedza mergowi
scalania tych 256 kawalkow) tylko lepiej dalej
kasperskim w petli - nie jest to juz to samo co
czysty TLA (by tak to nazwac) ale i tak masa
speedu

do góry

napisze za godzine jak cos zjem aby zobaczyc
ile linijek ma ten kod

do góry

W dniu niedziela, 14 października 2012 12:15:03 UTC+2 użytkownik kenobi napisał:
> napisze za godzine jak cos zjem aby zobaczyc
>
> ile linijek ma ten kod

polowa procedury bo musze cos skoczyc zjesc i pelna napisze pozniej

for(int i=0; i<max; i++)
hi[t[i]>>16]++; //kasperski 1 dla HI

// tutaj zsumowanie do tablicy offset (skipped, pozniej dopisze)

t2[off[t[i]>>16]+ t[i*0xffff]]++; // kasperski 2 dla LO w podzialach

// teraz przejachanie po t2 i odtworzenie z offsetu i zliczen w t2[i] juz
posortowanych wartosci

do góry

W dniu 2012-10-14 09:39, M.M. pisze:
> 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

Nie do końca, ale...*)
To trochę inne zagadnienia.
Zauważ, że posortowanie 5 elementów
wymaga 9 komparatorów. Czyli 9 porównań.
Wiemy, że wystarczy 7.

Sieć sortująca nie ma 'ifów' mogących
diametralnie zmienić działanie w zależności
od wyniku, może tylko porównywać pary
w ustalonej kolejności.

Po pierwszych 2 porównaniach możemy mieć wiedzę
postaci a<-b<-c lub a<-b->c i zależnie od tego
należy działć ciut inaczej.


Za to mają inna przewagę. Cześć porównan moze być
równoległa, więc głębokość wynosi (wg wiki) 5.
Wynik będzie w czasie wykonania 5 kolejnych porównań.
(tylko czasem wykona się dwa).

O, znalazłem ciekawą stronę.
http://pages.ripco.net/~jgamble/nw.html

http://jgamble.ripco.net/cgi-bin/nw.cgi?inputs=5&alg
orithm=batcher&output=svg

Zgadza się.

I teraz do naszego ale. Jest to ewidentnie gorsze rozwiązanie
niż algorytm optymalny, czy nawet przywoływany przez PK
Ford and Johnson Merge-Insertion Sort (który dla 10 elementów
ma optymalne 22 porównania). Hmm, a nawet insertsorta
z wyszukiwaniem binarnym.
user.it.uu.se/~fm/Courses/AA/2000/h6.ps

Za to jest znacznie prostszy.

I wykorzystuje 29 porównań
http://jgamble.ripco.net/cgi-bin/nw.cgi?inputs=10&al
gorithm=best&output=svg

Można więc pociągnąć Twój sposób z http://pastebin.com/RGhkx6u6

Mógłbyś użyć takiego ciągu (uwaga, zrobione automatycznie
z wyników podanych przez stronę). daj znać, czy przebija sort10;)

static inline void sort10_N( typs d[] ) {
sort( d[4] , d[9] );
sort( d[3] , d[8] );
sort( d[2] , d[7] );
sort( d[1] , d[6] );
sort( d[0] , d[5] );
sort( d[1] , d[4] );
sort( d[6] , d[9] );
sort( d[0] , d[3] );
sort( d[5] , d[8] );
sort( d[0] , d[2] );
sort( d[3] , d[6] );
sort( d[7] , d[9] );
sort( d[0] , d[1] );
sort( d[2] , d[4] );
sort( d[5] , d[7] );
sort( d[8] , d[9] );
sort( d[1] , d[2] );
sort( d[4] , d[6] );
sort( d[7] , d[8] );
sort( d[3] , d[5] );
sort( d[2] , d[5] );
sort( d[6] , d[8] );
sort( d[1] , d[3] );
sort( d[4] , d[7] );
sort( d[2] , d[3] );
sort( d[6] , d[7] );
sort( d[3] , d[4] );
sort( d[5] , d[6] );
sort( d[4] , d[5] );
}


A, stronka sama generuje takie 'swap macros'.

pzdr
bartekltg

do góry

W dniu 2012-10-14 10:35, kenobi pisze:
> tak wogole ten sort10 to mi wyglada
> na zahardkodowana wersje boubla,

Nazwijmy to przez grzecznośc selectionsortem
na swapach;)

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 12:10:32 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 08:10, kenobi pisze:
>
>
>
> > 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
>
> >
>
>
>
> http://www.vcskicks.com/five-element-sort2.php [c#]
>
>
>
> A, jest w tym kodzie to, o czym mówiłem.
>
> Używamy swapa aby zmniejszyć liczbę gałęzi
>
> do liczby 'topologicznie rożnych'.
>
>
>
> Jak wyglądają gałązki, można zobaczyć tutaj
>
> http://wiki.tcl.tk/4118
>
> Ale chyba nie zachęcam d głębszego analizowania;)
>
>
no ciekawe,wlasnie bylem ciekaw tych dwu rzeczy ile
linijek ma werskja z ifami ew ile przestawien

do góry

W dniu 2012-10-14 12:06, kenobi pisze:


> w pierwszym przejsciu liczysz histogram, czyli
> 256 offsetow, w drugim wstawiasz wzgledem tych
> ofsetow i masz zgrubnie posortowane, reszte
> podobnie lub ew merge sortem bedzie potezny
> speedup ;)


Całą idea i "prawdziwy speedup" wynika stąd,
że surtujemy _w odwrotnej kolejności_ algorytmem
stabilnym. najpierw posortujemy po niższym
bajcie. Ok. Teraz sortujemy po wyższym.
Jeśli jakieś dwie liczby mają taki sam bajt wyższy,
to nie zostanie zamieniona ich kolejność.
A, że był wcześniej posortowane po niższym,
to są posortowane po obydwu słownikowo.
koniec.

żadnych dodatkowych kontenerów, żadnych histogramów,
żadnego mergesorta nie wiadomo skąd.
Tylko dodatkowa tablica (stabilne sortowanie przez
zliczanie nie działą w miejscu) i wydajność;)

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 12:50:00 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 12:06, kenobi pisze:
>
>
>
>
>
> > w pierwszym przejsciu liczysz histogram, czyli
>
> > 256 offsetow, w drugim wstawiasz wzgledem tych
>
> > ofsetow i masz zgrubnie posortowane, reszte
>
> > podobnie lub ew merge sortem bedzie potezny
>
> > speedup ;)
>
>
>
>
>
> Całą idea i "prawdziwy speedup" wynika stąd,
>
> że surtujemy _w odwrotnej kolejności_ algorytmem
>
> stabilnym. najpierw posortujemy po niższym
>
> bajcie. Ok. Teraz sortujemy po wyższym.
>
> Jeśli jakieś dwie liczby mają taki sam bajt wyższy,
>
> to nie zostanie zamieniona ich kolejność.
>
> A, że był wcześniej posortowane po niższym,
>
> to są posortowane po obydwu słownikowo.
>
> koniec.
>
>
>
> żadnych dodatkowych kontenerów, żadnych histogramów,
>
> żadnego mergesorta nie wiadomo skąd.
>
> Tylko dodatkowa tablica (stabilne sortowanie przez
>
> zliczanie nie działą w miejscu) i wydajność;)
>
>

ok zastanowie sie, mozliwe (musze przemyslec chwile) - jesli tak to fajnie bo mozna
latwo uogolnic kasperskiego
- w kazdym razie widzisz pewnie ze kasperski/histogram jest to najszybsza metoda ;>

do góry