Feld (Datentyp)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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“.[1] Dabei wird zwischen einem ‚Standard-Feld‘ und dem ‚assoziativen Array‘ unterschieden.

Begriffe[Bearbeiten]

Synonyme[Bearbeiten]

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“.[2]

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

Kontextbezogene Unterschiede[Bearbeiten]

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[Bearbeiten]

Der Ausdruck ‚Feld‘ wird auch als elementares, 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 unerheblich, 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[3]) 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[4] oder Ausdrücke wie „Felder für den Datenaustausch“, „… überträgt Daten zu einem Feld“, „Inhalt des Datenfelds“, „Feldbeschreibung“, „Feldlänge“ in[5]
  • 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[6]

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

Sprachspezifische Unterschiede[Bearbeiten]

Grundsätzlich können Arrays in den meisten(*) 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) unterschiedlich umgesetzt/unterstützt. Beispiele:

  • Unterscheidung Standardfeld / assoziatives Array / nur Listen durch die Programmiersprache (den Compiler)
  • Anzahl der möglichen Dimensionen; mehrdimensional / Array-im-Array
  • Maximale Array-Größe
  • Adressierung der Elemente (ab 0, ab 1, ab <beliebig> beginnend)
  • Im Array mögliche Datenformate und -Längen
  • Anzahl der Unterfelder: fix, dynamisch/variabel je Dimension
  • Format der Unterfelder: einheitlich für alle Indexwerte, unterschiedlich
  • Unterstützung für Operationen auf Datenmengen im Array: auf Elemente, beliebige Strukturen, ganze Dimension, ganzes Array
  • Adressierungsverfahren: Schlüsselsuche, verschiedene Methoden zur Indexermittlung

(*) In den meisten Assemblersprachen ist die Verarbeitung von Arrays zwar möglich, sie wird aber sprachlich-syntaktisch meist nicht speziell unterstützt und muss vom Programmierer explizit „nachgebaut“ werden. 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.

Sowohl beim Deklarieren als auch bei der Verwendung in Befehlen werden Array-bezogene Anweisungen in einer sprachspezifischen Syntax formuliert.

Element-Datentyp[Bearbeiten]

In statisch typisierenden Programmiersprachen sind Feldinhalte meist auf Elemente eines einzelnen Datentyps eingeschränkt; mitunter ist jedoch ein Spezialfall „(weitgehend) beliebiger Inhalt“ möglich, bei objektorientierten Programmiersprachen oft über Polymorphie der allgemeinen Basisklasse. In dynamisch typisierenden Programmiersprachen können meist Objekte oder allgemeine Datenstrukturen in fast beliebiger Zusammensetzung und Reihenfolge gespeichert werden; in dynamisch typisierenden Programmiersprachen werden jedoch oft nur assoziative Arrays angeboten.

Standard-Feld[Bearbeiten]

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 Indizes möglich wird. Das (Standard-)Feld ist im Gegensatz zum assoziativen Feld auf ganzzahlige Indizes zur Adressierung festgelegt. Ein Index beginnt, bei einem (eindimensionalen) 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).

Assoziatives Feld[Bearbeiten]

Hauptartikel: Assoziatives Array

Eine Sonderform bildet das „assoziative Array“. Es verwendet keinen numerischen Index, sondern sogenannte Schlüssel zur Indizierung und damit zur Adressierung der Elemente. Beispiel: Die Produktnummer ist der Index, mit dem Daten zu einem bestimmten Produkt in einer Produkttabelle indiziert werden. Am häufigsten werden „assoziative Felder“ als Hashtabelle umgesetzt.

Bei assoziativen Arrays muss – als zusätzlicher Teil der Adressrechnung (s. u.) – die Position der Daten anhand des/der als Schlüssel festgelegten Datenfeldes/r ermittelt werden.

Dimensionen [Bearbeiten]

In den meisten Programmiersprachen kann ein Feld (und damit die darin gespeicherten Informationen) mehrdimensional sein. Zum Begriff der Dimension können die nachfolgenden Varianten unterschieden werden. In den Beispielen wird ein symbolischer Beispielcode verwendet, der Startindex sei 1.

Eindimensionale Felder[Bearbeiten]

Feldelemente werden wie in einer Liste als elementares Datenfeld oder als Verbund mit mehreren Elementarfeldern geführt. Zugriff auf die Informationen erfolgt über '<AttrName>(index)'.

Beispiele

1.   eindimensional (wie eine ‚Liste‘)

 Vektor := array(3) of float  // Deklaration einer 1-dimensionalen Liste namens „Vektor“ mit 3 ‚freien Plätzen‘
 Vektor := (0.5, 1.7, -0.2)   // der Punkt (x=0.5 ; y=1.7 ; z=-0.2) im ℝ³
Vektor[2] liefert so die y-Komponente mit dem Wert 1.7.

2.  eindimensional (mit Verbund-Datentyp):

 Produkt := array(100) of structure{       
    ProdNr        := Text[6] ,             // Text mit max. 6 Stellen 
    Einkaufspreis := FixPunktZahl[4;2]     // Kommazahl mit 4 Stellen vor, 2 Stellen nach dem Komma
    Verkaufspreis := FixPunktZahl[4;2]     // dito
    Lagerbestand  := Integer[6]            // Ganzzahl mit 6 Stellen
 } // end structure
Produkt.ProdNr[Index], Produkt.Einkaufspreis[Index] liefern die genannten Werte für das Produkt, auf das der Index zeigt.

