Feld (Datentyp)

Ein Feld (englisch Array [əˈɹeɪ] (Betonung auf 2. Silbe) für ‚Anordnung‘, ‚Aufstellung‘ usw.) ist in der Informatik eine Datenstruktur-Variante, mit deren Verwendung „viele gleichartig strukturierte Daten [...] verarbeitet werden sollen“. Dabei wird zwischen einem ‚Standard-Feld‘ und dem ‚assoziativen Array‘ unterschieden.

Begriffe

Synonyme

Im Sprachgebrauch und im Wesentlichen geprägt aus dem Einsatz in verschiedenen Programmiersprachen (ihrer Terminologie und Entstehungsgeschichte) und durch Übersetzung aus dem Englischen, wird der hier – mit der Bedeutung ‚Array‘ – beschriebene Begriff ‚Feld‘ mit unterschiedlichen Ausdrücken belegt: Array, Tabelle, Vektor, Reihe, Reihung, Datenfeld, Aufstellung, Bereich, Gate Array, Matrix/Matrize, indizierte Variable usw. „Der englische und gängigere Begriff für Feld ist Array.“

Auch die einzelnen Elemente eines Arrays werden mit unterschiedlichen Ausdrücken bezeichnet: Element, Komponente, Unterfeld, Feldelement - zum Teil ebenfalls Feld.

Kontextbezogene Unterschiede

Der Ausdruck 'Feld' hat unterschiedliche Bedeutungen

In der Bedeutung ‚Array‘ bezeichnet man mit ‚Feld‘ je nach Kontext im Detail unterschiedliche Gegebenheiten:

• Wenn ‚Feld‘ als Synonym für ‚Array‘ benutzt wird: Das gesamte Array mit allen seinen Elementen, ggf. auch mehrdimensional - mit allen Indexausprägungen.
• Bei Bezug auf ein definiertes Feld, oft nur in Deklarationen: Die Gesamtheit aller Index-Ausprägungen des Feldes (eine ganze Spalte).
• Mit '<Name> (Index)' bezieht man sich auf eine einzelne Index-Ausprägung, alternativ ein elementares Feld oder eine ganze Zeile.

Ebenfalls kontextabhängig betrifft die Bezugnahme auf ‚Feld‘ alternativ die Deklarationsebene des Arrays (Bsp.: dim Feld (100)) oder gespeicherte Inhalte (Bsp.: ADD Feldelement (Index) to Summe).

Abweichende Bedeutung

Der Ausdruck ‚Feld‘ wird auch als ‚Daten beschreibendes Konstrukt‘ im Allgemeinen verstanden, das im Quelltext eines Computerprogramms zur Definition von Speicherplatz verwendet wird. In diesem Sinn ist ein Feld kein Datentyp, sondern es hat einen Datentyp, und es ist unabhängig davon, ob es einem Array oder einer übergeordneten Datenstruktur (wie Verbund oder Record) angehört oder nicht. ‚Feld‘ in diesem Sinn wird damit i. W. mit Variable oder Datenfeld gleichgesetzt. Literaturbeispiele:

• Ausdrücke wie statisches Feld, Klassenfeld, Feldlänge usw. beziehen sich auf ‚Feld‘ in einem allgemeinen Sinn.
• ‚Feld‘ wird (z. B. in) als typneutrales Datenkonstrukt verwendet.
• Gleiches gilt für Texte wie „... Inhalt des Feldes Auftragskennung“ (im Link zu siko.de) und „...behandelt jedes Array Element wie ein eigenes Feld“ in oder Ausdrücke wie „Felder für den Datenaustausch“, „... überträgt Daten zu einem Feld“, „Inhalt des Datenfelds“, „Feldbeschreibung“, „Feldlänge“ in
• Sogar in Unterlagen, die ‚Feld‘ grundsätzlich i. S. von ‚Array‘ benutzen, wird der Ausdruck ‚Feld‘ auch nicht-arraybezogen verwendet: „Hier hat das Array 10 Felder“ oder „alle anderen Felder besitzen einen undefinierten Wert“ in

Diese beiden sich wesentlich unterscheidenden Bedeutungen von ‚Feld‘ sind und waren immer wieder Anlass zu zum Teil heftigen Diskussionen, Beispiel siehe

Sprachspezifische Unterschiede

Grundsätzlich können Arrays in allen(*) Programmiersprachen angelegt und verarbeitet werden. Neben den unterschiedlichen Begriffen, die sich in einzelnen Sprachen entwickelt haben (meist nach der Übersetzung aus dem Englischen), werden Arrays von den Sprachen (Compilern) sowohl beim Deklarieren als auch bei der Verwendung in Befehlen unterschiedlich umgesetzt/unterstützt. Beispiele:

