Speicherabbildungsfunktion

Ein Feld (engl. Array [əˈɹeɪ, Betonung auf 2. Silbe] für „Anordnung“, „Aufstellung“, „Reihe“, „Reihung“, „Bereich“) bezeichnet in der Informatik eine Datenstruktur. Dabei wird zwischen einem Standard-Feld und dem assoziativen Array unterschieden.

Standard-Feld

Mit Hilfe eines Feldes können Daten eines üblicherweise einheitlichen Datentyps geordnet so im Speicher eines Computers abgelegt werden, dass ein Zugriff auf die Daten über einen Index möglich wird. Das (Standard-)Feld verwendet im Gegensatz zum assoziativen Feld einen ganzzahligen Index zur Adressierung.

Beispiele

Im folgenden wird ein symbolischer Beispielcode verwendet:

• Vektor (Eindimensional)

Vektor = (10, -11, 12)

So liefert Vektor(2) den Wert -11 (hier wird die Zahl 1 als Startindex definiert; in der Praxis ist es meistens 0).

• Matrix oder Tabelle (Zweidimensional)

In einer Matrix werden die waagrechten Einträge (Felder, Zellen) als Zeilen, die Senkrechten als Spalten bezeichnet. Ein einzelnes Element ist also durch Nennung von Zeile und Spalte eindeutig bezeichnet (adressiert). Üblich ist die Adressierung über ein Tupel (0,0) oder A1 für Spalte A, Zeile 1.

Schachfeld is array(8,8) of String

array definiert die Anordnung der Einträge, of den Typ des Eintrags

Schachfeld = („Turm_W“,„Springer_W“,„Läufer_W“, … ,„Turm_W“,
              „Bauer_W,„Bauer_W“   ,„Bauer_W“ , … ,„Bauer_W“,
              „Leer“  ,„Leer“,     ,„Leer“    , … ,„Leer“,
              „Leer“  ,„Leer“,     ,„Leer“    , … ,„Leer“,
              „Leer“  ,„Leer“,     ,„Leer“    , … ,„Leer“,
              „Leer“  ,„Leer“,     ,„Leer“    , … ,„Leer“,
              „Bauer_S,„Bauer_S“   ,„Bauer_S“ , … ,„Bauer_S“,
              „Turm_S“,„Springer_S“,„Läufer_S“, … ,„Turm_S“)

Die Beispielsanweisungen Schachfeld(3,3) := Schachfeld (1,2) und Schachfeld(1,2) := „Leer“ liefern den Eröffnungszug „Weißer Springer auf C3“.

In den meisten höheren Programmiersprachen ist das (Standard-)Feld Teil des Sprachumfangs. Die objektorientierten Programmiersprachen können diese Felder als Objekte nachbilden.

Adressierung eines Feldes

Letztlich müssen auch die in einem Feld gespeicherten Elemente in einem linearen Speicher abgelegt werden. Die Elemente eines eindimensionalen Vektors werden hintereinander im Speicher abgelegt, bei einer zweidimensionalen Matrix werden die Elemente entweder als Zeilen- oder als Spaltenvektoren hintereinander abgelegt, bei einem dreidimensionalen Feld werden entsprechend viele Matrizen hintereinander abgelegt, usw.

Speicherabbildungsfunktion

Ein Programm, das auf das Datenfeld oder einzelne Elemente davon zugreifen will, muss die Speicheradresse eines beliebigen Elements in einem Feld errechnen.

In einem n-dimensionalen Feld $A[i_1:k_1, i_2:k_2, \ldots, i_n:k_n]$ wird die Adresse eines Elements a[j₁,j₂,..,j_n] beispielsweise mit Hilfe der Formel $(j_n-i_n) + \sum_{s=1}^{n-1}( (j_s-i_s) \cdot \prod_{t=s+1}^{n} (k_t-i_t+1))$ berechnet. Man nennt diese Formel auch Speicherabbildungsfunktion.

