🚀 go-pugleaf

On 30 Oct 1997, Andrzej Bialecki wrote:

> Oj, chyba niezupelnie... :-) To jest owszem sposob dobry na DOSa, ktory
> sam w sobie ma zarzadzania pamiecia tyle, co kot naplakal. Ale w kazdym
> przyzwoitym unixie (BSD, Linux, Sun) od tego jest zarzadzanie pamiecia
> wirtualna, zeby nie musiec sie tym przejmowac. Oczywiscie, kiedy system
> zacznie page'owac, bedzie to znacznie wolniej szlo, ale pewnie i tak
> szybciej, niz wlasnorecznie napisany algorytm page'owania :-)
> 
> Ja bym po prostu wzial qsort() i nie przejmowal sie - byleby wystarczylo
> swapa.

Oj, niekoniecznie! Różne algorytmy sortowania mają różny styl dostępu do
elementów tablicy - jedne działają bardziej lokalnie, inne skaczą po całej
tablicy. Ponieważ w naszym przypadku to nie jest wszystko jedno i dostęp
do pamięci zajmuje różny czas w zależności od kolejności tych dostępów,
lepiej zastosować jakiś algorytm z'optymalizowany pod tym kątem, a nie
ten, który ma najmniejszy formalny koszt.

QSort nie powinien być tragiczny - najwolniej będzie na początku, ale
później będzie sortował w obrębie niewielkich kawałków. Jednak na pewno są
algorytmy lepsze do tego przypadku.

                                QRCZAK
    __("<             Marcin Kowalczyk
    \__/             qrczak@knm.org.pl
     ^^      http://kki.net.pl/qrczak/