Proč se počítají operace a ne sekundy
Přirozená otázka zní „jak dlouho to trvá“. Přirozená odpověď — změřit to stopkami — je překvapivě k ničemu, a stojí za to vědět proč.
Naměřená milisekunda závisí na procesoru, na tom, co zrovna běží vedle, na tom, jestli se stihl rozehřát překladač za běhu, a na tom, kdy naposledy uklízel správce paměti. Totéž měření dá při druhém spuštění jiné číslo. Nedá se z něj tedy nic dokázat a nedá se to ani zkontrolovat testem.
Počet porovnání je jiný druh čísla. Je stejný na každém stroji, při každém spuštění, navždycky. Je to veličina, o které mluví ta teorie — a hlavně se o něm dají tvrdit přesné věci: třídění výběrem udělá na poli o n prvcích právě n(n−1)/2 porovnání. Ne přibližně. Právě tolik.
Proto je v téhle labce každý algoritmus instrumentovaný: sám si počítá porovnání, přesuny, alokace a modelované výpadky cache. Nic se neodhaduje a nic se neměří stopkami. A testy v repu díky tomu můžou držet identity místo dojmů.
Co se počítá
| veličina | proč zvlášť |
|---|---|
| porovnání | to, o čem mluví klasická analýza |
| zápisy | u některých algoritmů jich je řádově víc než porovnání — a u pomalé paměti rozhodují |
| alokace | skrytá cena, kterou porovnání nezachytí (kapitola 5 a 11) |
| výpadky cache | modelované, ne měřené — vysvětlují to, co složitost neříká (kapitola 10) |
To rozdělení není pedanterie. Třídění výběrem dělá kvadraticky mnoho porovnání, ale jen lineárně mnoho přesunů — a když je zápis drahý (paměť flash, síťová položka), je to najednou rozumná volba, ačkoli je „stejně kvadratické“ jako ostatní.