Datové struktury I - NTIN066 - ZS 2015/2016 - 1. úkol

Termín odevzdání: 27. října 2015. Samotné měření je možné dodělat do 3. listopadu 2015.
Způsob odevzdání: Odesláním v příloze emailem na ds1@kam.mff.cuni.cz.
Vstup a výstup: Řešení musí přečíst vstupní textová data ze souboru data.txt a zapsat je setříděná do souboru data.out. Předpokládejte, že zmíněné soubory se nacházejí v aktuálním adresáři.
Systém: Fyzická pamět testovacího počítače je 6 GB, OS Linux.
Čas: Řešení musí vyprodukovat korektní výstup do 35 minut.

Pravidla

Popis problému

Napište program, který setřídí soubor na disku data.txt. Soubor data.txt je textový soubor, který na každém řádku obsahuje dvě nezáporná nanejvýš 63-bitová čísla bez znaménka, klíč a hodnotu. V setříděném souboru data.out musí jít klíče vzestupně. Pro každý klíč vypište minimální hodnotu, se kterou byl asociován.

Generování dat a testování

Pomocí unixového programu /afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw1/gen-data dostupného v laboratoři Rotunda vygenerujte zkušební vstup (je nutné přesměrovat do data.txt, protože generátor vypisuje na standardní výstup). Následně změřte dobu běhu vašeho programu na jednom z počítačů u-pl0u-pl15. Na měření použijte utilitu time. Vygenerovaný soubor má cca 45 GB a časový limit na jeho setřídění je 35 minut. Řešení, které se nevejde do tohoto časového limitu na těchto datech, je považované za nedostačující. Rychlost a správnost řešení bude následně ověřena na jiných ale podobných datech.

Při měření ukládejte soubor data.txt a jakékoliv pomocné soubory do adresáře /tmp. Po ukončení měření po sobě soubory smažte, aby ostatní mohli provést svoje měření. Jinak dojde místo na disku a jelikož ostatní po vás nemohou soubory smazat, počítač tím bude pro měření zablokován. Nezapomínejte smazat nejen pomocné soubory ale i vstup a výstup.

Chovejte se k ostatním ohleduplně, pokud uvidíte, že někdo daný počítač zrovna používá na výpočty (příkazy who a top nebo htop), použijte jiný počítač, nebo počkejte, až měření dokončí. Nekolegiální jednání anebo zablokovaný počítač nám hlaste emailem na ds1@kam.mff.cuni.cz.

Naměřenou dobu vašeho programu pošlete emailem na ds1@kam.mff.cuni.cz s detaily uvedenými níže. Řešení je nutné odevzdat ve výše uvedeném termínu.

Příklad vstupu

96313 3992064775605989878
6024613951808161023 4071849752967919252
11417427497858712892 3671181978208670736
3894 2867422479361385327
96313 3992064775605758114
6437842131676518652 6510455770151352973

Výstup

3894 2867422479361385327
96313 3992064775605758114
6024613951808161023 4071849752967919252
6437842131676518652 6510455770151352973
11417427497858712892 3671181978208670736

Generování zkušebních dat

$/afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw1/gen-data -s XX >/tmp/data.txt

vygeneruje data pro měření, zhruba 45 GB, a

$/afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw1/gen-data -s XX --short >/tmp/data.txt

vygeneruje verzi dat pro ladění programu cca 2 GB.

Zde XX jsou poslední dvě číslice z vašeho studentského čísla.

Doprovodný email

Při odeslání emailu se změřeným časem uveďte detaily měření dle následujícího vzoru. Datum uvádějte ve tvaru D. M. YYYY H:M:S.

Předmět uveďte jako 'HW1-55973318'. (t.j. HW1-<studentské číslo>).

Do přílohy vložte zdrojový kód vašeho řešení, pojmenujte jej napríklad sorter-55973318.cpp.

Jmeno: Martin Babka
Pocitac: u-pl7
CPU: Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
RAM: 6GB
Cas: real 33m41.704s, user 15m30.975s sys 1m26.892s
Datum spusteni: 1. 11. 2015 15:28:50
XX: 37
Popis: Pouzil jsem Huge-sort kombinovany se Super-sortem aplikovanym na inverzni prvky.
Pseudonym pro vysledky na webu: nechci byt uveden.
Cviceni: pondeli-12:20-lichy.
Kompilace: gcc -O3 sorter-55973318.cpp -o sorter-55973318

