W dniu niedziela, 14 października 2012 12:57:53 UTC+2 użytkownik kenobi napisał:
> 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 ;>

chwile sie zastonowilem i bez modyfikacji nie
da sie trzeba jednak zmodyfikowac in przerzucic histogram na offsety by zliczyc
miejsce na listy,

do góry

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

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


Nie jest to metoda kasperskiego, tylko sortowanie przez zliczanie
wymyslone przez Harold H. Seward w starożytności (znaczy latach 50).
Sortowanie pozycyjne, czyli to, co próbujesz teraz tak dzielnie
odkryć, było jeszcze wcześniej.

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 13:13:53 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 12:57, kenobi pisze:
>
>
>
> > 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
;>
>
>
>
>
>
> Nie jest to metoda kasperskiego, tylko sortowanie przez zliczanie
>
> wymyslone przez Harold H. Seward w starożytności (znaczy latach 50).
>
> Sortowanie pozycyjne, czyli to, co próbujesz teraz tak dzielnie
>
> odkryć, było jeszcze wcześniej.
>

spox, ale kasperski to upowszechnil ;-)
przynajmniej sobie i mnie (przeniosl to
na mojsiejszy grunt) tak ze widze
pewien powod by to tak tu nazywac (niech
bedzie ze oficjalna nazwa to counting
sort, spox)

nie probuje odkryc sortowania pozycyjnego
tylko ew mowie o tym ze mozna napisac
procedure z uogolnieniem 'kasperskiego' na
szersze zakresy - i tak jest cholernej uzytecznosci mz

do góry

W dniu 2012-10-14 13:22, kenobi pisze:
> W dniu niedziela, 14 października 2012 13:13:53 UTC+2 użytkownik bartekltg napisał:
>> W dniu 2012-10-14 12:57, kenobi pisze:
>>
>>
>>
>>> 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
;>
>>
>>
>>
>>
>>
>> Nie jest to metoda kasperskiego, tylko sortowanie przez zliczanie
>>
>> wymyslone przez Harold H. Seward w starożytności (znaczy latach 50).
>>
>> Sortowanie pozycyjne, czyli to, co próbujesz teraz tak dzielnie
>>
>> odkryć, było jeszcze wcześniej.
>>
>
> spox, ale kasperski to upowszechnil ;-)

Bzdury. Kasperski urodził się w 1976r.
Wiki twierdzi, że trzeci tom
The Art of Computer Programming
to 1973.
Ten algorytm był powszechnie znany 'od zawsze'.

Kiedy był ten konkurs? 1990 to już 'Cormen'.


> przynajmniej sobie i mnie (przeniosl to

A mi moja dziewczyna wytłumaczyła na czym polegają
plazmony powierzchniowe. Mam je publicznie
nazywać 'rozwiązaniami Anki'? Bez jaj;)

> na mojsiejszy grunt) tak ze widze
> pewien powod by to tak tu nazywac (niech
> bedzie ze oficjalna nazwa to counting
> sort, spox)


Nie, jest to mylące (nikt nie kojarzy tego!)
i wprowadza w błąd (piedołę będa powtarzać inni)

Zrozum, że to legenda zrobiona na ignorancji autora.
I chyba do dziś nie załapał, jeśli się tym chwali w ksiażce.

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 13:56:46 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 13:22, kenobi pisze:
>
> > W dniu niedziela, 14 października 2012 13:13:53 UTC+2 użytkownik bartekltg
napisał:
>
> >> W dniu 2012-10-14 12:57, kenobi pisze:
>
> >>
>
> >>
>
> >>
>
> >>> 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 ;>
>
> >>
>
> >>
>
> >>
>
> >>
>
> >>
>
> >> Nie jest to metoda kasperskiego, tylko sortowanie przez zliczanie
>
> >>
>
> >> wymyslone przez Harold H. Seward w starożytności (znaczy latach 50).
>
> >>
>
> >> Sortowanie pozycyjne, czyli to, co próbujesz teraz tak dzielnie
>
> >>
>
> >> odkryć, było jeszcze wcześniej.
>
> >>
>
> >
>
> > spox, ale kasperski to upowszechnil ;-)
>
>
>
> Bzdury. Kasperski urodził się w 1976r.
>
> Wiki twierdzi, że trzeci tom
>
> The Art of Computer Programming
>
> to 1973.
>
> Ten algorytm był powszechnie znany 'od zawsze'.
>
>
>
> Kiedy był ten konkurs? 1990 to już 'Cormen'.
>
>
>
>
>
> > przynajmniej sobie i mnie (przeniosl to
>
>
>
> A mi moja dziewczyna wytłumaczyła na czym polegają
>
> plazmony powierzchniowe. Mam je publicznie
>
> nazywać 'rozwiązaniami Anki'? Bez jaj;)
>
>
>
> > na mojsiejszy grunt) tak ze widze
>
> > pewien powod by to tak tu nazywac (niech
>
> > bedzie ze oficjalna nazwa to counting
>
> > sort, spox)
>
>
>
>
>
> Nie, jest to mylące (nikt nie kojarzy tego!)
>
> i wprowadza w błąd (piedołę będa powtarzać inni)
>
>
>
> Zrozum, że to legenda zrobiona na ignorancji autora.
>
> I chyba do dziś nie załapał, jeśli się tym chwali w ksiażce.
>

