Proč bychom si neřešili

aneb krátké divadelní představení pro začínající účastníky KSP

Osoby na scéně:

T: Tomáš Marný, začínající účastník KSP. Právě sedí u počítače v městské knihovně, jehož kabely se ztrácejí kdesi mezi regály. Za okny je ospalé podzimní odpoledne.

T: Tomáš Marný, dlouholetý organizátor KSP. Tentýž počítač v téže knihovně, totéž ospalé odpoledne, jen o 10 let později. Vlastně i tentýž Tomáš, ale ještě o tom neví.

Začínáme …

T: (vztekle odhazuje svazek řešení, kterým probleskují pestrobarevné poznámky opravovatelů, a nemaje si komu postěžovat, bezmyšlenkovitě ťuká do klávesnice) Sakryš! Už zase jenom dva body, to mi ti mizerové snad dělají naschvál, vždyť to přece mám úplně správně!

T: (odkládá knížku o geometrii L-prostoru a jelikož začíná tušit, co se děje, opatrně vyťukává odpověď) Ahoj Tomáši, tady je také Tomáš. Asi mne ještě neznáš, i když já tebe znám docela dobře. Oni ti organizátoři jsou docela svérázní lidé, jenže dva body za dobré řešení by nedal ani jeden z nich. Pojď se na to podívat. Co jsi jim to vlastně poslal?

T: (trochu udiveně, protože nečekal, že mu na jeho výkřik někdo odpoví, a ještě méně, že by jeho problémy někoho zajímaly) No, byla to taková děsně jednoduchá úloha s převodem čísla do dvojkové soustavy. Hned mi bylo jasné, jak na to. Co říkáš tomuhle:

{ Převod čísel do dvojkové soustavy. Funguje
  jednoduše: přečte si číslo a pak ho vypisuje
  ve dvojkové soustavě. Doběhne do sekundy. }

uses crt;
var	cislo,index:integer;		{ číslo a index }
	vysl:string;			{ výsledek }
begin
repeat
	clrscr; textcolor(red);		{ smažeme obrazovku }
	write('Zadej cislo: '); textcolor(white);
	read(cislo);			{ přečteme číslo }
until cislo>=0;			{ nedáme pokoj než zadá kladné }
for index := 0 to trunc(ln(cislo)/ln(2)) do begin
	r := trunc(exp(ln(2)*index));	{ mocnina }
	if (cislo div r) mod 2 = 0 then
		vysl := '0' + vysl	{ výsledek je 0 }
	else
		vysl := '1' + vysl;	{ jednička }
end;					{ konec cyklu }
write(vysl);				{ výsledek }
end.

T: (zděšeně) To tedy zírám. Uff. Určitě jsi to ani nevyzkoušel … vlastně ani nezkompiloval.

T: (udiveně) No, nevyzkoušel. Ale jaks' to poznal?

T: Předně: zkompilovat by Ti to ani nešlo, protože proměnná r není nikde deklarovaná. Ale ani pak to nebude fungovat, zapomínáš totiž inicializovat vysl.

T: Dobře, to jsou přeci maličkosti. Hlavní je, že to funguje.

T: Jenže nefunguje. Třeba pro nulu nastane běhová chyba, protože z nuly neexistuje logaritmus, a pro mocniny dvojky to také většinou nevyjde, protože kvůli zaokrouhlovacím chybám bude podíl logaritmů o maličko menší než celé číslo, a tak ho trunc ořízne na o 1 méně, než je správně, a zapomeneš vypsat první číslici. Zkrátka pokud opravdu nevíš, co děláš, je daleko lepší s celočíselnými vstupy zacházet jenom celočíselně, žádný real.

T: To je fakt. Ale na to mně ani neupozornili. Zato to žalostné zavytí na začátku programu … Co tím vlastně chtěli říct?

T: Že je zbytečné věnovat tolik místa v programu všelijakému pozlátku, jako je třeba mazání obrazovky nebo barvičky. Angličané tomu výstižně říkají "bells and whistles". Všechno to jsou věci, které by skutečného uživatele možná potěšily, ale v KSP jsou spíš na obtíž, protože se mezi nimi ztrácí to, o co opravdu jde. Stejně tak není potřeba testovat korektnost vstupu.

T: A co znamenají ty otazníky u komentářů? Vždyť jsem s nimi dal takovou práci.

T: Ono jich sice je spousta, ale mají jednu vadu: jsou úplně k ničemu. Kterým endem končí který cyklus, každý vidí (či spíš by viděl, kdybys program rozumně odsazoval), stejně tak, že read čte číslo ze vstupu. A popis v úvodu je úplně totéž. Ovšem naproti tomu třeba není zřejmé, co znamenají ty kejkle s logaritmy a exponenciálami, a ty jsi vůbec neokomentoval.

