Trvalo to dlouho, dalo nám to hodně práce, zabralo mnoho času, ale nakonec se to povedlo!
Máme tu výsledky 1. kola soutěže .NET Challenge!
Můžete se také podívat na vzorová řešení nejlepších soutěžících:
Pokud jste se zaregistrovali a odevzdali svá řešení, můžete se podívat na body, které jste dostali za jednotlivá hodnotící kritéria, a samozřejmě také na komentáře poroty k vašim řešením, abyste viděli, co se nám líbilo a co by se dalo zlepšit.
Všem soutěžícím děkujeme za odevzdaná řešení a za čas, který psaním soutěžních úloh strávili, všichni beze zbytku oddvedli velmi dobrou práci. Omlouváme se, že nám výsledky tak dlouho trvaly, ale je opravdu časově hodně náročné pečlivě projít 70 odevzdaných prací a porovnat, která z nich je lepší. Samozřejmě se mohlo stát, že jsme nějakou funkci neobjevili nebo nám něco nefungovalo, přečtěte si tedy, prosím, komentáře k řešení, a v případě, že něco nebude souhlasit, určitě nám napište.
Komentáře poroty k řešením z 1. kola
Lehká úloha – Code Snippets
Zadání a výsledková listina úlohy
Přestože tato úloha byla označena jako lehká, nakonec se ukázalo, že vůbec lehká nebyla. Mnoho uživatelů napsalo velmi robustní objektový model, což je na jednu stranu velice dobře, žel bohu na straně druhé jim to často přineslo více problémů než užitku.
Poměrně dost aplikací mělo problémy s mazáním a přejmenováváním placeholderů, pár aplikací při otevření nového snippetu zapomněly vyprázdnit seznam s referencovanými jmenný, takže se smíchaly reference z načítaného souboru s těmi, které tam byly před tím. Občas nějaká aplikace spadla, ale jinak základní funkcionalitu nabízely téměř všechny odevzdané práce.
Ve většině aplikací nám vadilo, že při kliknutí na placeholder v textu či jeho označení se nevybral také v seznamu nebo tabulce placeholderů a člověk ho musel složitě hledat v případě, že jej chtěl změnit. Také mnoho uživatelů nechalo v textovém poli pro zadání kódu obyčejné proporciální písmo místo fontu neproporcionálního, který se pro zobrazování kódu běžně používá. To samozřejmě nevypadá nejlépe a není to moc přehledné, i když je to samozřejmě jen detail.
Jinak musíme všechny soutěžící pochválit za dobře odvedenou práci, většina aplikací byla povedená a funkční.
Těžká úloha – Duplicitní soubory
Zadání a výsledková listina úlohy
Mnoho uživatelů si sice stěžovalo, že lehká úloha není o tolik lehčí než tato, nicméně v této úloze šlo především o správnou volbu algoritmu a nutno podotknout, že jen pár soutěžních prací použilo rychlý a efektivní algoritmus.
Drtivá většina odevzdaných řešení porovnávala soubory ve stylu “každý s každým.” Zkrátka si napsali nějakou metodu, které předhodili dva soubory, metoda si pro každý z nich otevřela FileStream, oba soubory postupně načítala a porovnávala. Jakmile nalezla rozdíl, skončila. Toto řešení ale může být velmi pomalé, souborů může být dost a pokud máte 100 souborů, tak každý z nich čtete od začátku do konce řádově 100x (časová složitost N2). Disk je poměrně pomalé zařízení, takže 100x přečíst dvougigový soubor, to dá trochu zabrat.
Vylepšit to sice můžete tak, že soubory rozdělíte na skupinky podle velikosti a porovnáváte každý s každým jen v rámci té skupinky, ale i tak existuje sada souborů (jakkoliv v praxi neupotřebitelná a nesmyslná), na které bude hledání trvat strašně dlouho. Poslední hřebík do rakve tomu dali ti, kteří soubory porovnávali doslova po bajtech, prostě ve while smyčce četli z každého souboru pomocí ReadByte. Ano, ty streamy si to interně přednačítávají a cacheují, ale i tak, čtení po bajtech má dost velkou režii, takže je daleko rychlejší načítat to třeba po 64kB.
Našli se i experti, kteří soubory natvrdo načetli do paměti přes File.ReadAllBytes a pak tato pole porovnávali (anebo si ty bajty převedli ještě na string a porovnali tyto stringy). Mimochodem, víte, jak se dá zjistit velikost souboru? No přece File.ReadAllBytes(“soubor”).Length. I tento způsob se objevil, představte si, že chcete zjistit velikost dvougigového souboru. Takhle tento soubor celý načtete do paměti jenom proto, abyste zjistili velikost toho pole. Takhle tedy opravdu ne.
Zarazilo nás, jak málo lidí napadlo použít hashování. Nejznámější hashovací algoritmy jsou třeba MD5 a SHA, pár lidí použilo i CRC. Hashovací algoritmus dostane na vstup libovolně dlouhá data a spočítá z nich hodnotu nějaké pevné délky (MD5 má např. 128 bitů). Mezi základní vlastnosti hashování patří to, že je velice těžké najít takové dva vstupy, které dají jako výsledek stejný hash. I když MD5 se dnes již nemá používat pro zabezpečení dat, pro naše účely se hodí velmi pěkně. Navíc je to standardní algoritmus, takže jej .NET Framework umí a nemusíme nic složitě programovat.
Z každého souboru si stačí tedy spočítat hash (což je krátká hodnota, která se vejde do paměti) a mezi sebou porovnávat jen ty hashe. Pokud jsou stejné hashe, je stejný i obsah souboru (u CRC je to dobré ověřit přečtením binárního obsahu, u MD5 či SHA je to zbytečné, pravděpodobnost kolize je mizivá, u MD5 je to 1 ku 2^128, což je v desítkovém zápisu asi 40ciferné číslo, tolik souborů na disku nikdy mít nebudete). Hashe samozřejmě v rámci skupiny musíme porovnat každý s každým, ale tyto hashe jsou malé a vejdou se nám do paměti. Pravděpodobnost, že by dva soubory daly stejný hash, je opravdu mizivá, takže takové situace nemusíme vůbec řešit.
Samozřejmě není ani nutné počítat hash pro všechny soubory; pokud si soubory rozdělíte na skupiny podle jejich velikosti, není nutné počítat hash u souborů, které jsou ve skupince samy. Navíc je u dlouhých souborů vhodné rozdělit si je na části třeba po 4 MB a kontrolovat postupně hashe těchto bloků (a počítat si je až ve chvíli, kdy jsou skutečně potřeba), abychom nemuseli celé gigové soubory procházet. U každého souboru si pak v paměti držíme jen seznam hashů v jednotlivých 4MB blocích, a nový blok počítáme až v okamžiku, kdy je skutečně potřeba (když mají 2 soubory stejnou sadu hashů předchozích). Tím budeme každý soubor číst maximálně jednou, a to ještě ve většině případů ne celý.
Jinak pokud už používáte vestavěné třídy pro počítání MD5, opět není vhodné předat metodě ComputeHash výsledek volání ReadAllBytes, která celý soubor načte do paměti, metoda ComputeHash bere jako parametr i stream. Tolik k volbě algoritmu a k efektivitě řešení.
Po funkční stránce mnoho prací postrádalo poměrně důležitou možnost smazání nalezených duplicit, hlavním vílem aplikace bylo najít duplikátní soubory a zbavit se jich. Trochu nás také překvapilo, že i ti nejlepší řešitelé často zapomínali na jednu základní věc při procházení souborů - kontrolovat, zda má program vůbec ke složce (potažmo přímo k souboru) práva pro čtení. Velká část aplikací na tom padala.
Pokud se jedná o technologickou stránku věci, tak několik soutěžících využilo WPF, unit testy, efektivně návrhové vzory a dodali nápovědu a dokumentaci, což se samozřejmě promítlo také v celkovém hodnocení.