• Einschränkungen bezüglich möglicher Datenformate und -Längen im Array
• Unterscheidung Standardfeld / assoziatives Array durch die Programmiersprache (den Compiler) - J/N
• Anzahl der möglichen Dimensionen; Array-Größe
• Adressierung der Elemente (ab 0, ab 1, ab <beliebig> beginnend)
• Unterstützung des Compilers für Operationen auf Datenmengen im Array: auf Elemente, das ganze Array, Teilbereiche daraus.
• Adressierungsverfahren: Schlüsselsuche, verschiedene Methoden zur Indexermittlung
• Dynamische oder fixe Größe von Arrays

(*) In den meisten Assemblersprachen ist die Verarbeitung von Arrays zwar möglich, sie wird aber sprachlich-syntaktisch meist nicht speziell unterstützt. Der Programmierer implementiert Array-Elemente so wie auch andere Variablen, reserviert zusätzlich den Speicherplatz für n weitere Ausprägungen, ermittelt die Position (den Index) relevanter Elemente mit geeigneten Algorithmen und adressiert diese mit – nicht speziell auf die Array-Verarbeitung ausgerichteten – geeigneten Anweisungen.

Standard-Feld

Mit Hilfe eines Feldes können die Daten eines üblicherweise einheitlichen Datentyps 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. Dieser beginnt, bei einem Feld mit N Elementen, standardmäßig je nach Programmiersprache bei 0 (C++: 0,1,2,…,N-1) oder 1 (Fortran: 1,2,3,...,N), kann jedoch oftmals auch frei gewählt werden (42,43,44,…,N+41).

Beispiele

Im Folgenden wird ein symbolischer Beispielcode verwendet (der Startindex sei 1):

• Vektor (eindimensional)

Vektor := (10, -11, 12)

So liefert Vektor[2] den Wert -11.

• Matrix oder Tabelle (zweidimensional)

In einer Matrix werden die waagerechten 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 := 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 Beispielanweisungen Schachfeld[3,3] := Schachfeld[1,2] und Schachfeld[1,2] := „Leer“ liefern den Eröffnungszug „Weißer Springer auf C3“.

Ein Praxisbeispiel für Anrede-Bezeichnungen

Ein Array enthält die Daten 'Herr, Frau, Firma, usw.' in der Reihenfolge 1,2,3 bis n. In den Adressdaten des Kundenbestands ist nur die Anredenummer (zwischen 1 und n) gespeichert. Beim Erstellen von Briefen etc. wird diese Anrede-Nummer als Index benutzt und der Text, also der Wert 'Frau' für '2', aus dem Array als Anrede-Volltext eingesetzt.

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_{1},j_{2},..,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 ein solches 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 dies in der innersten Schleife ebenso 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.

Feld in freierer Form

In manchen Programmiersprachen – als Beispiel kann Java dienen – sind Feldinhalte nicht auf Elemente eines einzelnen Datentyps eingeschränkt, es können Objekte oder allgemeine Datenstrukturen fast beliebiger Zusammensetzung und Reihenfolge gespeichert werden. In Java muss auch nicht jede Zeile eines zweidimensionalen Arrays gleich lang sein. Die obigen Adressrechnungen muss die Laufzeitumgebung der jeweiligen Programmiersprache dann entsprechend anders und ggf. aufwändiger gestalten.

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. Am häufigsten werden „assoziative Felder“ als Hashtabelle umgesetzt.

Ein Praxisbeispiel aus der Rechnungsschreibung

Eine IT-Anwendung erstellt Kundenrechnungen. Je Produkt sollen auch die insgesamt in Rechnung gestellte Anzahl und der Gesamtbetrag gezählt werden. Die Anwendung liest die Angaben 'Produktnummer, Produktbezeichnung und Preis' aus einer Datenbank in ein assoziatives Array im Hauptspeicher ein, um nicht bei jeder Rechnungsposition auf das externe Speichermedium zugreifen zu müssen. Schlüssel im Array ist die Produktnummer, alle Einträge sind danach sortiert. Zu der in jeder Rechnungsposition enthaltenen Produktnummer wird die jeweilige Array-Position ermittelt und die Bezeichnung und der Preis in der Rechnungszeile eingesetzt. Die Produktanzahl je Position und der daraus gebildete Preis wird in den zusätzlich angelegten Array-Elementen 'Gesamtanzahl' und 'Gesamtpreis' (je Produktnummer) kumuliert - um am Programmende als Summeninformation ausgegeben zu werden.

Siehe auch

• Liste (Datenstruktur)
• Baum (Graphentheorie)
• Range Minimum Query
• Vektorprozessor
• Zuweisungskompatibilität

Weblinks

Wiktionary: Array – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

 Commons: Array-Datenstruktur – Sammlung von Bildern, Videos und Audiodateien

 Wikibooks: Algorithmen und Datenstrukturen in C/ Felder – Lern- und Lehrmaterialien

• Das Array, unendliche Weiten? – Dimensionen von Arrays auf www.aspheute.com