hehe, uzywam wielu nazw, sam kasperski
nazywa to sortowaniem liniowym, (mozna tez
mowic sortowanie przez histogram itp)

nie jestem pewien zreszta czy ten counting
sort to zupelnie to samo; zliczac mozna
roznie a to jest specjalny sposob na
gruncie kodu - wcale nie twierdze ze to jest
unikalny sposob kasperskiego jest to jednak
jedna z nie bardzo znanych metod gdy tymczasem
daje ona kopa w dpe wszystkim innym algorytmom
(przynajmniej na sporym gruncie swoich zastosowan ;)

do góry

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

>>
>
> hehe, uzywam wielu nazw, sam kasperski

Nazwy są po to, aby komunikować się z innymi.
Jeśli nazwa nie dekoduje się u rozmówcy,
nie jest nic warta.

> nazywa to sortowaniem liniowym, (mozna tez
> mowic sortowanie przez histogram itp)

A można mówić magic harry potter sort. Tylko po co.


> nie jestem pewien zreszta czy ten counting
> sort to zupelnie to samo; zliczac mozna

To samo.
http://city17.ca/out.of.print.book.pdf
Tylko gośc zupełnie poważnie mówi o gigabajtach
RAMu sortując inty.

> roznie a to jest specjalny sposob na
> gruncie kodu - wcale nie twierdze ze to jest
> unikalny sposob kasperskiego jest to jednak
> jedna z nie bardzo znanych metod gdy tymczasem
> daje ona kopa w dpe wszystkim innym algorytmom

Jest to jeden z najpowszechniej znanych algorytmów,
jest w każdej książce do "ASD" i uczą go na każdym
kursie 'algorytmiki'.

Jest bardzo ważnym przykładem, bo mówimy 'Sortując
przez porównania nie da się zejść poniżej log_2 (n!)
~ n log[n] porównań. Dowód:[...] Ale jeśli posortujemy
inaczej, nie porównując par elementów, to ograniczenie
nas nie dotyczy, zobaczcie: [i to countsort]'.

BTW. Sortowanie przez porównanie działa na dowolnych
obiektach. Sortowanie przez zliczanie/pozycyjne
potrzebuje tym więcej przebiegów, im dłuższe w zapisie
bitowym są dane. Ostatecznie, jeśli sortujemy n liczb
z zakresu np 0-100n, zlozonośc asymptotyczna spowrotem
jest n log[n]. W przyrodzie nic nie ginie;)


Korzyść i przyspieszenie wynika z tego, że dane
spałniają pewną własność. Tutaj, mają mały zakres.
podobnie, jeśli potrafimy powiedzieć coś o ich,
rozkładzie, potrafimy sortowac liniowo (w sensie czasu
oczekiwanego) za pomocą kubełków.



