Array (Datentyp)

Definition und Begriffe

Ein Array (englisch für Anordnung, Bereich, Aufstellung) ist in der Informatik eine Datenstruktur, mit der viele gleichartig strukturierte Daten verarbeitet werden sollen. Der Zugriff auf einzelne Inhalte erfolgt über Indizes. Häufig verwendete Synonyme sind Tabelle (Table), Vektor, Reihe, Reihung, Aufstellung, Bereich, Matrix u. a. Zum Teil wird auch der Ausdruck Feld (aus englisch 'field') benutzt; dieser ist aber mehrdeutig: Ein 'Datenfeld' im Quelltext eines Programms ist kein Datentyp, sondern ein benannter Speicherplatz, der einen Datentyp hat – unabhängig davon, ob er Teil eines Arrays oder einer anderen Datenstruktur (z. B. Verbund, Record) ist. Diese doppelte Bedeutung von 'Feld' führt immer wieder zu Diskussionen; der gängigere englische und allgemein verstandene Begriff ist Array. Auch die einzelnen Array-Inhalte haben mehrere Bezeichnungen: Element, Komponente, Unterfeld, Feldelement, indizierte Variable, teils ebenfalls Feld oder Datenfeld. Dabei kann man als Untermenge entweder die über einen Index adressierten Daten ('vertikale' Dimension) oder innerhalb der Struktur definierte Datenfelder ('horizontale' Sicht) verstehen.

Indizes und sprachspezifische Unterschiede

Zur Adressierung der Array-Inhalte wird ein Index verwendet. Bei Standard-Arrays in höheren Programmiersprachen ist der Index eine Ganzzahl; assoziative Arrays erlauben dagegen beliebige, aber eindeutige Schlüsselwerte. Bei mehrdimensionalen Arrays gibt es für jede Dimension einen unabhängigen Index und eine unabhängige Länge. In streng strukturierten Sprachen wird die Zulässigkeit eines Indexes zur Laufzeit geprüft, damit Zugriffe auf ungültige Speicherbereiche verhindert werden. Arrays können in den meisten Programmiersprachen angelegt werden, aber Compiler unterstützen sie unterschiedlich, z. B. hinsichtlich: Anzahl der möglichen Dimensionen, maximale Array-Größe, Indexbereich (ab 0, ab 1, beliebig, auch negativ), feste oder dynamische Anzahl der Unterfelder, einheitliche oder individuelle Länge der Elementarfelder, unterstützte Operationen (auf Elemente, Strukturen, Dimensionen, ganze Arrays) sowie Wertzuweisung per Deklaration oder Zuweisungsbefehl. Auch das Adressierungsverfahren variiert: Der Index kann eine Ganzzahl-Variable sein (Adresse wird bei Bezugnahme berechnet), ein Direktwert (Adresse zur Compilezeit berechnet), einen relativen Abstand zum Array-Beginn enthalten oder ein Suchschlüssel sein. Die Deklarationssyntax ist sprachspezifisch, z. B. NameX(100) in PL/I, NameX[100] in C/C++ und Java, NameX array(100) in Modula-2, NameX OCCURS 100 in Cobol, Dim NameX(100) in VBA. In Assemblersprachen werden Arrays nicht speziell unterstützt; der Programmierer muss sie explizit 'nachbauen', etwa über ein Indexregister.

Array-Varianten: Standard, dynamisch und assoziativ

