W dniu sobota, 13 października 2012 21:18:12 UTC+2 użytkownik Edek Pienkowski
napisał:
> Dnia Sat, 13 Oct 2012 11:58:34 -0700, kenobi napisal:
>
>
>
> > za jakis czas sobie klepne pewnie to uogolnienie, np dla 32 bit mozna
>
> > pewnie w jednym przebiegu zrobic histogram na gornych bitach wygenerowac
>
> > czesciowo uporzadkowany wynik i w kolejnym posortowac kawalki, albo tez i
>
> > inaczej ladnie dobierajac po efektywnosci - w kazdym razie raczej da sie
>
> > to uogolnic :U
>
>
>
> Dla string�w te� si� da. Taki 8-bajtowy string to 2^64 tak jak int64
>
> to 2^64 jak i float to 2^64. Ymmv, ale widz� morfizm, wystarczy uzupe�ni�
>
> string zerami do najd�u�szego, zera tak rzadko wyst�puj�. Jedynie te
>
> floaty majďż˝ jakieďż˝ NaNy i InfY, ale int siďż˝ nadaje. A jak siďż˝ zmienne
>
> typu String wrzuci w histogram potem, to mo�na histogramowa� po
>
> intach zbudowanych ze znak�w, robi si� to raz, a nie z bajt�w, wystarczy
>
> jak wszystkiemu por�wnywalnemu waln�c raz przypisanie znaku do liczby,
>
> znaki s� znane, wed�ug lexykografii i jeste�my w domu po jednym
>
> przebiegu, chyba �e wszystkie przypisane liczby s� takie same, ale
>
> wtedy zaczyna si� od string�w obci�tych uprzednio co sprawia
>
> �e por�wnanie potem jest szybsze, mo�na bezkosztowo prawie
>
> offsetem za�atwi�.
>
>
>
> Uog�lniaj�c, ma si� mo�liwo�� histogramowania wszystkiego do czego
>
> mo�na przypisa� liczb� bez uprzedniego sortowania.
>
>
nieczytelny tekst da sie przeczytac tylko niektore slowa - tu jest zrodlo tego
pomyslu
przynajmniej ja stad sie o tym dowiedzialem

The quick-sort algorithm requires O(n lg n) operations on average and O(n2)
operations in the worst situation. This
algorithm is very fast. Nevertheless, it needs to be improved! It reminds me of a
quotation from a sci-fi novel by Arkady
and Boris Strugatsky: "We are well aware that this task has no solution... We want to
know how to solve it."
A simple and efficient sorting algorithm exists that, in the worst situation,
requires O(n) operations. No, this is not a joke!
There is such an algorithm. On AMD Athlon 1050, it sorts 10 million numbers in
approximately 0.3 seconds, thousand
times faster than quick sort.
I discovered this algorithm time when I was participated in a computer-science
contest. One of the problems required the
participants to sort seven numbers using no more than three comparison operations.
Seeing this problem as a perfect
opportunity for showing off, I wrote a small program that sorted the numbers without
using any comparison operations.
Unfortunately, my solution was not considered superior. Only after a couple of years
of carefully exploring the existing
sorting algorithms could I evaluate the importance of the result.

kriss kaspersky code optimization effective memory usage

(dalej jest opis ale sprowadza sie to mw do tego co mowie) problemem jest tu ze
dobrze
to dziala jesli wartosci jest duzo a zakres jest waski a niezbyt nadaje sie kiedy
wartosci jest malo, a zakres szeroki ale kiedy wartosci jest duzo i zakres szeroki,
da sie to mz
podzilic pokombinowac i tez ogolnie wykorzystac ten sposob


i tak czesto ja potrzebowalbym sortowac po prostu male inty i wtedy to dziala
blyskawicznie i jest hipergenialna metoda