T: (trochu zmateně) A co tam tedy mám psát?

T: Zkus začít tím, že vysvětlíš, jakou základní myšlenku Tvůj algoritmus má, případně dokážeš, že opravdu funguje (pokud to není zřejmé), a program pak napíšeš co nejpřímočařeji – když se budeš držet popisu algoritmu a proměnné budeš pojmenovávat výstižně, hned bude vidět, co program dělá, i když v něm moc komentářů nebude. Výstižně ovšem vůbec nemusí znamenat dlouze – pro obyčejnou indexovací proměnnou je opravdu nejlepší název i. Komentuj jenom místa, která nejsou všem jasná, kde třeba používáš nějaký trik. Zkus si třeba představit, že chceš svému kamarádovi, vysvětlit, jak program funguje. A také si to po sobě nezapomeň pozorně přečíst, gramatické a pravopisné chyby v češtině jsou úplně stejně špatně, jako syntaktické chyby v programu.

T: Jak Tě tak poslouchám, to by tam ani ten program nemusel být, ne?

T: Máš pravdu, nemusel. Kdybys popis algoritmu napsal tak, že si každý dokáže detailně představit, jak by program vypadal, je program opravdu zbytečný. Jenže málokdy poznáš s jistotou, že to tak je, takže je lepší programy pokaždé psát, třeba tím usnadníš práci někomu, kdo se bude už druhou hodinu marně snažit Tvůj popis algoritmu pochopit. A nakonec i Tebe psaní a ladění programu donutí všechno si pořádně rozmyslet, zvlášť různé okrajové případy, jako třeba ty nuly.

T: A když používám nějaký standardní algoritmus?

T: Pokud je dobře známý (třeba proto, že byl v minulé kuchařce), tak ho samozřejmě podrobně vysvětlovat nemusíš. Stačí, když řekneš, jaký algoritmus použiješ a kde se dá najít. I v programu ho pak můžeš vynechat (byť se tím připravíš o možnost ladění).

T: OK, a co ta poznámka o složitosti? Tu už mi tam psali minule, tak jsem si to přesně změřil a opravdu to vždycky doběhne do sekundy. Co to tedy ta časová složitost je a k čemu slouží?

T: Prakticky každá úloha se dá řešit mnoha různými algoritmy. A jak už to chodí, nejsou všechny stejně dobré – často se liší tím, že některý pro nějaký vstup doběhne ihned, zatímco jiný se pro tentýž vstup loudá želvím krokem celé roky. Pravda, oba nakonec vydají správný výsledek, ale asi budeš souhlasit, že ten druhý je vcelku nanic.

Takže když vymyslíš nějaké řešení, měl by ses hned sám sebe zeptat, jak je rychlé, čili jak dlouho pro který vstup poběží. Obvykle doba běhu nijak zvlášť nezávisí na konkrétních číslech na vstupu, jenom na jejich počtu (velikosti vstupu). Také nemá smysl měřit se stopkami v ruce časy v sekundách, už proto, že by pro různé počítače vycházely naprosto různě. Takže si raději zvolíme nějaké elementární operace a za časovou složitost prohlásíme funkci, která nám pro každou velikost vstupu řekne, kolik operací program spotřebuje pro vstupy této velikosti. A kdyby se to pro různé vstupy téže velikosti lišilo, prostě si z časů pro danou velikost vybereme maximum.

T: Hmm, a co to přesně jsou ty elementární operace?

T: Běžné aritmetické operace – sčítání, odčítání, násobení, porovnávání; také základní řídící konstrukce, jako jsou třeba skoky a podmíněné skoky. Zkrátka to, co normální procesor zvládne jednou nebo několika instrukcemi. (šeptem) Ale psst, ono to je tak trochu jedno – ať si vymyslíš libovolnou rozumnou sadu operací, stejně se počet operací v programu změní jen konstanta-krát a na tom, jak za chvíli uvidíme, moc nezáleží. Ovšem to (rozumnou) je důležité, nesmíš si za základní operaci zvolit třeba zkopírování celého pole nebo dokonce jeho setřídění, to by Ti nikdo neuvěřil.

T: (udiveně) A není strašně těžké spočítat, kolik těch operací bude?

T: Kdybys to chtěl spočítat přesně, tak to opravdu těžké bude. Ale ono málokdy záleží na přesném počtu, obvykle se zajímáme jenom o to, jak rychle ten počet roste s velikostí vstupu. Všelijaké konstanty přitom budeme ignorovat (ty stejně závisí na přesné definici operací), takže čas 32n2 pro nás bude totéž jako n2. Dokonce i t(n)=n2+42n-5 je totéž, protože pro n>= 42 je t(n) <= 2n2. Ovšem T(n)=n3/1000 už roste rychleji, ačkoliv to bude poznat až pro velká n (konkrétně n > 1000). Proto pokud je časová složitost polynom, záleží jenom na jeho stupni: rozlišujeme složitost lineární (c*n), kvadratickou (c*n2), kubickou (c*n3) atd.

