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