Datové struktury 1

Datové struktury 1 - NTIN066 - ZS 2014/2015

1. úkol

Termín odevzdání: 23. října 2014.

Způsob odevzdání: odesláním do CodExu a odesláním v příloze emailem na ds1@kam.mff.cuni.cz.

Změna:

Testovací data jsou 45GB místo 30GB.
Řešení odeslané do CodExu musí vstup přečíst ze souboru data.txt a zapsat je setříděná do data.out a nemělo by používat více než 500MB paměti. (Bude testováno na datech velikosti maximálně 10MB.) Až na nastavení paměťových nároků, vstupu a výstupu a definici 64-bitových čísel by řešení odeslané emailem a do CodExu mělo být stejné.

Pravidla

Veškerý odevzdaný kód musí být originální tedy vytvořen vámi bez jakékoliv vedlejší "inspirace".
Svůj kód s nikým nesdílejte, aby se váš kód nestal něčí "inspirací". Výjimku tvoří odevzdání kódu.
Úkol a možné postupy řešení můžete probírat s ostatními, avšak respektuje výše uvedené o nesdílení kódu.
Řešení, která nejsou ve shodě s těmito pravidly, nebudou hodnocená.

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ě 64-bitová čísla bez znaménka, klíč a hodnotu. V setříděném souboru musí jít klíče vzestupně a klíče se stejnou hodnotou musí mít hodnotu setříděnou také vzestupně.

Pomocí unixového programu /afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl1-gen-data dostupného v laboratoři Rotunda vygenerujte zkušební soubor data.txt a změřte dobu běhu vašeho programu na jednom z počítačů u-pl0 až u-pl15. Vygenerovaný soubor má cca 45GB a časový limit na jeho setřídění je 60 minut. Řešení, které se nevejde do tohoto časového limitu na těchto datech, je považované za nedostačující. 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í. Chovejte se k ostatním ohleduplně, pokud uvidíte, že někdo daný počítač zrovna používá (příkazy who a top), použijte jiný počítač, nebo počkejte, až měření dokončí. Nekolegiální jednání mi hlaste emailem. 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, nicméně měření a doprovodný email stačí zaslat do 30. října.

Příklad vstupu

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

Výstup

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

Generování zkušebních dat

$/afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl1-gen-data XX >/tmp/data.txt

vygeneruje data pro měření a

$/afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl1-gen-data - XX >/tmp/data.txt

vygeneruje desetinovou verzi dat pro účely ladění. 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

Jmeno: Michal Koucky Pocitac: u-pl7 CPU: Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz RAM: 6GB Cas (podle utility time): real 43m41.704s, user 20m30.975s sys 1m26.892s Datum a cas mereni: 08-09-14 15:28:50 XX (pro gen-data): 37 Strucny popis algoritmu: Pouzil jsem Huge-sort kombinovany se Super-sortem aplikovanym na inverzni prvky. Pseudonym pro zverejneni na webu: nechci byt uveden.

Podívejte se též na soutěž Gray sort.