21.6.2018 Sort

Seznámení se základními principy operačního systému UNIX, převážně z uživatelského hlediska. Absolvent kurzu by měl být schopen napsat netriviální program v shellu.
Egst
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 22. 6. 2018 13:50
Typ studia: Informatika Bc.

21.6.2018 Sort

Příspěvek od Egst »

Naprogramuj sort bez použití utility sort.

Požadovaná funkcionalita:

Kód: Vybrat vše

SYNTAXE
        mysort [OPTIONS] SOURCE

POPIS
        Setřídíděné řádky souboru SOURCE vypíše na standardní výstup

        OPTIONS:
        -t
                Oddělovač polí.
                Pokud nenastaven: Libovolně dlouhá posloupnost mezer.
                Pokud se nějaký nastaví, pak pole odděluje jediný zadaný symbol, ne posloupnost.

        -k
                Klíče (rozsah polí) podle kterých se třídí zleva doprava.
                Nejprve se setřídí podle prvního klíče, pokud nastane shoda, třídí se podle dalšího.
                Pokud i v posledním klíči nastane shoda, pak se řádky vypíší v pořadí v jakém byly v originálu.
                (Jde tedy o stabilní sort.)
                Pokud nenastaven: Třídí podle všech polí.

                Formát zápisu klíčů:
                -kN,M[FLAGS], kde N a M jsou celá čísla a [N, M] je pak rozsahem polí tvořících klíče.

                FLAGS:
                n       numerické třídění (jinak lexikografické)
                r       třídění pozpátku (pouze pro numerické třídění)
                b       ignoruje mezery (pouze pro lexikografické třídění)
                f       ignoruje case (pouze pro lexikografické třídění)
Omezení paměti: Soubor se celý do paměti nevejde, ale klíče ano. Pamětí na disku nijak omezeni nejsme.

Omezení vstupu: Klíče mohou obsahovat pouze alfanumerické znaky a mezery. Můžeme uvažovat, že jsou nějak "rozumně" dlouhé.

Řešení:

Forst pak ještě navíc uváděl explicitně, co je povoleno dělat. Snažil se nás tím navést na nějaké řešení, co si představoval, že je optimální. Hlavní myšlenka byla v tom, že sortovat umí nejenom sort, ale třeba i ls a jelikož klíče obsahují pouze alfanumerické znaky a mezery, pak není problém vytvořit soubor pro každý klíč a tak ho pojmenovat, pak to jednoduše setřídit pomocí ls.

(Ti co zvolili tento postup Forsta zřejmě potěšili. Prý takových nebylo hodně, a tak mi dal za jedna i přesto, že všechno ostatní kromě použití ls nebylo nejchytřeji promyšleno.)

Lexikografické třídění je jasné podle názvu souboru. Numerické jsem osobně dělal tak, že jsem souboru nastavil na dané číslo datum modifikace (dává to 4 byty unsigned integerů, což je celkem dost) a třídil podle ls -t. Forst mi ale vytkul, že se to dá dělat i podle názvu souboru, akorát si musím ta čísla vhodně posunout, abych z lexikografického třídění dostal numerické.

Implementaci třídění samotného tedy řešit nemusíme, stačí promyslet, jak třídit podle více klíčů a zajistit stabilní sort. Já osobně na to šel rekurzí: Setřídím podle prvního klíče, pokud najdu několik stejných klíčů za sebou, pak je opět setřídím stejným způsobem podle dalšího klíče, ale jen mezi sebou. Pokud jsou klíče za sebou různé, tak je mám setříděné a můžu je postupně vypisovat. Uchovával jsem si původní čísla řádků a tak jsem takto očíslované řádky prostě vypisoval z originálního souboru pomocí sed -n "${n}p", kde $n je číslo řádku. Forst mi pak vytkul, že takto pro každý řádek sedem projíždím opět všechny řádky a tedy z nějakého hezkého algoritmu, co je implementovaný v ls to kazím na kvadratickou složitost. Prý očekával, že někoho napadne použít ed << END ${n1}p ${n2}p ... END, který vypíše všechny řádky najednou, jelikož to celé uchovává v paměti, a v tom mělo být to navedení, že klíče se vejdou do paměti.

Celkově k ústní: Pokud vám tam něco chybí, nebo nefunguje, tak se vás akorát zeptá, jak to udělat správně. Pokud něco vymyslíte, tak je to v pohodě. Takže se akorát přpravte být schopni rychle zfleku něco vymýšlet.
Odpovědět

Zpět na „SWI095 Úvod do UNIXu“