BTW Obstwiałbym, że więcej osób zna to sortowanie przez
zliczanie niż postać Kaspersiego.

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 14:23:10 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 14:09, kenobi pisze:
>
>
>
> >>
>
> >
>
> > hehe, uzywam wielu nazw, sam kasperski
>
>
>
> Nazwy są po to, aby komunikować się z innymi.
>
> Jeśli nazwa nie dekoduje się u rozmówcy,
>
> nie jest nic warta.
>
>
>
> > nazywa to sortowaniem liniowym, (mozna tez
>
> > mowic sortowanie przez histogram itp)
>
>
>
> A można mówić magic harry potter sort. Tylko po co.
>
>
>
>
>
> > nie jestem pewien zreszta czy ten counting
>
> > sort to zupelnie to samo; zliczac mozna
>
>
>
> To samo.
>
> http://city17.ca/out.of.print.book.pdf
>
> Tylko gośc zupełnie poważnie mówi o gigabajtach
>
> RAMu sortując inty.
>
>
>
> > roznie a to jest specjalny sposob na
>
> > gruncie kodu - wcale nie twierdze ze to jest
>
> > unikalny sposob kasperskiego jest to jednak
>
> > jedna z nie bardzo znanych metod gdy tymczasem
>
> > daje ona kopa w dpe wszystkim innym algorytmom
>
>
>
> Jest to jeden z najpowszechniej znanych algorytmów,
>
> jest w każdej książce do "ASD" i uczą go na każdym
>
> kursie 'algorytmiki'.
>
>
>
> Jest bardzo ważnym przykładem, bo mówimy 'Sortując
>
> przez porównania nie da się zejść poniżej log_2 (n!)
>
> ~ n log[n] porównań. Dowód:[...] Ale jeśli posortujemy
>
> inaczej, nie porównując par elementów, to ograniczenie
>
> nas nie dotyczy, zobaczcie: [i to countsort]'.
>
>
>
> BTW. Sortowanie przez porównanie działa na dowolnych
>
> obiektach. Sortowanie przez zliczanie/pozycyjne
>
> potrzebuje tym więcej przebiegów, im dłuższe w zapisie
>
> bitowym są dane. Ostatecznie, jeśli sortujemy n liczb
>
> z zakresu np 0-100n, zlozonośc asymptotyczna spowrotem
>
> jest n log[n]. W przyrodzie nic nie ginie;)
>
>
>
>
>
> Korzyść i przyspieszenie wynika z tego, że dane
>
> spałniają pewną własność. Tutaj, mają mały zakres.
>
> podobnie, jeśli potrafimy powiedzieć coś o ich,
>
> rozkładzie, potrafimy sortowac liniowo (w sensie czasu
>
> oczekiwanego) za pomocą kubełków.
>
>
>
>
>
>
>
> BTW Obstwiałbym, że więcej osób zna to sortowanie przez
>
> zliczanie niż postać Kaspersiego.
>
>

luzik, nie ma problemu - z tym ze ja bym sie nie
czepial mojego sposobu nazewnictwa, dla mnie
zrodlem tej metody bylo info od kasperskiego
na programistycznym gruncie a nie doki nt countingsorta

do góry

On 2012-10-13, bartekltg <b...@g...com> wrote:
> Dla 20?

Chyba to cofnę, bo źle się wyraziłem.
Tzn. wyniki są, więc ktoś napisał programy dowodzące, że posortowanie
po iluś porównaniach jest możliwe. Nie wiem czy ktoś napisał program
sortujący :).

> Sprzętowe sortowanie za pomocą pełnego drzewa decyzyjnego
> dla 20 liczb? Jaja sobie robisz? ;) Oszczedza się kompa,
> ale trzeba tone krzemu.

Nie wiem jak to się odbywa. Może tak jak w algorytmie Ford-Johnson
(podział problemu).

W rozwiązaniach, o których mówię (np. w fizyce), tona krzemu pewnie
wchodzi w grę :).
Nie mniej 20 to brzydka liczba. Spodziewałbym się 8, 12 czy 16.

> Ładny. Ale widzisz różnicę między nim, a pełnym drzewem.
> To się mieści w RAMie lub krzemie;)

Kto wie jak to będzie wyglądało, jak porzucimy krzem :). Nie mniej
rzeczywiście zaimplementowanie dla 20 liczb byłoby cokolwiek
kłopotliwe (choć kombinować jakoś można, ale się nie zagłębiałem
w to aż tak).

pozdrawiam,
PK

do góry

On 2012-10-14, Michoo <m...@v...pl> wrote:
> Możemy rozważyć mergesort na 10 procesorach - wykona trochę więcej
> porównań niż Twoje "optimum", ale za to zakończy pracę prawie 2 razy
> szybciej ;)

Oczywiście. Algorytmika to coś innego niż inżynieria :). Algorytm
optymalny (w jakimś sensie: np. liczby porównań lub liczby zapisów
w pamięci) to rzecz konkretna i obliczalna.
Algorytm szybki, to szybki i już. Szybkość zależy od sprzętu,
obciążenia, pogody, intensywności tła i cholera wie czego jeszcze.

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ą :).

pozdrawiam,
PK

do góry

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



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

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.


--
Pozdrawiam
Michoo

do góry