T: To je krásně jednoduché. Žádné další nejsou?

T: Jsou, a kolik! Někdy třeba narazíš na algoritmy, které jsou rychlejší než lineární. Takové si ani nemohou stihnout přečíst celý vstup, ovšem pokud ho dostanou připravený v poli, nemusí to vadit. Třeba vyhledávání půlením intervalů má složitost řádu log n (logaritmickou; všimni si, že na základu logaritmu nezáleží, protože loga x = logb x / logb a, a proto se různé logaritmy liší zase jenom konstanta-krát a my přeci na konstanty nevěříme). Naopak některé želvovité algoritmy oplývají složitostí řádu 2n (exponenciální), takže už pro docela malá n můžeme na výsledek čekat pár hodin. Často také potkáš složitosti typu n* log n (tu mají mnohé třídící algoritmy a je mezi n a n2) nebo n* log 2 n (ta je mezi n* log n a n2).

T: Občas jsem také narazil na cosi jako O(n2). Co to je?

T: To je taková zkratka. Aby informatici nemuseli pořád psát "když zanedbáme multiplikativní konstanty, složitost lze shora omezit funkcí řádu n2", napíší raději "složitost je O(n2)". Pokud to chceš vědět přesně: když napíšeme f(n)=O(g(n)), znamená to, že existuje nějaká konstanta c>0 taková, že pro všechna dost velká n (přesněji od nějakého n0 dál) je f(n)<= c*g(n). Šikovná věcička, ale pozor, je trochu nebezpečná. Vypadá totiž jako rovnost, ale nemůžeš obě strany prohodit (O(g(n))=f(n) prostě nedává smysl) a navíc je to vlastně nerovnost -- pokud napíšu f(n)=O(n3), říkám tím pouze, že (až na konstanty atd.) f roste nejvýše jako n3 – ve skutečnosti může růst mnohem pomaleji. Čili i o lineárním algoritmu můžeme říci, že má složitost O(n3) – bude to pravda, ale moc trefné to není. Pro úplnost dodávám, že existuje podobná značka Ω pro opačnou nerovnost, takže to, že nějaký algoritmus má složitost alespoň kvadratickou, mohu také napsat jako Ω(n2).

T: Jakou má tedy složitost ten můj algoritmus?

T: Tahle úloha zrovna do našeho způsobu měření velikosti vstupu moc nezapadá, protože vstupem je jediné číslo a doba výpočtu závisí jen na jeho hodnotě. Proto budeme časovou složitost studovat raději jako funkci té hodnoty.

T: (vítězoslavně) Takže je logaritmická!

T: Málem. For-cyklem opravdu projdeš O(log n)-krát (jednou pro každou číslici výsledku a těch je 1+trunc(log2 n)). Jenže jelikož si číslice skládáš do stringu, nesmíš zapomenout na to, že operace se stringem, třeba takové přiřazení stringů, nemá konstantní časovou složitost, nýbrž lineární v délce stringu. První přiřazení tedy bude trvat čas c, druhé 2c, třetí 3c až poslední řádově log n*c. To je dohromady O(log 2 n).

T: To je zrada! Jak můžu poznat, co trvá jak dlouho?

T: Pokud používáš jednoduché operace (toho druhu, jaké jsme před chvilkou považovali za elementární), můžeš se spolehnout na to, že trvají konstantně dlouho, čili O(1). Ale jakmile začneš využívat nějakých pokročilejších funkcí svého oblíbeného programovacího jazyka, už to začne být složitější. Tehdy je nejlepší představit si, jak taková funkce uvnitř funguje, a podle toho určit složitost. Možná bude implementována chytřeji a rychleji, než to dovedeš ty, ale málokdy hůře. A pokud si nedokážeš fungování takové funkce představit, je lepší se jí obloukem vyhnout.

T: A nešlo by tu úlohu vyřešit rychleji? Jak bys to napsal Ty?

T: Určitě šlo, stačí si všimnout toho, že namísto skládání čísel do stringu bys je mohl skládat do pole předem známé délky … nebo ještě lépe obrátit směr běhu cyklu a jednotlivé číslice vypisovat průběžně. Vypadalo by to asi takhle (rovnou Ti ukážu, jak k tomu napsat popis algoritmu):

