Arrays

Den millionsten Wert eines Arrays zu lesen, kostet einen Schritt. Einen neuen Wert an den Anfang desselben Arrays zu setzen, verschiebt eine Million Werte.

Was eine Datenstruktur ist

Ein Programm, das eine Namensliste, eine Warteschlange von Druckaufträgen oder eine Preistabelle führt, muss diese Daten irgendwo speichern und Fragen dazu beantworten: Was ist das dritte Element, steht dieser Name in der Liste, welcher Auftrag ist als Nächstes dran? Eine Datenstruktur ist eine Art, Daten zu speichern, zusammen mit den Verfahren, die diese Fragen beantworten. Der MIT-Kurs 6.006 trennt hier zwei Ideen. Die Schnittstelle sagt, welche Operationen man verlangen kann, etwa „hol das Element an Position i“ oder „füg ein Element am Ende hinzu“. Die Datenstruktur ist, wie diese Operationen tatsächlich im Speicher ausgeführt werden. Hinter einer Schnittstelle können mehrere Datenstrukturen stehen, und sie können sich in der Geschwindigkeit gewaltig unterscheiden.

Dieser Kurs zählt wie der Algorithmenkurs Schritte, damit sich zwei Strukturen ohne Stoppuhr vergleichen lassen. In dieser Einheit ist ein Schritt das Lesen oder Schreiben einer Speicherzelle. Das Labor unten zählt sie für dich.

Ein Block von Zellen, Seite an Seite

Ein Array speichert seine Werte in einem lückenlosen Speicherblock, jeden Wert in einer gleich großen Zelle, nummeriert ab 0. Diese Anordnung macht Arrays schnell beim Lesen. Beginnt der Block an Adresse s und belegt jede Zelle c Bytes, dann liegt a[i] an Adresse s + i × c. Der Computer rechnet das mit einer Multiplikation und einer Addition aus und springt direkt dorthin, egal ob i 3 oder 3 000 000 ist. Die MIT-Unterlagen geben „get at(i)“ und „set at(i, x)“ für ein Array mit Θ(1) an. Das heißt, die Kosten wachsen nicht mit der Länge.

Dieselbe Anordnung macht Änderungen in der Mitte langsam. Angenommen, das Array enthält 7, 3, 9, 4, 6, und du willst eine 1 an den Anfang. Vor der 7 ist keine Lücke, also muss zuerst jeder Wert eine Zelle nach rechts rücken, angefangen beim letzten, damit nichts überschrieben wird. Das sind 5 Verschiebungen und 1 Schreibvorgang: 6 Schritte. Den vordersten Wert zu entfernen, ist das Spiegelbild: ihn lesen, dann die anderen 4 Werte eine Zelle nach links schieben. Einfügen an Position i in einem Array mit n Werten kostet n − i Verschiebungen plus einen Schreibvorgang. Der Anfang ist also die schlechteste Stelle und das Ende die beste.

Wenn der Block voll ist

Ein Speicherblock hat eine feste Größe. Was passiert also, wenn du einen Wert hinzufügst und jede Zelle belegt ist? Das Array muss einen neuen, größeren Block anfordern und jeden Wert hinüberkopieren, bevor es den neuen schreiben kann. Im Labor kostet ein Push auf den vollen Block mit 5 Zellen 5 Kopien und 1 Schreibvorgang. Würde das Array jedes Mal nur um eine Zelle wachsen, würde jeder Push alles kopieren, und n Pushs kosteten etwa n²/2 Kopien.

Die Lösung aus den MIT-Unterlagen: auf einmal kräftig wachsen, zum Beispiel durch Verdoppeln. Bei Kapazität 1 beginnend, wird kopiert, wenn das Array 1, 2, 4, 8 und 16 Werte enthält. 17 Pushs kosten also insgesamt 1 + 2 + 4 + 8 + 16 = 31 Kopien, weniger als 2 pro Push. Ein einzelner Push kann trotzdem langsam sein, aber jede lange Folge von Pushs mittelt sich auf konstante Kosten pro Push. Das nennt man amortisierte Θ(1)-Zeit. Ein JavaScript-Array verhält sich von außen so: MDN beschreibt Arrays als in der Größe veränderbar, und push und pop arbeiten am Ende, dem billigen Ende.

const a = [7, 3, 9, 4, 6];
console.log(a[3]);      // 4, ein Schritt
a.push(8);              // billig: das Ende
a.unshift(1);           // jeder Wert rückt eine Zelle nach rechts
console.log(a.join(" ")); // 1 7 3 9 4 6 8