Mehrdimensional / direkt im Feld[Bearbeiten]

Mit dieser Variante lassen sich Informationen wie Elemente einer Fläche (2D) oder eines Würfels (3D) vorstellen. Dabei „beinhaltet nur die letzte Dimension die Elemente ,“[8] jede Einzelinformation ist somit allen Dimensionen (z. B. Breite, Höhe, Tiefe) gleichermaßen zuzurechnen. Der Zugriff erfolgt unter Angabe aller Indices ('<AttrName>(i1,i2,...)').

Beispiele

1.   zweidimensional (wie eine Matrix oder eine Tabelle):

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 deklariert die 8 mal 8 Felder von Schachfeld, of den Typ des Eintrags;
hier: (Zeile,Spalte)
 Schachfeld := (("Turm_W" ,"Springer_W","Läufer_W", … ,"Turm_W"),
                ("Bauer_W","Bauer_W"   ,"Bauer_W" , … ,"Bauer_W"),
                (""       ,""          ,""        , … ,""),
                (""       ,""          ,""        , … ,""),
                (""       ,""          ,""        , … ,""),
                (""       ,""          ,""        , … ,""),
                ("Bauer_S","Bauer_S"   ,"Bauer_S" , … ,"Bauer_S"),
                ("Turm_S" ,"Springer_S","Läufer_S", … ,"Turm_S"))
Die vorstehende Zuweisung legt die Start-Anordnung der Figuren fest, W=weiß, S=schwarz.
Die Beispielanweisungen Schachfeld[3,3]*1 := Schachfeld[1,2]*2 und Schachfeld[1,2]*2 := "" liefern den Eröffnungszug „Weißer Springer auf C3“.
*1: oder [NachZeile,NachSpalte] *2: oder [VonZeile,VonSpalte], Indices jeweils vorher mit Werten belegt

2.   mehrdimensional (hier mit 4 Dimensionen):

Für einen Brennraum (x;y;z) (z. B. eines Motors),
wobei x, y und z in Millimeter jeweils von 1 bis 50 angegeben seien,
sei an jeder Stelle, und über den Zeitraum einer Sekunde für jede Millisekunde, eine Temperaturangabe gespeichert:
 temperatur := array(50,50,50,1000) of float
→ 4-dimensionales Array (x,y,z,zeit)
Wie heiß war es an der Stelle (x=7;y=12;z=48) zum Zeitpunkt t=617 ms?
 = temperatur( 7 , 12 , 48 , 617 )

Mehrdimensional / Feld enthält weiteres Feld[Bearbeiten]

Hierbei enthält ein Feld als Element - neben meist anderen Datenfeldern - wiederum ein Feld, usw. mit ggf. weiteren Stufen. Diese Variante wird auch „verzweigtes Array“ genannt [9], [10]. Im Feld gespeicherte Informationen gehören dabei jeweils zu genau einer Dimension, d. h. zu genau einer ihrer Indexausprägungen. Dementsprechend erfolgt der Zugriff auf Informationen im äußeren Feld zum Beispiel mit '<Attr_in_Dim1>(i)' und auf Informationen im inneren Feld mit '<Attr_in_Dim2>(i,j) usw. „Mehrdimensional“ bezieht sich hier auf die Gesamtheit aller im Feld hierarchisch (= baumartig = ‚verzweigt‘) gespeicherten Informationen, nicht auf jedes einzelne Element. Die Anzahl der Dimensionen ergibt sich aus der „Schachtelungstiefe“ des innersten Arrays.

Beispiel
 Lager      := array(10)                   // Es gibt 10 Lager = Feld der 1. Dimension
  LagerNr   := Text(4)                     //  darin: jedes wird mit seiner Nummer geführt
  Produkt   := array(100)                  //  ... und in jedem Lager (max.) 100 Produkte, = Feld der 2. Dimension
   ProdNr   := Text[6]                     // Je Produkt dessen Nummer mit max. 6 Stellen 
   EK_Preis := FixPunktZahl[4;2]           //  ... und dessen Einkaufspreis
'LagerNr (Index1), ProdNr[Index1,Index2], EK_Preis[Index1,Index2] ...' liefert die genannten Werte für das jeweilige Produkt aus dem jeweiligen Lager gemäß dem Inhalt der Indices.
'LagerNr (Index1)' liefert die Lagernummer, jeweils gemäß Index1
Für den Zugriff sind nur die Indices für die Dimension(en) erforderlich, zu denen die Informationen gehören.

Adressierung eines Feldes[Bearbeiten]

Trotz der meist räumlich dargestellten Inhalte von Feldern, besonders bei mehrdimensionalen, werden auch die in einem Feld gespeicherten Elemente in einem linearen Speicher abgelegt. 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[Bearbeiten]

Ein Programm, das auf das Feld 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, diese Berechnungen vorzunehmen, egal nach welcher Variante..

Dope-Vektor[Bearbeiten]

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[Bearbeiten]

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.

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

 Wiktionary: Array – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
 Commons: Array-Datenstruktur – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise[Bearbeiten]

  1. Programmieren in Fortran, Uni Bayreuth
  2. Ein C-Tutotial C-how-to
  3. Microsoft msdn visual studio
  4. linguee
  5. Die allgemeine Cobol-Programmstruktur (PDF; 308 kB)
  6. rrzn Uni Hannover (PDF; 411 kB)
  7. LEO
  8. Programmersbase [1]
  9. Rheinwerk-Verlag [2]
  10. MSDN [3]