Dnia Sat, 13 Oct 2012 12:33:40 -0700, kenobi napisal:

> 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

"Doing the impossible is fun" - Walt Disney.

--
Edek