Beim Standard-Array werden Daten eines einheitlichen Datentyps so im Speicher abgelegt, dass der Zugriff über Indizes möglich ist. Der Index beginnt bei N Elementen je nach Sprache bei 0 (C++: 0,…,N-1) oder 1 (Fortran: 1,…,N) und kann oft auch frei gewählt werden (z. B. 42,…,N+41). Ein dynamisches Array (Array-Liste) ist eine Listendatenstruktur mit variabler Größe und wahlfreiem Zugriff, bei der Elemente hinzugefügt oder entfernt werden können; es wird von Standardbibliotheken vieler moderner Sprachen bereitgestellt. Es ist nicht dasselbe wie ein dynamisch zugewiesenes Array, dessen Größe bei der Zuweisung festgelegt wird – ein dynamisches Array kann ein solches Array fester Größe allerdings als Back-End verwenden. Dabei werden die Elemente am Anfang eines überdimensionierten festen Arrays zusammenhängend gespeichert; der Rest dient als Reserve. Elemente lassen sich am Ende in konstanter Laufzeit hinzufügen, bis die Kapazität erschöpft ist; dann muss das zugrunde liegende Array vergrößert werden, was teuer ist, weil ein neues Array zugewiesen und alle Elemente kopiert werden müssen. Entfernen am Ende ist in konstanter Zeit möglich. Die Anzahl der tatsächlich genutzten Elemente ist die logische Größe, die Größe des zugrunde liegenden Arrays die Kapazität (physische Größe). Ein dynamisches Array wird benötigt, wenn die maximale logische Größe vor der Speicherreservierung nicht festgelegt oder berechnet werden kann. Das assoziative Array (Zuordnungstabelle) verwendet als Indizes keine ganzzahligen Werte, sondern Schlüssel, die beliebigen Typs haben können (z. B. Zeichenketten) und ein Element eindeutig identifizieren müssen. Beispiel: Die Produktnummer als Index in einer Produkttabelle, z. B. Produkt = ProdBezeichn(ProdNr). 'Assoziativ' nennt man sie nur, wenn die Programmiersprache den die Datenadresse berechnenden Suchalgorithmus automatisch generiert; am häufigsten werden sie als Hashtabelle umgesetzt.

Element-Datentyp und Dimensionen

In statisch typisierenden Sprachen sind Array-Inhalte oft auf einen einzelnen Datentyp beschränkt; ein Spezialfall 'weitgehend beliebiger Inhalt' ist mitunter möglich, in objektorientierten Sprachen oft über Polymorphie einer allgemeinen Basisklasse. In dynamisch typisierenden Sprachen können meist Objekte oder Datenstrukturen fast beliebig gespeichert werden; dort werden jedoch oft nur assoziative Arrays angeboten. In den meisten Programmiersprachen kann ein Array ein- oder mehrdimensional sein; mehrdimensionale Arrays verwenden für jede Dimension einen eigenen Index. Eindimensionale Arrays funktionieren wie eine Liste; Beispiel: Vektor := array(3) of float mit Vektor := (0.5, 1.7, -0.2) als Punkt im ℝ³ – Vektor[2] liefert die y-Komponente 1.7. Auch ein Array aus Verbund-Datentypen ist möglich, z. B. Produkt := array(100) of structure{ProdNr, Einkaufspreis, Verkaufspreis, Lagerbestand}; der Zugriff erfolgt dann z. B. über Produkt(Index).ProdNr. Beim in-sich-mehrdimensionalen Array ('inhärent mehrdimensional' nach ISO/IEC 11404) beinhaltet nur die letzte Dimension die Elemente; jede Information ist allen Dimensionen (z. B. Breite, Höhe, Tiefe) gleichermaßen zuzurechnen. Der Zugriff erfolgt unter Angabe aller Indizes, z. B. AttrName(i1,i2). Solche Arrays werden, vor allem im Deep Learning, auch als Tensoren bezeichnet. Beispiel zweidimensional (Matrix/Tabelle): Schachbrett := array(8,8) of String; ein Element ist durch Zeile und Spalte eindeutig adressiert. Beim Schach heißen die Spalten Linien ('a'–'h') und die Zeilen Reihen ('1'–'8'); der Eröffnungszug 'd2–d4' entspricht etwa den Anweisungen Schachbrett[5,4] := Schachbrett[5,2] und Schachbrett[5,2] := ''. Ein vierdimensionales Beispiel: temperatur := array(50,50,50,1000) of float speichert für einen Brennraum (x,y,z von 1 bis 50 mm) Temperaturen für jede Millisekunde einer Sekunde; Zugriff z. B. temperatur(7,12,48,617). Beim 'Array enthält weiteres Array' (verzweigtes Array, nach ISO/IEC 11404 'induziert mehrdimensional') enthält ein Array als Element wiederum Arrays über mehrere Stufen; die Anzahl der Dimensionen ergibt sich aus der Schachtelungstiefe des innersten Arrays. Beispiel Lagerregal: Regalboden := array(10) (Dimension 1), je Boden WZ_Box := array(5) Werkzeugboxen (Dimension 2) mit Bezeichnung und Anzahl; Zugriffe wie RB_Bezei(I1) oder WZ_Bezei(I1,I2). Indizes innerer Dimensionen werden nur angegeben, wenn aus ihnen Informationen angesprochen werden.

