Datové struktury I - 1. úkol

Termín odevzdání: 30. října 2016.
Způsob odevzdání: Odevzdáním na stránce https://kam.mff.cuni.cz/~ds1/.
Obecná pravidla: Prečtěte si je důkladně

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 jediné 63-bitové číslo bez znaménka, klíč. V setříděném souboru data.out musí jít klíče vzestupně a bez duplicit. Navíc pro každý klíč vypište číslo řádku, na kterém se daný klíč vyskytoval poprvé. Řádky číslujte od 1. Řádky výstupního souboru jsou tedy dvojice čísel oddělené mezerou. Vstup data.txt, výstup data.out a dočasné soubory držte v aktuálním adresáři.

Ř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.

Fyzická pamět testovacího počítače je 8 GiB a operační systém je OS Linux.

Příklad

Vstup

96313 6024613951808161023 8417427497858712892 3894 96313 6437842131676518652

Výstup

3894 4 96313 1 6024613951808161023 2 6437842131676518652 6 8417427497858712892 3

Problémy při implementaci

Práce s pamětí

Většinu času váš program spotřebuje čtením a zapisováním dat, tedy je nutné minimalizovat počet přístupů na disk. Porovnejte například čas nutný k porovnání dvou prvků (řádově nanosekundy) oproti času na jedno načtení dat z disku (řádově milisekundy [1]). Protože při čtení dat z pevného disku je nutné čekat na natočení plotny (rotational latency) a nastavení hlavy (seek time) je výhodné načíst víc dat, které jdou za sebou [2]. K tomu slouží page cache operačního systému a buffer pro práci s I/O [3]. Tuto nevýhodu pevných disků (částečně) řeší disky SSD.

Také je vhodné zvolit rychlý přístup ke čtení dat. Na toto téma najdeme na internetu spousta porovnání a názorů [4]. Vždy je vhodné si zvolené přístupy pro danou aplikaci si samostatně otestovat. Nám v zásadě bude stačit použít základně prostředky zvoleného jazyka.

K přetřídění vstupních dat je také výhodné znát velikost operační paměti počítače, na kterém budou vykonány testy (v našem případě je to 8 GiB). Pozor, pokud budete při běhu programu používat více paměti než je dostupné, pak dojde ke stránkování. Používaní stránkování (swap prostoru) vyžaduje přístupy na disk a tím dojde k výraznému zpomalení běhu programu [5]. Proto při měření vždy nastavte velikost alokované paměti v závislosti na velikosti paměti počítače (stačí jako konstanta v zdrojovém kódu).

Hardware

K testování použijte počítače v unixové části laboratoře Rotunda, t.j. u-pl1 až u-pl37. V zásadě jsou dvojího typu - jeden typ má 16 GiB operační paměti a druhý typ má jenom 4 GiB paměti a menší disk. Testovací počítač má 8 GiB paměti, vaše řešení odevzdávejte tak, aby na něm fungovali efektivně. Běžný stav paměti testovacího stroje:

$ free -m
              total        used        free      shared  buff/cache   available
Mem:           7476         139         132          81        7204        6985
Swap:          7985           0        7984

Generování dat a testování

Generování dat

Na generování dat je v laboratoři rotunda dostupný generátor /afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw1/gen-data.

Volby generátoru

Generátor standardně vygeneruje zadání o takové délce, která se použije pri jeho testování na testovacím počítači.

-s XX: Zde XX je seed. K ladění použijte několik seed-ů a na nich ověřte rychlost a korektnost vašeho řešení.
-l LL: Zde LL určí počet vygenerovaných klíčů na vstupu. Minimum je 1 048 576 klíčů. Pro menší délky je vhodné ořezat data pomocí utility head.
--half: Nastaví počet klíčů na polovinu oproti standardnímu. Velikost výstupu bude přibližně 25 GiB.
--short: Nastaví délku výstupu na 1/16 oproti standardní. Velikost výstupu bude přibližně 3 GiB.
--super-short: Nastaví délku výstupu na 1/256 oproti standardu. Velikost výstupu bude přibližně 200 MiB.

Příklady použití

$/afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw1/gen-data -s XX >/tmp/data.txt
vygeneruje data pro měření, zhruba 44 GiB.

$/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 3 GiB.

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ě ověřte dobu běhu vašeho programu na počítačích u-pl1 až u-pl37. Na měření použijte utilitu time.

	Názvy	RAM	Disk	Velikost testovacích dat	Čas na plný počet bodů	Čas na nulový počet bodů
Rychlejší	`u-pl1` až `u-pl20`	16 GiB	SDD	Plná, 44 GiB	13 minut	19 minut
Pomalejší	`u-pl21` až `u-pl37`	4 GiB	HDD	Poloviční, 25 GiB	28 minut	45 minut

Váš program by měl splnit časový limit na obou typech počítačů. Náš testovací stroj má 8 GiB paměti RAM a HDD disk. Ve vašem programu může být konstanta udávající množství dat, která se mají najednou zpracovávat. Před odesláním tuto tuto konstantu správně nastavte pro testovací stroj.

Při měření ukládejte soubor data.txt a jakékoliv pomocné soubory do adresáře /tmp, t.j. pracujte v adresáři /tmp. V případě, že vstup data.txt, výstup data.out a dočasné soubory neuložíte do aktuálního adresáře, vaše řešení není správné. Při doběhnutí programu pomocné soubory automaticky smažte. Navíc po skončení měření smažte i vstup a výstup, 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.

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 hlaště emailem na ds1@kam.mff.cuni.cz.

Odevzdání

Pro odeslání řešení použijte formulář na https://kam.mff.cuni.cz/~ds1/. Do poznámky uvádějte například parametry kompilace "kompilace: gcc -O3 sorter-55973318.c -o sorter-55973318". Popisem je textový soubor, kde je uveden stručný popis řešení. Odevzdávejte, prosím, jenom úplně správné a dostatečně rychlé řešení do 30. října 2016.