Die dargestellte Formel ist nur eine von mindestens zwei Alternativen, je nachdem, in welcher Reihenfolge die Indices zu Speicherblöcken zusammengefasst werden, vom ersten hin zum letzten oder gerade umgekehrt. Im Englischen unterscheidet man hier Row-major order (zeilenweise Anordnung) und Column-major order (spaltenweise Anordnung). Es ist normalerweise Sache der Laufzeitumgebung des jeweiligen Compilers, welche Variante ein Programm verwendet.

Dope-Vektor

Da die Produkte $\prod_{t=s+1}^{n} (\ldots)$ in obiger Formel konstant sind, können sie einmalig berechnet werden, und der daraus resultierende Dope-Vektor d ermöglicht dann über die Formel $\deg_{t=1}^{n} (j_t-i_t) \cdot d_t$ eine sehr schnelle Berechnung der Adresse eines jeden gespeicherten Elements.

Programmeffizienz

Wenn in einem Computer so ein Feld im RAM gehalten wird, erfolgen Zugriffe auf Feldelemente in der Regel am schnellsten, wenn direkt aufeinander folgende Adressen abgerufen werden. Der Programmierer ist also gehalten, die Reihenfolge der Indices im Feld so festzulegen, dass das in der innersten Schleife auch so erfolgt. Da die Speicherabbildungsfunktion vom Compiler abhängt, sollte sich der Programmierer über diese Details informieren und dann im Programm den in der innersten Schleife durchlaufenen Index so definieren, dass er den Einerschritten in der Speicherbelegung entspricht.

Assoziatives Feld

Eine Sonderform bildet das „assoziative Array“. Es verwendet keinen numerischen Index, sondern sogenannte Schlüssel zur Indizierung und damit zur Adressierung der Elemente. Da die Anzahl der Elemente nicht feststeht und diese in undefinierter Reihenfolge enthalten sind, ist es kein echtes Feld. Am häufigsten werden „assoziative Felder“ als Hashtabelle umgesetzt.

Implementierung

Hier folgen Tipps zur Implementierung:

Zeiger und Felder

Naheliegend wäre, dass die einzelnen Feldelemente direkt hintereinander im Speicher abgelegt sind. Das ist zumindest bei „hardwarenahen“ Programmiersprachen tatsächlich der Fall. Man sieht (vor allem in C) oft Konstrukte, bei denen mit Zeigern auf Felder zugegriffen wird. Ein kleines Beispiel in C soll diese Thematik verständlich erläutern:

#include <stdio.h>
#include <stdlib.h>
 
int main(int argc, char *argv[]) {
    /* Ein Feld mit der Länge 5 vom Typ Integer (Ganzzahl) anlegen */
    int iArray[5];
    /* Eine Zeigervariable, die auf einen Integer-Wert im Speicher zeigen kann */
    int *zeiger;
    /* Eine Integer-Variable als Zähler für die Zählschleife */
    int i;
 
    /* Feld mit Beispieldaten (Ganze Zahlen von 10 bis 14) füllen */
    for(i=10; i<15; i++)
       iArray[i-10] = i;
 
    /* Adresse des Zeigers auf Adresse des 4. Feldelementes setzen */
    /* (Index 3 entspricht 4. Position, da bei 0 zu zählen begonnen wird) */
    zeiger = &(iArray[3]);
 
    /* Ausgabe der Speicherzelle, die um „1 Einheit“ */
    /* (= Länge einer Integervariable) nach der Adresse des Zeigers steht */
    printf("%d\n", *(zeiger+1));
 
    /* Andere Ausgaben */
    printf("%d\n", *zeiger);
    printf("%d\n", *(zeiger-1));
    return 0;
}

Dieses Programm gibt folgendes aus:

  14
  13
  12

Siehe auch

• Liste (Datenstruktur)
• Baum (Graphentheorie)
• Vektorprozessor