Úlohu budeme řešit tak, že si všimneme, že n mod 2 je rovno poslední číslici dvojkového zápisu čísla n a celočíselným dělením čísla n číslem 2i odřízneme i posledních dvojkových číslic. Proto (n / 2i) mod 2 dává i-tou číslici dvojkového zápisu. Tento algoritmus má časovou složitost O(log n) (která je optimální, protože rychleji nelze ani vypsat výstup) a paměťovou složitost O(1).

var x,n:integer;
begin
	read(n);
	x := 1;
	while 2*x<=n do x:=2*x;
	{ x je nejbližší nižší mocnina 2 }
	while x>0 do begin
		write(n div x mod 2); { číslice řádu x }
		x := x div 2;
	end;
	writeln;
end.

T: To je krásně jednoduché!

T: To je. Většina úloh z KSP-čka se dá vyřešit na pár řádků. Samozřejmě napsat opravdu hezké a krátké řešení je velké umění a asi Ti ještě bude nějaký čas trvat, než se to naučíš (asi tomu nebudeš věřit, ale i autoři vzorových řešení často celý program několikrát přepisují, než se jim začne líbit). Ovšem pokud Tvé řešení má tisíc řádků a je plné objektů a volání exotických knihoven, skoro určitě je od správného na hony daleko a vysloužíš si za něj spíš než body další hrst sarkastických poznámek.

T: Když už jsi zmínil prostorovou složitost, ta se měří jak?

T: Prostorová (jinak také paměťová) složitost algoritmu udává množství paměti, které algoritmus spotřebuje, opět v závislosti na velikosti vstupu. Obvykle se do ní nepočítá velikost vstupu a výstupu, pokud algoritmus vstup pouze čte a do vstupu pouze zapisuje. Většinou se měří v paměťových buňkách, přičemž každá buňka pojme jedno číslo, jeden znak nebo jeden ukazatel (string už zabere tolik buněk, kolik je jeho délka, plus jednu buňku navíc na uchování té délky).

T: (s úsměvem takřka ďábelským) Ha! Takže skoro všechna vzorová řešení KSP vlastně mají konstantní časovou i prostorovou složitost, protože mají velikost vstupu omezenou nějakou konstantou.

T: Ne tak zhurta. Technicky vzato, máš pravdu. Ale ty konstanty tam jsou jenom proto, že dynamické alokování polí nebo seznamů podle skutečné velikosti vstupu je otročina, na které většinou není nic zajímavého a každý si ji snadno domyslí. Takže tam raději napíšeme konstantu, aby v programu bylo dobře vidět na ty opravdu důležité části.

T: A není to s tou prostorovou složitostí trochu podvod? Nemohl bych si třeba všechny proměnné zakódovat po bitech do jednoho dlouhatánského čísla a mít vždycky prostorovou složitost konstantní?

T: Máš pravdu, trochu podvod to opravdu je. Když se složitost zavádí pořádně (což už, jak název napovídá, není úplně jednoduché), neměří se prostor v paměťových buňkách, nýbrž přesně v bitech. Velikánská čísla proto zaberou daleko víc místa než malá a to už tak snadno neošidíš. Stejně se pak měří i velikost vstupu (čímž přestanou být problémy s naším příkladem, jelikož ten má pak na vstupu logaritmicky mnoho desítkových číslic) a časová složitost elementárních operací pak není jednotková, nýbrž závisí na počtu bitů čísel, se kterými se právě počítá. Pak do sebe všechno dokonale zapadá a žádné paradoxy nenastávají. Jenže je s tím zase o dost víc práce než předtím. Většinou naštěstí pomůže takový malý úskok: budeme složitosti počítat postaru, jen si zavedeme omezení, že všechna čísla, se kterými pracujeme, musí být polynomy ve velikosti vstupu, čili maximálně nk pro nějaké k. Pak bude ta "pořádná" definice složitosti dávat vždy k* log n-krát větší hodnoty než ta "podvodná", takže vše bude fungovat.

T: (obdivně) Tedy klobouk dolů, Ty toho ale víš… Kde ses to všechno naučil?

T: (trochu rozpačitě) Každý začátek je těžký. To základní mně kdysi stejně jako Tobě někdo poradil, zbytek jsem si našel po knížkách (pěkné jsou například Algoritmy a programovací techniky od RNDr. Pavla Töpfera), ve vzorových řešeních KSP a pak na přednáškách na soustředění. Vyplatí se podívat se i do starších ročníků, ty se dají objevit třeba na webu nebo v ročenkách, které KSP každý rok vydává. A když nebudeš vědět, jak dál, klidně se mailem zeptej organizátorů.

T: Tak jo, díky moc, já už musím jít, už se nemůžu dočkat, až napíšu řešení další série.

T: Hodně štěstí, Tomáši. (pak dodá) Vím, že to zvládneš.

Opona.