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.
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-pl0 až u-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.
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.txtvygeneruje verzi dat pro ladění programu cca 2 GB.
Zde XX jsou poslední dvě číslice z vašeho studentského čísla.
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 BabkaV 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.
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. |