W dniu sobota, 13 października 2012 22:53:09 UTC+2 użytkownik M.M. napisał:
> W dniu sobota, 13 października 2012 19:37:28 UTC+2 użytkownik kenobi napisał:
>
> > oczywiscie i tak jest to slamazarstwo
>
> > najlepsze sortowanie to to co ja nazywam
>
> > metoda chrissa kaserskiego, czyli
>
> > h[ tab[i] ]++;
>
> Przepiekna sztuczka, do dzis pamietam uczucie euforii gdy
>
> sie po raz pierwszy dowiedzialem o tej metodzie :) Zdaje sie ze
>
> ta sztuczka nazywa sie sortowaniem kubelkowym. Niestety ma ona
>
> wade. Gdy ilosc roznych wartosci w tab jest duza to potem na
>
> posortoanie h i tak potrzeba M*log(M) operacji (gdzie M to ilosc
>
> roznych wartosci).
>
>

no mnie tez to zdziwilo i tez pamietam moment
jak o tym przeczytalem w tym kawalku
kasperskiego (bardziej utkwilo w pamieci ze
duraki z komisji odrzucily jego rozwiazanie)
ksiage wypozyczylem z mjejskiej biblioteki w bydgoszczy i czytalem to raz pamietam
idac
chyba ze trzy kilometry i czytajac w marszu
po jakichs bydgoskich (niespecjalnie wyjsciowych) peryferiach, (mieszkalem tam
troche wtedy) niezla sprawa

co do tego ze to ma ograniczenia to wydaje mi
sie ze mozna to prawdopodobnie rozwinac/uogolnic a i tak bedzie najlepsze

co do algorytmow to wogole jednak mnie
omijają - w swojej bazie kodu nie mam ani
jednego algorytmu pomijajac rysowanie kolka
bressenhamem (czego nie rozumiem jakies plus szesc minus dwa) ale to bym chyba
zaliczyl
wlasnie do sztuczki optymalizacyjnej -
te bardzo lubie i mam ich sporo


>
> > Podobno kiedys zrobil tak na jakiejs
>
> > olimpiadzie jako nastolatek i komisja
>
> > mu tego nie uznala ;-) zarabista anegdota
>
> > (pisalem o tym z rok czy dwa temu)
>
> Moze w tresci zadania byl jakis kruczek?
>
>
>
> > Mozna to uogolnic np w h(tab[i])
>
> > robiac galaz drzewa, albo innymi metodami
>
> > i mysle ze to raczej jest po prostu najszybsze
>
> Jesli jest mala ilosc roznych wartosci (innymi slowy
>
> te same wartosci powtarzaja sie czesto) to z pewnoscia
>
> bedzie najszybsze.
>
>
>
> W praktyce pewnie przyda sie jeszcze jakias funkcja hash
>
> czestos[ hash(elementy[i]) % size ]++.
>
>
>
> Pozdrawiam