-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: Potyczki
Date: Sat, 24 Nov 2012 14:13:33 +0100
Organization: ATMAN - ATM S.A.
Lines: 60
Message-ID: <k8qh5v$rad$1@node1.news.atman.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>
<k8qfhq$eue$1@mx1.internetia.pl>
NNTP-Posting-Host: 144-mi3-6.acn.waw.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node1.news.atman.pl 1353762815 27981 85.222.69.144 (24 Nov 2012 13:13:35
GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Sat, 24 Nov 2012 13:13:35 +0000 (UTC)
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026
Thunderbird/16.0.2
In-Reply-To: <k8qfhq$eue$1@mx1.internetia.pl>
Xref: news-archive.icm.edu.pl pl.comp.programming:201182
[ ukryj nagłówki ]W dniu 2012-11-24 13:39, Michoo pisze:
> 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.
Aj, wszytko liczyłem dla 4GB, czyli 8 razy większego.
Problem jest gdzie indziej, nie zauważyłem, że ciągi
na siebie nachodzą. To powiększa mój bufor 16 razy;)
Zaczyna być nieprzyjemnie, ale nadal robialnie.
Zwłaszcza, że w normalnych warunkach ma się 12GB z czego 8 wolne;)
niech będzie 10GB danych, *16. 160GB.
RAMu niech będize 41GB, to daje ok 7 cykli, czyli
powiedzmy 13 (odczytów+zapisów=13)
Trzeba przewalić. 2TB
Powiedzmy, ze nie korzystamy ze sprzętu za 60k$ typu
dysk na PCI-16 6GB transger 4GB/s.
Jakiś dysk SSD na szybko zerknięty na Agito, odczyt/zapis 500MB/s.
Dysk maagnetyczny: "Szybkość przesyłu danych sformatowanych: 6 Gbit/s"
Cokolwiek to znaczy;)
W każdym razie naszą operację szacujemy na 15-20 minut.
Długo, trzeba by poprawić.
Ale zaczyna być ciekawie:)
> 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.)
Moja pomyłka. +1 w dobrą stronę i -4 w złą;)
>> 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.
To drzewo dużo miejsca nam nie oszczędza, ale zawsze.
Nie zaszkodzi spróbować, ale dla losowego ta heurystyka
zadziała?
pzdr
bartekltg
Następne wpisy z tego wątku
- 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
- 24.11.12 15:18 PK
- 24.11.12 15:25 Jacek
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) <=