-
Path: news-archive.icm.edu.pl!news.gazeta.pl!not-for-mail
From: Mateusz Loskot <s...@s...net>
Newsgroups: pl.comp.programming
Subject: Re: sortowanie
Date: Sun, 04 Oct 2009 20:59:34 +0100
Organization: "Portal Gazeta.pl -> http://www.gazeta.pl"
Lines: 47
Message-ID: <haaur9$5m6$1@inews.gazeta.pl>
References: <haaous$bjs$1@inews.gazeta.pl>
NNTP-Posting-Host: 5ad618df.bb.sky.com
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: 8bit
X-Trace: inews.gazeta.pl 1254686377 5830 90.214.24.223 (4 Oct 2009 19:59:37 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Sun, 4 Oct 2009 19:59:37 +0000 (UTC)
X-User: mloskot
In-Reply-To: <haaous$bjs$1@inews.gazeta.pl>
User-Agent: Thunderbird 2.0.0.23 (X11/20090817)
Xref: news-archive.icm.edu.pl pl.comp.programming:183751
[ ukryj nagłówki ]Mariusz Marszałkowski wrote:
> Hey
>
> Muszę napisać (albo skądś dorwać gotową) bardzo wydajną implementację
> sortowania. Sortowana będzie wielokrotnie tablica o rozmiarze około
> 2-10mln elementów. Jeden element będzie miał rozmiar około 12-20
> bajtów. Elementy będą miały przypisane wartości z mało licznego
> zbioru, np wartości całkowite z zakresu od 1 do 50.
>
> Pierwsza kwestia od jakiego rozmiaru elementu opłaca się użyć tablicy
> wskaźników. Jeśli element jest duży to opłaca się użyć wskaźników
> zamiast kopiowania, pytanie czy 12-20 bajtów to już duży element?
Nic nie piszesz o tym, czy zależy Ci na szybkości, czy na oszczędności
pamięci.
Może widok się nada. Polecam artykuł Macieja Sobczaka:
http://www.ddj.com/showArticle.jhtml?articleID=18440
1789
oraz View Template Library.
Rozwiązanie koncepcyjnie podobne do wskaźników, ale zamiast wskaźników,
możesz sortować indeksy (zakładając, że istnieją) z kolekcji macierzystej.
Najgorszy przypadek to będzie sortowanie kolekcji ~0.5 GB danych.
Do tego widok sortujący to dodatkowe ok 10% z w/w pamięci.
Wszystkie indeksy są o tym samym rozmiarze, czyli np. 10 mln * 4 bajty.
> Druga sprawa to wybór algorytmu. Na pewno qsort odpada dla małej
> ilości wartości. Chyba jakieś sortowanie kubełkowe?
Albo to:
http://en.wikipedia.org/wiki/Polyphase_merge_sort
Jak pamięci brak, to istnieje też STXXL (http://stxxl.sourceforge.net/)
implementujące 2 lub 3 tzw. algorytmy external sorting.
Jak pamięci jest dość, a ma być szybko, to być może jest sens aby to
zrównoleglić (choć czytałem jakąś analizę znanych algorytmów z
sekwencyjnych implementacji ale wykonanych z użyciem OpenMP i wyniki nie
były jednoznacznie "za MP", AFAIR).
Pozdrawiam
--
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
Następne wpisy z tego wątku
- 04.10.09 23:18 Mariusz Marszałkowski
- 05.10.09 05:40 Maciej Pilichowski
- 05.10.09 15:54 luckboy
- 05.10.09 15:58 Mariusz Marszałkowski
- 05.10.09 18:34 luckboy
- 05.10.09 19:39 Mariusz Marszałkowski
- 05.10.09 22:51 Wiktor S.
- 16.11.09 23:12 Bastion
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-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 <=
- 2024-05-18 Łódź => Handlowiec - Systemy CRM <=
- 2024-05-17 ZŁOMNIK o pracy w TVN TURBO, nowych przepisach i współczesnej motoryzacji. Turbo Taryfa!
- 2024-05-17 Białystok => DevOps Engineer Conexa First (Contractor) <=
- 2024-05-17 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-17 Zabrze => Junior HelpDesk <=
- 2024-05-17 Bieruń => Administrator i wdrożeniowiec Lotus Notes/Domino <=