W dniu 2012-10-14 16:06, PK pisze:

> Absolutnie nie jest prawdą, że algorytm optymalny musi być najszybszy
> na konkretnej maszynie. Nie jest nawet prawdą, że szybszy jest
> algorytm z mniejszą złożonością obliczeniową :).

Ale tego to nawet najzaciętsi teoretycy nie twierdzą:)

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 11:58:58 UTC+2 użytkownik bartekltg napisał:

> 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ł;)
A jakby po jednym bicie brać a nie po osmiu?
Pozdrawiam

do góry

W dniu 2012-10-14 12:42, bartekltg pisze:

> 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

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


Napisałem skrypcik, który ściągnął 'Best' i 'Batcher's Merge-Exchange',
wybrał ten z mniejszą liczbą porównań i przerobił na c++.

Wyniki: [na dole]

Jest to szybsze od klasycznych alg aż do 11 elementów.
Potem gwałtownie zwalnia.
Nie do końca odpowiada to skokom liczby porównań
(35 do 39). Pewnie program robi się 'za duży'.

A, kod: http://pastebin.com/qmzqfiHK
:D

pzdr
bartekltg


Czasy, [n, powtorzen, T_insert, T_select, T_sieciowy]
2, 24999999, 196.000000, 284.000000 210.000000 ;
3, 11111110, 179.000000, 223.000000 153.000000 ;
4, 6249999, 157.000000, 192.000000 134.000000 ;
5, 3999999, 142.000000, 180.000000 116.000000 ;
6, 2777777, 140.000000, 184.000000 105.000000 ;
7, 2040816, 130.000000, 191.000000 99.000000 ;
8, 1562499, 120.000000, 197.000000 94.000000 ;
9, 1234567, 110.000000, 198.000000 94.000000 ;
10, 999999, 102.000000, 195.000000 86.000000 ;
11, 826446, 95.000000, 190.000000 82.000000 ;
12, 694444, 89.000000, 183.000000 168.000000 ;
13, 591715, 85.000000, 178.000000 183.000000 ;
14, 510204, 80.000000, 174.000000 171.000000 ;
15, 444444, 77.000000, 170.000000 164.000000 ;
16, 390624, 73.000000, 165.000000 153.000000 ;
17, 346020, 70.000000, 161.000000 174.000000 ;
18, 308641, 67.000000, 157.000000 172.000000 ;
19, 277008, 65.000000, 155.000000 172.000000 ;
20, 249999, 63.000000, 151.000000 165.000000 ;
22, 206611, 59.000000, 146.000000 159.000000 ;
24, 173611, 57.000000, 140.000000 148.000000 ;
26, 147928, 54.000000, 136.000000 145.000000 ;
28, 127550, 52.000000, 132.000000 138.000000 ;
30, 111111, 50.000000, 129.000000 132.000000 ;
32, 97656, 48.000000, 126.000000 124.000000 ;

do góry

W dniu 2012-10-14 17:58, M.M. pisze:
> W dniu niedziela, 14 października 2012 11:58:58 UTC+2 użytkownik bartekltg napisał:
>
>> 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ł;)
> A jakby po jednym bicie brać a nie po osmiu?

I po firowemu ładować do pomocniczych tablic,
zamiast użyć wersji stabilnej?
Będzie o 2^7 raza gorzej, musisz przecież zapamiętać
wszytko, poza jednym bitem, zamiast wszytko poza 8 bitami.

Zresztą, te całe rozważania są mało sensowne:)

pzdr
bartekltg

do góry

W dniu 2012-10-14 16:42, Michoo pisze:
> On 14.10.2012 13:56, bartekltg wrote:
>>
>> Zrozum, że to legenda zrobiona na ignorancji autora.
> Autor zrobił jakiś dziwne kombinacje z tym qsortem - prawdopodobnie użył
> "naiwną" implementację i jeszcze spreparował dane:
>
> Przetestowałem std::sort na cyrixie@133MHz (60MB ram) i geodzie@400MHz
> (256MB ram)
>
> sortowanie miliona:
> 7.1s/2.6s
> sortowanie 10 milionów:
> -84.6s/31s
>
> (btw: counting sort miliona (z zakresem 0-mln) na cirixie trwa 1.6s - 5x
> różnica)
>
> A on podobno na Athlonie, procesorze pracującym z ponad 1GHz miał czasy
> 3.6s/300s
>
> ktoś tu najzwyczajniej w świecie robi czytelnika w *.

