-
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
Następne wpisy z tego wątku
- 14.10.12 16:55 bartekltg
- 14.10.12 17:58 M.M.
- 14.10.12 18:10 bartekltg
- 14.10.12 18:12 bartekltg
- 14.10.12 18:25 bartekltg
- 14.10.12 18:27 kenobi
- 14.10.12 18:29 M.M.
- 14.10.12 18:31 bartekltg
- 14.10.12 18:45 kenobi
- 14.10.12 18:57 bartekltg
- 14.10.12 19:43 kenobi
- 14.10.12 19:56 kenobi
- 14.10.12 20:01 bartekltg
- 14.10.12 20:14 bartekltg
- 14.10.12 20:14 kenobi
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-20 Fiat 125p wer. pikup - w PRL moszna było, w III Reczy [pospolitej] nie moszna
- 2024-05-19 Pożar salonu z chińskimi elektrykami
- 2024-05-18 LED
- 2024-05-19 ceny nieruchomości
- 2024-05-18 Szczecin => UX/UI Designer <=
- 2024-05-18 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-18 Warszawa => Software .Net Developer <=
- 2024-05-18 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-18 Ulm => Solution Architect (sichere Kommunikation und IoT-Loesungen <=
- 2024-05-18 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-05-18 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-18 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-18 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-18 Warszawa => Account Manager (Recruitment Services) <=
- 2024-05-18 Łódź => Salesperson - CRM Systems <=