Diskova cache a moje dalsi cache

[Pavel Kankovsky]

On Mon, 8 Sep 2008, Martin `MJ' Mares wrote:

> Tohle je ovšem značně závislé na použitém výpočetním modelu 

To je pravda, ale...

> -- na Turingově stroji je to samozřejmě pravda, na Random Access Machine
> (což je pro běžné algoritmy častěji přijímaný model) už nikoliv.

Pokud se složitost u RAM počítá opravdu pořádně, tak se AFAIK musí
zohlednit velikosti zpracovávaných hodnot (nejen prostý počet instrukcí),
čili pořád platí, že a porovnání dvou hodnot klíčů budu obecně potřebovat
čas lineární vzhledem k počtu jejich bitů. Připouštím, že u výpočtu
hašovací hodnoty to lze občas vzít zkratkou a lze jí spočítat jen z určité
části vstupu (např. typické mod 2^n).

I když teď vidím, že je tam pak háček druhého stupně: to samé pak musím
pro RAM aplikovat i na hodnoty použité coby ukazatele, čili přístup přes
ukazatel mě stojí až log n, kde n je max. použitá adresa. Hašovací tabulka
tuto penalizaci dostane s velkou pravděpodobností jen jednou (tedy
aditivně), ale strom při každém průchodu skrz uzel (čili multiplikativně).
(V případě TM, když už tady byl zmíněn, je to penále cca lineární vůči
délce pásky.)

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