A może to rzeczywiście był najlepszy qsort jaki byl w stanie napisac?


> Do tego popełnia dość istotny błąd rzeczowy:
>> Actually, the amount of required memory is Cmem = N_VAL*sizeof(cell),
>> where N_VAL is the number of allowed values
>
> Well, w zaprezentowanej implementacji po lekkich poprawkach N_VAL może
> być max(data)-min(data). Np posortujmy wartości ze zbioru
> (10-100)\/(2^30-2^30+5); No chyba, że autor zakłada użycie jakiejś
> sterty/drzewa jako hashmapy...


Można do zamiast tablicy zliczającej użyć zrównoważonego drzewa
zawierającego, poza liczbą jako kluczem, krotność wystąpienia.

Jeśli tablica ma długość N, i znajduje się w niej D różnych wartości,
taki algorytm zadziała w czasie N*log(D).

Znów w przyrodzie nic nie ginie;)


> Sugestia użycia sparse table też imo zakłada o kiepski żart. (Genialny
> algorytm sortowania, który czasami się wywala z OOM-exception.)

:)

>> In particular, sorting data belonging to the range of [0; 1,000,000]
>> will require no more than 4 MB of memory, a rather insignificant amount.
>
> I to jest imo jedyny sensowny wniosek z całego rozdziału - dane LICZBOWE
> (a rzadko sortujemy same liczby, częściej jednak struktury danych) z
> małego zakresu opłaca się sortować przez zliczanie.


Struktury tu nic nie przeszkadzają. Byle pole, po którym sortujemy
było zmienną dyskretną (cłkowitą) i miała niewielki zakres.


pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 18:12:59 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 17:58, M.M. pisze:
>
> > W dniu niedziela, 14 października 2012 11:58:58 UTC+2 użytkownik bartekltg
napisał:
>
> >
>
> >> 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ł;)
>
> > A jakby po jednym bicie brać a nie po osmiu?
>
>
>
> I po firowemu ładować do pomocniczych tablic,
>
> zamiast użyć wersji stabilnej?
>
> Będzie o 2^7 raza gorzej, musisz przecież zapamiętać
>
> wszytko, poza jednym bitem, zamiast wszytko poza 8 bitami.
>
>
>
> Zresztą, te całe rozważania są mało sensowne:)
>
>

Imo np przy sortowaniu miliona intow najpierw
nalezy mahnac histogram po wiekszj ilosci
bitow (niz polowa) np 20 czy 22 (histogram o
milionie czy 4 milionach wpisow ) bedzie
on srednio mial 1 lub 1/4 elementu na rekord
a jakby trafilo sie wiecej to beda to
juz liczby z mniejszego zakresu (4tys lub
1 tys)
Zaleta nierownego podzalu jest to ze
posortowane listy sa krotki i maja maly
zakres

Mozesz powiedziec jak to widzisz inaczej,
troche nie che mi sie pisac tego przykladu
i testu ale jak odpoczne to moze trzasne

do góry

W dniu niedziela, 14 października 2012 12:42:36 UTC+2 użytkownik bartekltg napisał:
> 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[] ) {

No to jeszcze dwie wersje i sprawiedliwe aserty.

http://pastebin.com/496ZPcbh

Na moim kompie/kompilatorze takie wyniki:

926 802 712 664 475 408 236 127 112 101
selection time 4.130000s
926 802 712 664 475 408 236 127 112 101
insertion time 2.920000s
926 802 712 664 475 408 236 127 112 101
bubbles time 2.790000s
926 802 712 664 475 408 236 127 112 101
sort10 time 2.280000s
926 802 712 664 475 408 236 127 112 101
sort10_N time 2.440000s
926 802 712 664 475 408 236 127 112 101
sort10_M time 2.830000s
926 802 712 664 475 408 236 127 112 101
qsort time 5.660000s
926 802 712 664 475 408 236 127 112 101
std::sort time 3.160000s

Pozdrawiam

P.S.
Jak sie przyjrzec uwaznie, to faktycznie sort10 jest
najbardziej podobne do bubble z rozwinietmi petlami.

do góry

W dniu 2012-10-14 18:27, kenobi pisze:

> Imo np przy sortowaniu miliona intow najpierw
> nalezy mahnac histogram po wiekszj ilosci
> bitow (niz polowa) np 20 czy 22 (histogram o

Twoje IMO jest w błędzie.

> milionie czy 4 milionach wpisow ) bedzie
> on srednio mial 1 lub 1/4 elementu na rekord
> a jakby trafilo sie wiecej to beda to
> juz liczby z mniejszego zakresu (4tys lub
> 1 tys)
> Zaleta nierownego podzalu jest to ze
> posortowane listy sa krotki i maja maly
> zakres

A teraz wymyśliłeś sortowanie kubełkowe.
Weź przeczytaj te 3 teksty w wikipedii,
sortowanie przez wstawianie
sortowanie pozycyjne
sortowanie kubelkowe

Wszytko się magicznie rozjaśni.


> Mozesz powiedziec jak to widzisz inaczej,
> troche nie che mi sie pisac tego przykladu
> i testu ale jak odpoczne to moze trzasne

Widzę to tak, jak na wiki. Wszystkie te algorytmy
kiedyśtam implementowałem.

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 18:31:17 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 18:27, kenobi pisze:
>
>
>
> > Imo np przy sortowaniu miliona intow najpierw
>
> > nalezy mahnac histogram po wiekszj ilosci
>
> > bitow (niz polowa) np 20 czy 22 (histogram o
>
>
>
> Twoje IMO jest w błędzie.
>
>
>
> > milionie czy 4 milionach wpisow ) bedzie
>
> > on srednio mial 1 lub 1/4 elementu na rekord
>
> > a jakby trafilo sie wiecej to beda to
>
> > juz liczby z mniejszego zakresu (4tys lub
>
> > 1 tys)
>
> > Zaleta nierownego podzalu jest to ze
>
> > posortowane listy sa krotki i maja maly
>
> > zakres
>
>
>
> A teraz wymyśliłeś sortowanie kubełkowe.
>
> Weź przeczytaj te 3 teksty w wikipedii,
>
> sortowanie przez wstawianie
>
> sortowanie pozycyjne
>
> sortowanie kubelkowe
>
>
>
> Wszytko się magicznie rozjaśni.
>
>
>
>
>
> > Mozesz powiedziec jak to widzisz inaczej,
>
> > troche nie che mi sie pisac tego przykladu
>
> > i testu ale jak odpoczne to moze trzasne
>
>
>
> Widzę to tak, jak na wiki. Wszystkie te algorytmy
>
> kiedyśtam implementowałem.
>

jak rozumiesz co mowie to moglbys sie
do tego odniesc

to inne pytanie ;) jakim algorytmem postortowalbys
1) milion unsigned shortow
2) milion unsigned intow ?

do góry

W dniu 2012-10-14 18:45, kenobi pisze:

>
> jak rozumiesz co mowie to moglbys sie
> do tego odniesc

Ty nie masz zamiaru czytać (i to od paru
postów i chyba 2 dni) to ja nie będę się
produkował i przepisywał podręcznika.

Załapałeś counting sorta. Chcesz go rozwinąć,
ale bujasz się między stworzeniem z niego radix
sorta (czyli kilkakrotnie przez zliczanie)
i kubełkowego.


> to inne pytanie ;) jakim algorytmem postortowalbys
> 1) milion unsigned shortow
> 2) milion unsigned intow ?

Zależy od warunków. W normalnych: std::sort().

W jakiś specyficznych, gdy to jest ważne
i rzeczywiście tam siedzi wąskie gardło
algorytmu, w przypadku [1] dałbym przez zliczanie
(zwłaszcza, że nie wymagasz stabilności!),
a w [2] zastanowiłbym się nad pozycyjnym
(2 razy przez zliczanie).

pzdr
bartekltg


Tak mi się przypomniało:
http://en.wikipedia.org/wiki/Dutch_national_flag_pro
blem

do góry