Tři krásné quicksorty - záznam přednášky v Google

Dnes jsem narazil na záznam přednášky Jona Bentleyho Three Beautiful Quicksorts, kterou měl nedávno v Google. Byť normálně videa, podcasty a podobné multimediálnosti příliš nemusím¹, abstrakt začínající větou "This talk describes three of the most beautiful pieces of code that I have ever written." mě k přehrání přesvědčil.

V první části přednášky John představil klasickou implementaci quicksortu, ukázal, proč je obtížně pochopitelná a náchylná k chybám, a navrhl implementaci lepší (dle něj "krásnou").

Ve druhé části pak implementaci zanalyzoval z pohledu počtu porovnání. Tato část přednášky je asi nejzajímavější, hezky ukazuje různé optimalizační techniky a především spojitost těchto technik s matematikou. Nápadité bylo i přirovnání datových struktur ke "zmraženým algoritmům" – uvidím, zda si na to při učení na státnice za pár měsíců vzpomenu.

Poslední část přednášky Jon věnoval ukázce implementace real-world quicksortu v céčkové knihovní funkci qsort. Zde bylo hezky vidět, jak jsou požadavky na krásu kódu v přímém střetu se snahou o nekompromisní výkon. Jonova implementace z toho ale nakonec vyšla celkem dobře.

Byť nakonec byla přednáška o něčem trochu jiném, než jsem čekal, vůbec mi to nevadilo. Asi jsem si potřeboval odpočinout od lovení bugů v diplomce a hory jednotvárných řádků kódu v PHPčku trochou teoretické informatiky, byť v celkem odlehčeném podání. Hezké bylo i to, že celá přednáška byla doplněna řadou citátů na téma krásy a jednoduchosti, které jí daly až téměř metafyzický nádech. Do seznamu knížek k přečtení jsem si také po shlédnutí zařadil Beautiful Code, na kterou Jon v přednášce upozorňoval. Snad si na ni najdu čas.

Zájemce o video bych měl asi upozornit, že bez znalostí odpovídajících zhruba výuce programování a algoritmů v prváku na matfyzu nemá jeho shlédnutí nejspíš smysl.

Poznámky

1. Množství informací za jednotku času je u nich jednoduše příliš nízké a na rozdíl od textu nejde moc dobře přeskakovat nezajímavé části.