Diskova cache a moje dalsi cache

[Pavel Kankovsky]

On Sun, 7 Sep 2008, Dalibor Straka wrote:

> Tak zavadejici vyrok by se dal rici i o spojaku.

V principu ano. Z přísně aplikovaného hlediska asymptotické složitosti se
programy běžící na reálném počítači na ty, které mají složitost omezenu
konstantou, a ty, které se navěky zacyklí. :)

Z praktického hlediska je to ovšem tak, že rozdíl mezi 10 a 100
"teoretickými instrukcemi" může být vlastnostmi reálného počítače
eliminován nebo dokonce otočen v neprospěch těch 10, zatímco u
100 vs 10^9 se asi shodneme, že první možnost bude v praxi vždy řádově
rychlejší než ta druhá.

A navíc: složitost vyhledávání v radixovém stromu je \Theta(l), kde l
je délka klíče v bitech. Ovšem operace jako porovnání klíče nebo spočtení
hašovací hodnoty musí zpracovat celý vstup, a tedy mají složitost
\Omega(l), uvažujme optimisticky \Theta(l). Hašování může být O(1) pouze
za předpokladu, že \Theta(l) \subset O(1), čili že l je omezeno
konstantou, což je předpoklad téhož typu, jako ten diskutovaný.
A pak je O(1) i radixový strom.

A konečně (ať je to trochu relevantní k tématu konference): při množství
lidí, kteří se snaží optimalizovat v jádře každou ptákovinu, je poměrně
nepravděpodobné, že by tamní implementace byla podstatně horší než nějaká
dobře známá alternativa. :)

-- 
Pavel Kankovsky aka Peak                          / Jeremiah 9:21        \
"For death is come up into our MS Windows(tm)..." \ 21th century edition /