-
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: Potyczki
Date: Sat, 24 Nov 2012 13:39:32 +0100
Organization: Netia S.A.
Lines: 29
Message-ID: <k8qfhq$eue$1@mx1.internetia.pl>
References: <k8frhm$5pg$1@node1.news.atman.pl>
<50abbc9e$0$1214$65785112@news.neostrada.pl>
<k8p9ei$h43$1@mx1.internetia.pl> <k8qbgp$ls0$1@node1.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 1353761146 15310 83.238.197.12 (24 Nov 2012 12:45:46 GMT)
X-Complaints-To: a...@i...pl
NNTP-Posting-Date: Sat, 24 Nov 2012 12:45:46 +0000 (UTC)
In-Reply-To: <k8qbgp$ls0$1@node1.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:201180
[ ukryj nagłówki ]On 24.11.2012 12:36, bartekltg wrote:
>
> Mając dodatkową pamięć dysku równo pierwotnej tablicy
> (a tak naprawdę 0.5) możemy posortować tablicę
> w 4 przebiegach _sekwencyjnego_ odczytu/zapisu.
slawek się potem "poprawił", że plik jest "dużo" (10x) większy niż ram.
Nie do końca rozumiem to 0.5 nawet przy założeniu dane 4 razy większe od
tablicy - mergesort potrzebuje na każdy merge drugie tyle miejsca.
Wychodzi więc mi minimum 1.5 zakładając, że nie robimy ostatniego
scalania. (Mamy 4 bloki po 1/4 n zajmujące na dysku n i żeby dwa z nich
scalić potrzebujemy dodatkowe 0.5n na wynik.)
>
>
> Kołaczą mi się sztuczki ze statystyką i nie jestem pewien,
> czy nie da się tego zrobić lepiej. Ale ciężko będzie,
> 5 przbiegów po dysku to podejrzewam minimum.
> W koncu nawet log(n) jest większe.
W praktycznym przypadku (a nie maksymalnie złośliwym) spróbowałbym z
drzewem prefiksowym w ramie a jak by się przestało mieścić to dopiero
fallback do sortowania. Daje jeden dodatkowy odczyt sekwencyjny i
złożoność k*log(k) w RAMie gdzie k to liczba różnych wartości.
--
Pozdrawiam
Michoo
Następne wpisy z tego wątku
- 24.11.12 13:40 slawek
- 24.11.12 14:13 bartekltg
- 24.11.12 14:12 PK
- 24.11.12 14:23 PK
- 24.11.12 14:37 slawek
- 24.11.12 14:40 Michoo
- 24.11.12 14:44 slawek
- 24.11.12 14:47 Michoo
- 24.11.12 14:48 PK
- 24.11.12 14:48 slawek
- 24.11.12 14:51 PK
- 24.11.12 14:56 slawek
- 24.11.12 15:04 slawek
- 24.11.12 15:12 Michoo
- 24.11.12 15:17 Michoo
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-07-11 Tokarze CNC czyli ciężkie życie prototypiarza
- 2024-07-12 Zgody na przetwarzanie danych
- 2024-07-13 IObit Uninstaller Pro 13.6.0.5 Multilingual: Installation Guide
- 2024-07-12 stare graty młode kozy
- 2024-07-11 8080
- 2024-07-13 Przyłącze dolne grzejnika
- 2024-07-13 IObit Uninstaller Pro 13.6.0.5 Multilingual Overview
- 2024-07-12 Czym wykonać otwór fi 100 w betonie komórkowym?
- 2024-07-12 Warszawa => Senior Rust Software Engineer <=
- 2024-07-12 Warszawa => Business Unit Manager (Recruitment Business) <=
- 2024-07-12 Warszawa => Head of WMS Competence Center for IT&D Contract Logistics
- 2024-07-12 Warszawa => Head od WMS Competence Center dla IT&D (Blue Yonder) <=
- 2024-07-12 Kraków => Ruby Backend Developer <=
- 2024-07-12 Warszawa => UX/UI Designer <=
- 2024-07-12 Częstochowa => Specjalista ds. Marketingu (E-Commerce) <=