eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingsortowanie › Re: sortowanie
  • Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
    atman.pl!news.supermedia.pl!news.nask.pl!news.nask.org.pl!news.internetia.pl!no
    t-for-mail
    From: Michoo <m...@v...pl>
    Newsgroups: pl.comp.programming
    Subject: Re: sortowanie
    Date: Sun, 14 Oct 2012 16:42:36 +0200
    Organization: Netia S.A.
    Lines: 48
    Message-ID: <k5ejb1$a83$1@mx1.internetia.pl>
    References: <k59gbj$be7$1@node2.news.atman.pl> <k5bc6k$4ea$1@mx1.internetia.pl>
    <50795bb6$0$1297$65785112@news.neostrada.pl>
    <k5bo04$n79$2@mx1.internetia.pl>
    <507968f5$0$1220$65785112@news.neostrada.pl>
    <k5bqi2$n79$3@mx1.internetia.pl>
    <5079736f$0$1228$65785112@news.neostrada.pl>
    <k5bvji$n79$7@mx1.internetia.pl>
    <7...@g...com>
    <k5c6ta$hlr$1@mx1.internetia.pl>
    <2...@g...com>
    <b...@g...com>
    <c...@g...com>
    <k5cs8t$bkr$1@node1.news.atman.pl>
    <7...@g...com>
    <k5e2d2$jgh$1@node2.news.atman.pl>
    <8...@g...com>
    <k5e5co$iip$1@node1.news.atman.pl>
    <f...@g...com>
    <k5e6pg$jti$1@node1.news.atman.pl>
    <5...@g...com>
    <k5e99u$q1m$1@node2.news.atman.pl>
    NNTP-Posting-Host: 83.238.197.12
    Mime-Version: 1.0
    Content-Type: text/plain; charset=UTF-8; format=flowed
    Content-Transfer-Encoding: 8bit
    X-Trace: mx1.internetia.pl 1350226081 10499 83.238.197.12 (14 Oct 2012 14:48:01 GMT)
    X-Complaints-To: a...@i...pl
    NNTP-Posting-Date: Sun, 14 Oct 2012 14:48:01 +0000 (UTC)
    In-Reply-To: <k5e99u$q1m$1@node2.news.atman.pl>
    X-Tech-Contact: u...@i...pl
    User-Agent: Mozilla/5.0 (X11; Linux i686 on x86_64; rv:10.0.6esrpre) Gecko/20120817
    Icedove/10.0.6
    X-Server-Info: http://www.internetia.pl/
    Xref: news-archive.icm.edu.pl pl.comp.programming:199902
    [ ukryj nagłówki ]

    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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: