ESET Programátorská úloha - niekoľko slov a kódov na záver...

Existuje prostředek, kterým se pozná, co v kom vězí. Stačí ho pustit k práci. (F.X. Šalda).

Programátori sú vraj súťaživé povahy - akcie typu ICFP, či Google programming contest pravidelne priťahujú značnú pozornosť a množstvo záujemcov. V našom prípade odozva tiež prevýšila očakávania - celkovo na úlohu zareagovalo (podľa mojich skoro úplne, ale zase nie tak docela nekompletných štatistík) 179 záujemcov, pričom v drvivej väčšine bolo ich súčasťou aj riešenie. Časť poslala po našich komentároch aj druhé, prípadne ďalšie príspevky, takže celkovo počet riešení, ktoré prebehli našimi rukami a desktopmi výrazne prevýšil 200! (Bravó! :-).

Ďalším pozitívnym faktorom je, že viac ako 50% účastníkov vyriešilo úlohu na prvý pokus správne (viď. tabuľku 1), keďže povedané slovami B. Meyera "Correctness is clearly the prime quality. If a system does not do what it is supposed to do, then everything else about it matters little."

Než ale pristúpime k vlastným riešeniam, skúsme si predstaviť trochu podrobnejšie úlohu samotnú.

Programátorská úloha ako ju nepoznáte

Predstavte si, že máte súbory - veľa súborov aby som sa vyjadril jasnejšie (pokiaľ niekoľko sto miliónov znamená veľa aj vo vašom slovníku :-). Samozrejme, že ich potrebujete nejakým spôsobom indexovať, ale na to predsa existujú hešovacie funkcie ako MD5, alebo SHA. Potom na overenie toho, či sa nejaký súbor už nachádza vo vašej zbierke stačí vypočítať príslušný heš a napr. porovnať s údajmi v databáze.

Čo ak však chcete zistiť, či súbor nie je hoci aj neúplnou kópiou iného zo zbierky, prípadne či v zbierke nemáte kratšiu verziu toho nového? Hešovacie funkcie tu zjavne nepomôžu a predstava porovnávania celých súborov tiež príliš neláka - je treba prísť s niečím iným.

Jednou z možností je rozdeliť každý súbor na bloky rovnakej veľkosti (napr. 4kB) a spočítať nejaký heš pre každý blok samostatne (keďže v tomto prípade nepotrebujete tak kvalitnú hešovaciou funkciu ako pre celé súbory, stačí aj niečo jednoduchšie ako napr. CRC). No a zvyšok je jasný: podpis súboru bude definovaný sekvenciou hešov jednotlivých blokov a vy potrebujete zistiť, či nový podpis je alebo nie je prefixom iného. Nepripomína vám to náhodou niečo?

Typy riešení

Jednou z hlavných požiadaviek na typ úlohy bolo, aby aj napriek jednoduchému zadaniu nepostačovali priamočiare riešenia, ale naopak, aby boli riešitelia stimulovaní k hľadaniu algoritmicky a implementačne kvalitnejších postupov.

V našom prípade je priame riešenie jasné: jedinečnosť každého ďalšieho podpisu overíme tak, že ho porovnáme so všetkými ostatnými jedinečnými podpismi, ktoré už máme. Tak isto je ale očividné, že komplexita tohto riešenia rastie kvadraticky s počtom podpisov a preto je pre väčšie sady súborov neadekvátne. Takže čo lepšie ste vymysleli...

Triedený list podpisov

Základnou myšlienkou tejto kategórie riešení je, že pokiaľ necháme celé pole podpisov najskôr lexikograficky striediť (t.j. zoradíme ich podobne ako mená v telefónnom zozname), tak nám stačí jedna iterácia zoradeným poľom na určenie jednoznačnosti každého podpisu v poli. Takisto nezáleží na tom, či sú podpisy vo forme reťazca, alebo poľa čísiel (aj keď práca s reťazcami vyžaduje istú opatrnosť pri porovnávaní podpisov), čo môže zjednodušiť načítavanie. Zložitosť týchto riešení je sumou komplexity triedenia O(NlnN) a lineárneho prehľadania poľa podpisov, čo je akceptovateľné aj pre veľké súbory. Hlavnou nevýhodou je, že v pamäti potrebujeme držať aj nejedinečné podpisy - aj keď v našom prípade nebolo percento duplicitných podpisov príliš vysoké na to aby sa táto nevýhoda výraznejšie prejavila.

Príkladmi tohto typu riešenia sú:

• Priamočiare riešenie v C s veľmi jednoduchým (a efektívnym) načítavaním vstupných dát, pracujúce s reťazcami: rastos.c (autor: Rastislav Staník)
• Zástupca Javy so sparalelizovaným načítavaním dát (možno by bolo zaujímavé vidieť paralelizovaný aj sort): YYYMain2.java (autor: Stanislav Kaščák)
• Čistý SQL kód - srdce fanúšika databáz musí zaplesať: uniq.sql (autor: Miro Zilina/NY)
• Prečo sa trápiť s nejakým programovaním, keď máme unix tools:
  cut -f 2- -d " " | sort -r | awk -f uniq.awk
  (náš kód inšpirovaný niekoľkými inými riešeniami, v ktorých sa ale vyskytli drobné nedostatky)

Tieto príklady pracovali s podpismi ako s entitami, nasledujúci prístup začína z opačného konca.

Trie alias N-árny strom

Pri použití Trie sa každé číslo podpisu sa stáva samostatným uzlom stromu, to nasledujúce sa stáva jeho dieťaťom atď. Počet jedinečných podpisov je potom daný počtom listov vo výslednom strome. To sa dá sa zistiť priamo počas vytvárania stromu, alebo následným prebehnutím uzlov kompletného stromu. Z hľadiska komplexity je to najefektívnejšie riešenie, keďže každý podpis stačí raz pridať do stromu (komplexita pridania je O(N), kde N je dĺžka podpisu). Problémom tohto typu riešení sú vyššie nároky na pamäť, ktoré sa ale dajú do značnej miery zredukovať použitím niektorých optimalizácií dátových štruktúr stromu.

Príklady riešení používajúce Trie:

• Výborne zoptimalizované riešenie v C - prvé, ktorého autor využil fakt, že uzly Trie majú najčastejšie jedného potomka a prispôsobil tomu dátové štruktúry: uniq.c (autor: Viktor Bachratý)
• Ďalšie pozorne zoptimalizované riešenie v C++, ktorého autor rozvinul predošlú myšlienku ešte ďalej a zoskupil série uzlov, ktoré majú jedného potomka do jediného uzla: main.cpp (autor: Štefan Šimek)
• Jednoduché a elegantné riešenie v perle, ktoré sme sa rozhodli navzdory ponuke autora ponechať v "neperlovsky" čitateľnej podobe :-) jarob.pl (autor: Jaroslav Ban)

Nakoniec sme dostali niekoľko riešení, ktoré ideovo aj výpočtovou zložitosťou spadajú niekde medzi tieto dve skupiny riešení.

Iné typy stromov (binárne, ternárne, ...)

Patria sem napríklad binárne stromy, ternárne stromy, radixové stromy, technika kompresie reťazcov, prípadne iné variácie na dané téma... Podobne ako v prípade Trie, tieto riešenia je tiež možné do značnej miery optimalizovať ladením dátových štruktúr, pridaním vyvažovania, špecializovanou alokáciou pamäte a pod. Jednoduchý binárny strom bol napríklad naším interným víťazným algoritmom pred začiatkom súťaže.

Príklady rôznych riešení z tejto kategórie:

