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