Adressierung, Speicherabbildungsfunktion und Programmeffizienz

Obwohl Arrays oft räumlich dargestellt werden, werden ihre Elemente in einem linearen Speicher abgelegt: Vektoren hintereinander, zweidimensionale Matrizen als Zeilen- oder Spaltenvektoren hintereinander, dreidimensionale Arrays als viele Matrizen hintereinander. Die Speicheradresse eines Elements ergibt sich aus der Basisadresse des ersten Elements plus einer indexabhängigen Distanz: (aktueller Index minus Index-Erstwert) multipliziert mit der Länge der Array-Datengruppe. Bei den meisten Programmiersprachen übernimmt der Compiler diese Adressierung; in Assembler muss sie explizit programmiert werden. Beispiel: Ein 2-dimensionales Array mit 4 Zeilen (1..4) und 7 Spalten (1..7), jedes Element 4 Byte, Startadresse base; Zugriff auf (Zeile 3, Spalte 6): 2 zu überspringende Zeilen × 7 Elemente × 4 Byte = 56, plus 5 zu überspringende Spalten × 4 Byte = 20, also Adresse base + 76. Allgemein nennt man die Formel zur Adressberechnung in einem n-dimensionalen Array Speicherabbildungsfunktion; sie ist nur eine von mindestens zwei Alternativen, je nachdem, ob die Indizes zeilenweise (Row-major order) oder spaltenweise (Column-major order) zu Speicherblöcken zusammengefasst werden. Die Berechnung ist normalerweise Aufgabe der Laufzeitumgebung des Compilers. Da die Produkte in der Formel konstant sind, können sie einmalig berechnet werden; der daraus resultierende Dope-Vektor d ermöglicht eine sehr schnelle Berechnung der Adresse jedes Elements über die Formel (j_t − i_t) · d_t. Zur Programmeffizienz: Die Array-Verarbeitung erfordert im Gegensatz zu ohne Index adressierbaren Datenfeldern zusätzlichen Aufwand für die Adressberechnung. Der Programmierer kann die vom Compiler erzeugten Berechnungsbefehle teilweise beeinflussen und optimieren, z. B.: Literale als Index (Adresse meist zur Compilezeit berechnet), geeignete interne Datenformate für Indexvariablen (spart Formatkonvertierung), Wiederverwenden bereits berechneter Zugriffsadressen, geschickte Reihenfolge der Dimensionen (Zugriffe auf direkt aufeinander folgende Adressen im RAM sind am schnellsten, weil Lokalität Caching ermöglicht – der innerste Schleifenindex sollte aufeinanderfolgenden Elementen entsprechen), Ansprechen übergeordneter Verbundstrukturen statt vieler Einzel-Datenfelder (Adressberechnung nur einmal je Verbund) oder Auslagern häufig mit gleichem Index zugegriffener Array-Inhalte in einen direkt adressierbaren Speicherbereich. Ob solche Maßnahmen nötig sind, hängt von Faktoren ab; nicht relevant sind sie, wenn der Compiler automatisch optimiert oder wenn das Programm selten bzw. nur kurz läuft oder Array-Befehle nur einen geringen Teil der Verarbeitung ausmachen. Derartige Maßnahmen sollten aus Gründen der Lesbarkeit stets gut dokumentiert sein.