• Vlastnoručne naprogramovaný červeno-čierny binárny strom v C++: rbmain.cpp (autor: Matej "kravčo" Kravjar)
• Jediný zástupca LISPu s Treap implementáciou vyvažovaného binárneho stromu: eset.clj (autor: Em DeEm)
• Pekná implementácia ternárneho stromu v C: ttree.c (autor: Vladimír Chren)
• Technika kompresie reťazcov, ktorá sa dá tiež považovať (možno s mierne prižmúrenými očami :-) za špecifický druh stromovej štruktúry: compTreeQuick.c (autor: Midek)

No a na záver niečo, čo sa tak ľahko zaškatuľkovať nedá...

Iné (renegátske :-) algoritmy

Nakoniec ostalo pár riešení, ktoré nespadajú pod žiadnu (mne) známu visačku a potvrdzujú, že vždy sa dá vymyslieť niečo nové :-) Dvaja prispievatelia riešili úlohu podobným, zaujímavým spôsobom: rekurzívne zoskupovali podpisy po častiach, až kým nezískali jedinečné skupiny a tým aj počty jedinečných súborov. Toto riešenie potrebuje jeden prechod poľom podpisov (bez triedenia či iného predspracovania) a má výrazne nižšie nároky na spotrebu pamäte ako napr. Trie. Záujemcov o bližší popis odkazujeme priamo na stránku jedného z riešiteľov.

Zhrnutie použitých algoritmov

Výsledná štatistika riešení je zhrnutá v tabuľke 2. Mimoriadne pozitívne hodnotíme fakt, že väčšina riešiteľov neuspokojilo jednoduché riešenie s kvadratickou komplexitou, ale skúsila nájsť niečo efektívnejšie, a to veľmi často so zaujímavými výsledkami!

Programovacie jazyky

Na záver by sa patrilo povedať niečo o technickej stránke riešení - t.j. použitých programovacích jazykoch. Aj keď je zrejmé, že najviac nás zaujímali riešenia v C/C++, boli sme zvedaví, aké rôzne jazyky ľudia používajú... a rozhodne sme neboli sklamaní :-). Aj keď jazyky C-rodiny podľa očakávania dosť jasne dominovali, dostali sme aj celkom slušnú nádielku skriptovacích riešení, vyučovanie programovania na stredných a vysokých školách zanechalo stopy v podobe niekoľkých pascalistov, objavil sa aj jeden zástupca funkcionálnych jazykov v podobe Clojure, či riešenia čiastočne alebo kompletne v SQL. Najexotickejším kandidátom bol nepochybne kód (so správnymi výsledkami) v Progress 4GL.

Jasne sa tiež ukázalo, že pre efektivitu riešenia bol výber algoritmu či dátovej štruktúry dôležitejší ako použitý programovací jazyk - najrýchlejšie programy v pythone, bash/awku či perle sa blížili ku kvalitným kompilovaným C/C++ riešeniam (zmestili sa povedzme do pomyselnej hranice 10-násobku) a dobré Java/C# riešenia boli pre C/C++ absolútne vyrovnanými konkurentmi, čo myslím potvrdilo môj osobný maxim, že nie sú pomalé jazyky, ale len pomalé programy! Zhrnutie riešení podľa programovacích jazykov je v tabuľke 3.

Slovo na záver...

Interne máme veľmi dobrú skúsenosť s malým programátorským zadaním počas pohovorov, ale takáto programátorská úloha ako súčasť náborovej kampane bola pre nás novou výzvou. Jej jedinou tienistou stránkou z nášho pohľadu bolo, že sme dosť podcenili váš záujem o riešenie a teda aj kapacity potrebné na vyhodnotenie jednotlivých riešení - týmto vám ďakujeme za trpezlivosť, ktorú ste s nami preto museli mať :-). Dúfame, že aj napriek tomu to bolo pre vás zaujímavé vybočenie z normálu - pre nás to bola zase veľmi pozitívna a poučná skúsenosť, ktorú si s najväčšou pravdepodobnosťou niekedy v budúcnosti zopakujeme.

• Slovensky

Home > Programátor

© 1992 - 2009 ESET, spol. s r.o. - Všetky práva vyhradené