3.1 Hintergrund: der Speicherplatz im Rechner
Um überhaupt ein Gefühl für die Problematik zu bekommen, müssen wir zumindest im Prinzip
verstehen,
wie der Speicher eines Rechners organisiert sind. Bei der binären Suche beispielsweise sind wir
ja davon ausgegangen, dass man mit einer Code-Zeile wie
c = array[i];
in einem Schritt die -te Zelle des Arrays auslesen kann. Ist dies eine vernünftige
Annahme?
In sehr alten Rechnern wahrscheinlich nicht: der externe Speicher war ein Magnetband; um an die
-te Zelle
zu gelangen, muss man erst einmal dort hinspulen; wenn wir Pech haben, ist weit weg.
Auch bei Festplatten (Hard disk drives, HDD) spielt die physische Anordnung eine Rolle: der
Lesekopf
muss die entsprechende Spur finden, und dann abwarten, bis die Platte sich an die richtige
Stelle rotiert hat.
Moderne Rechner (Stand 2023) verwenden allerdings eher Solid-State-Drives (SSD), die ohne
bewegliche Teile
auskommen. Für sie ist die Annahme einer festen, konstanten Zugriffszeit realistischer.
Wenn die Zugriffszeit auf Zellen in unserem Speicher unabhängig von dem "Aufenthaltsort" der
Zelle ist,
sprechen wir von einem Random Access Memory (RAM).
Stellen wir uns das RAM als großes Array aus Zellen vor: Mem[0...N-1]
.
Es unterstützt Lese- und Schreiboperationen der Art
write <data> <address>
read <address>
in konstanter Zeit, also unabhängig von Wert von
<data>
und
<address>
.