Odevzdání

V případě, že budete měřit po 27. 10., pošlete stejný email s doplněnými naměřenými hodnotami, ale už bez zdrojového kódu. V případě, že se těsně nemůžete vejít do časového limitu, zkuste při generování dat jako XX zadat 333.

Výsledky

Tato tabulka uvádí pouze studenty, kteří uvedli pseudonym pro zveřejnění na webu.

Pseudonym T Jazyk Popis
Lukáš 23m23.257s C/C++ Jeden průchod 16-ti cestného Merge-sortu na souborech s bloky setříděnými kombinací Radix-sortu, Quick-sortu a Insert-sortu s bufferovaným vstupem i výstupem. (Vnitřní třídění převzato z úkolu do AIM.)
Toufi 25m11.971s C/C++ rozdelim soubor na useky, ktere v pameti zaberou ~4GB, setridim quicksortem (male useky se dotrizuji insertsortem), kazdy 4GB usek ulozim binarne do pomocneho souboru (bez duplicit). Nakonec dotridim vicecestnym mergesortem (1 pruchod).
JB 27m02.584s C/C++ V paměti třídím 4GB clustery quicksortem kombinovaným s insertion sortem pro krátké úseky, clustery pak slévám (všechny najednou)
woitee 27m16.024s C/C++ Predtridil jsem v pameti chunky velikosti 200.000.000 paru cisel quicksortem, ktere pak ukladal do souboru, a nakonec tyto soubory vsechny dohromady mergenul.
gyfis 29m01.482s C/C++ Pouzil jsem klasicky quicksort s ukladanim mezivysledku do temp souboru, ktere jsem nasledne setridil pomoci merge sortu.
O(N)dra 29m08.259s C/C++ Postupne jsem tridil bloky, ktere se vesly do pameti pomoci Quicksortu a nasledne setridene bloky slil dohromady.
-M^2- 29m34.030s C/C++ Ctena data se rozdeli na bloky o velikosti 5 GB (pri 16 B na jednu dvojici klic-hodnota), ktere se setridi pomoci Quicksortu a zapisi se binarne do docasnych souboru. Setrizene sekvence se pote z docasnych souboru postupne ctou a slevaji se (merge) do jedne sekvence, ktera se vypisuje do finalniho vystupniho souboru. K odmazavani duplicitnich klicu (které jsou v setrizene posloupnosti za sebou) dochazi jak pri zapisu docasnych souboru, tak pri vypisu finalniho vystupu.
Semai 29m46.319s C/C++ Program cte data ze vstupniho souboru po blocich, ktere se vejdou do operacni pameti pocitace, kde se tyto bloky setridi a nasledne ulozi v binarnim formatu na disk jiz bez duplicit klicu v ramci jednoho bloku. K trideni pouzivam vlastni implementaci algoritmu quicksort, ktera misto rekurze pouziva frontu intervalu k trideni a pro mala pole (min nez 15 prvku) prepne na InsertSort. Takto se vstupni soubor vejde do 4 bloku v pameti a vytvori se 4 pomocne setridene binarni soubory, ktere se nasledne slevaji dohromady (s kontrolou duplicit). Pro toto slevani je implementovana vlastni specializace pro 4 soubory. Pokud by vstupni soubor obsahoval vice nez 4*335544320 radek (to je vhodne zvolena konstanta pro RAM 6 GB), pak by byl vstup rozdelen do vice souboru a vysledne slucovani by se provadelo iterativne vzdy po dvou, coz je vyrazne pomalejsi a pravdepodobne by nesplnilo pozadavky na casovy limit. Ovsem finalni testovaci data budou stejne velka jako ta, ktera jsme meli k dispozici my, takze by v tom nemel byt z dny problem (viz mail od pana Kouckeho nize). Jeste me napadaji optimalizace, jak program zrychlit. Prvni je nemazani pomocnych souboru na konci programu. Tim se usetri zhruba 10s. Dalsi, vyraznejsi, je to, ze posledni blok trideny v pameti nemusim vubec ukladat na disk pred zahajenim operace slevani (pripadne pokud bych mel malo volne pameti, tak lze ulozit napriklad jen druha polovina nacteneho bloku). Tim lze usetrit odhadem 2 minuty. Jiste by bylo pekne, aby program najednou slevat i "n" souboru pro obecne "n" a ne mit jen specializaci pro 4 soubory pro tuto konkretni ulohu. To by slo zaridit napriklad pomoci minimalni haldy, ktera by si pamatovala "n" prvku - jeden prvek by byl dvojice aktualni hodnota a soubor, ze ktereho pochazi. Toto vylepseni jsem nepokladal v ramci teto domaci ulohy za nutne (a potvrdil mi to i pan Koucky v mailu). Test jsem poustel na u-pl1 opakovane, namerene hodnoty se pohybovaly v rozmezi 28m56.521s az 29m59.018s (pokud jsem byl na pocitaci sam nikdo mi mereni nezkazil).
Vojcek 29m54.046s C/C++ Data nacitam po 200,000,000 radek. Nactenou cast vzdy seradim quicksortem a binarne zapisu tento vysledek, jiz s eliminovanymi duplicitami. Az je hotovy cely soubor, nacitam z jednotlivych serazenych casti prvky do bufferu (jeden na kazdy soubor) a slevam je do vysledneho souboru, pricemz se opet kontroluji duplicity, jelikoz mezi soubory se mohou vyskytnout. V pripade, ze dojde buffer, je jednorazove nacteno dalsich nekolik (BUFF_SIZE) prvku, cimz se snizi pocet pristupu k disku.
Erim 30m10.331s C/C++ Pouzil jsem Radix Sort na bloky o velikosti 2 GB. Setridene bloky zbavil duplicit a zapsal do souboru. Vsechny soubory jsem pote najednou cetl a na vystup psal polozku s nejmensim klicem (merge).
mato 30m24.462s C/C++ Pouzil jsem Quicksort (pro malý počet prvků nahrazený Insertsortem) na cca. 5GB bloky dat. Na ty jsem pak pustil vícevláknový merge.
Mikandmik 30m31.761s C/C++ Nejprve nacitam data do pameti, dokud se vejdou. Pote je setridim pomoci quicksortu kombinovaneho s insertionsortem na poslednich nekolika prvcich. Pote pole projdu, vyhazim duplicity a ulozim jako binarni soubor. Z techto souboru potom vicecestnym slevanim vytvorim vystupni soubor.
Špulka 30m43.360s C/C++ Radix sort + jednofázové slévání
Poolen 31m09.147s C/C++ Pro vnitrni trideni jsem pouzil algoritmus quick-sort, vstupni soubor je nacitan po blocich pevne dane velikosti (250mil prvku - 3.8GB pameti, ale lze zmenit, testoval jsem i s 320mil prvky, tedy 4.8GB pameti a chodilo) a posilan prave do quick-sortu. Vysledky z nej jsou znovu ukladany na disk, uz ale v binarni podobe (uspora asi 2/3 dat). Po uspesnem nacteni, setrideni a ulozeni nasleduje modifikovane slevani. To sleva vsechny soubory najednou s pomoci minimalni haldy. Do te se nacitaji prvky z jednotlivych docasnych souboru a do uz konecneho vystupu se postupne ukladaji koreny haldy. Vypocetni cas by se jeste dal vylepsit lepsim bufferovanim pri zapisech a ctenich ze souboru.
Jonas 31m24.492s C/C++ Pro předtřídění používám quicksort, mezivýsledky slévám n-cestným mergesortem pomocí haldy. Napsal jsem si vlastní bufferování vstupu a výstupu s využitím read(2) a write(2). Eliminaci duplicitních klíčů provádím ve výstupním bufferu.
TomasM 31m28.890s C/C++ Pouzil jsem quicksort v nekolika vlaknech (mensi pole dotriduje insertion sortem) na 4 bloky po ~ 5 Gb, ktere se potom slevaji mergesortem.
pomelo 31m29.916s C/C++ Používám quicksort, na malé úseky insertion-sort. Nakonec vše sliju n-cestným mergem.
Edward 31m31.148s C/C++ Data delim do nekolika velkych bloku, ktere jako mezivysledky ukladam v binarni podobě do /tmp. Na trideni bloku pouzivam kombinaci QuickSort, HeapSort a InsertionSort dle velikosti tridene casti. Binarni soubory mezivysledku nakonec sliji MargeSortem do vystupniho souboru.
Stepan 32m24.041s C/C++ Count sort pro male hodnoty, rozdeleni do nekolika souboru podle klicu, kazdy soubor je trizeny po castech v pameti Quicksortem a pokud je casti vic, jsou pak spojene Mergesortem.
Koza Máňa 32m40.048s C/C++ Vstup načítám po 200M řádcích, které v paměti setřídím quicksortem (inplace) a následně bez duplicit zapíšu binárně do pomocných souborů. Takových souborů zapíšu cca 6-7 v závislosti na datech a duplicitách. Po zapsání posledního souboru z nich data postupně načítám, slévám a zapisuji do výsledného souboru. Kvůli sekvenčnímu přístupu na hdd si vždy 2M čísel z každého pomocného souboru načítám do paměti najednou (třída IO_Buffer).. Program vypisuje progress na stdout.
kuba 32m41.416s C/C++ Pro setrideni jsem pouzil QuickSort a MergeSort. Vzdy si do pameti nactu zhruba 4GB dat (260.000.000 radku, kde kazdy radek jsou dva longy = 16 B), ty setridim QuickSortem, zapisu v binarni podobe na disk, a jakmile mam takto setridene vsechny bloky, pak je jednim MergeSortem setridim (tj. modifikace klasickeho MergeSortu pro k setridenych poli") "
citron 32m53.859s C/C++ Tridim soubor po kouskach, ktere se vejdou do RAMky quicksortem (na min jak 8mi prvcich insertion sortem). Z toho mi vznikne pet souboru, ktere nasledne zmerguju.
helgrind 32m57.846s C/C++ Pouzil jsem Quick-Sort kombinovany s Insert-sortem na bloky o velikosti 300 milionů cisel, ty jsem ulozil jako binárni soubory, ktere jsem potom vsechny zaraz Merge-oval.
Mich29 32m58.765s C/C++ Pouzil jsem quicksort na setrideni casti souboru a potom pomoci k-cestneho slevani jsem je slil do vystupniho souboru.
Vaclav Klaus 33m23.511s C/C++ Pouzil jsem Quicksort na 4GB bloky a ty najednou slil vicecestnym slevanim.
Samkharadze 33m25.34s* C/C++
vladce_rotopedu 33m39.841s C/C++ Pouzil jsem MSB radix sort na vnitrni trideni a n-cestny merge. Pro zmenseni velikosti jsou setridene mezisoubory zapsany binarne a misto celych klicu jejich rozdily. Odstraneni duplikatu probiha jak v ramci kazdeho mezisouboru pred jeho vypsanim, tak pri samotnem slevani.
regnarg 33m45.140s C/C++ Cache-optimalizovany RadixSort pro setrideni bloku velikosti O(|RAM|), setridene bloky na disk, externi jednourovnovy B-cestny merge (B=pocet bloku, +radove 10)
Karryanna 34m31.510s C/C++ Do pameti se nacitaji 5GB bloky long longu, ty se tridi QuickSortem a dotriduji InsertSortem, pri odkladu na disk se zahazujici duplicity. Odlozene bloky se slevaji de facto MergeSortem, ktery nesleva bloky po dvou, ale vsechny naraz.
ondish 34m51.319s C/C++ Data nacitam po 3gb do pamati, utriedim quicksort-om s pivotom ako priemer prveho a prostredneho prvku. Poslednych 10 prvkov dotriediom insertion sortom. Citanie je optimalizovany read + vlastny atoi. Sekvencie zapisem binarne na disk. Nasledne zlejem cez externalSort a zapisem cez fprintf. 4gb usage ram swapovalo.
MZetko 35m00.59s* C/C++ Pouzil jsem quicksort na pocitani mezivyslednych souboru ktere jsem nasledne slil dohoromady soucasne do vysledneho souboru.
Honkl 35m18.96s* C#
Peťan 39m05.81s* C#
Kozel 44m59.16s* C/C++ Kombinace quicksortu a mergesortu na trideni v pameti, nasledovane vicecestnym mergem. Predpokladam, ze jako cas se bere user+sys.
BSK 127m33.34s* C/C++ Soubor jsem po asi 3 GB částech setřídil in place quicksortem. Tyto části jsem uložil do pomocných souborů, které jsem pak slil.
Chyla DNF Java Načtení kusu souboru - setřídění pomocí quicksortu - smazání stejných klíčů s vyšší hodnotou - uložení do dočasných souborů - slití dočasných souboru do jednoho, při té příležitosti mazání stejných klíčů s větší hodnotou.
Poznámky: * indikuje námi naměřený čas