Loading AI tools
Datenstruktur in der Informatik Aus Wikipedia, der freien Enzyklopädie
Ein Array ([englisch für Areal, Bereich, Anordnung, Aufstellung u. a.) ist in der Informatik eine Datenstruktur-Variante, mit deren Verwendung „viele gleichartig strukturierte Daten […] verarbeitet werden sollen“.[1] Der Zugriff auf bestimmte Inhalte des Arrays erfolgt mit Hilfe von Indizes.
],Zum Teil wird für Arrays auch der Ausdruck Feld (aus englisch ‚field‘, eine weitere mögliche Bedeutung von ‚Array‘) verwendet. Dieser Ausdruck (wie auch Datenfeld) gilt jedoch im Allgemeinen als elementares, Daten beschreibendes Konstrukt; es wird im Quelltext eines Computerprogramms zur Definition von oder Bezugnahme auf benannten Speicherplatz verwendet.
Ein Feld in diesem Sinn ist kein Datentyp, sondern es hat einen Datentyp, und es ist unerheblich, ob es Teil eines Arrays oder einer übergeordneten Datenstruktur, z. B. Verbund oder Record ist oder ein singulär definierter Speicherbereich.
Die beiden sich wesentlich unterscheidenden Bedeutungen von ‚Feld‘ sind und waren immer wieder Anlass zu zum Teil heftigen Diskussionen.[2]
„Der englische und gängigere Begriff ist Array“.[3]
Gleichbedeutende Synonyme für Array sind, im Wesentlichen geprägt aus dem Einsatz in verschiedenen Programmiersprachen, deren Terminologie und Entstehungsgeschichte oder durch Übersetzung aus dem Englischen: Tabelle (Table), Vektor, Reihe, Reihung, Aufstellung, Bereich, Gate Array, Matrix u. a.
Auch die verschiedenen Elemente eines Arrays werden mit unterschiedlichen Ausdrücken bezeichnet: Element, Komponente, Unterfeld, Feldelement, indizierte Variable – und zum Teil ebenfalls Feld oder Datenfeld.
Zur Adressierung der Inhalte eines Arrays wird ein ‚Index‘ verwendet.
Der Index wird bei ‚Standard-Arrays‘ in höheren Programmiersprachen als Ganzzahl angegeben.
‚Assoziative Arrays‘ erlauben dagegen die Verwendung von beliebigen, nicht notwendigerweise numerischen, aber eindeutigen Schlüsselwerten als Indizes.
Bei mehrdimensionalen Arrays gibt es für jede Dimension einen unabhängigen Index und eine unabhängige Länge.
Bei streng strukturierten Programmiersprachen wird die Zulässigkeit eines Indexes zur Laufzeit geprüft, damit der Zugriff auf ungültige Speicherbereiche unterbunden wird.
Grundsätzlich können Arrays in den meisten Programmiersprachen angelegt und verarbeitet werden. Neben den unterschiedlichen Ausdrücken, die sich in einzelnen Sprachen entwickelt haben, werden Arrays von den Compilern der Programmiersprachen, zum Teil auch in verschiedenen Sprachversionen, unterschiedlich umgesetzt und unterstützt. Beispiele:
In den meisten Assemblersprachen ist die Verarbeitung von Arrays zwar möglich, sie wird aber 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. Zur Verarbeitung ermittelt er die Position relevanter Elemente mit geeigneten Algorithmen, zum Beispiel in einem Indexregister, und adressiert sie mit aufgabenspezifischen – nicht speziell auf die Array-Verarbeitung ausgerichteten – Anweisungen.
Beim Deklarieren werden Arrays in einer sprachspezifischen Syntax formuliert. Beispiele:
NameX (100)
(Datenname plus Anzahl der Array-Elemente in runder Klammer): PL/INameX [100,...]
(Datenname plus je Dimension die Anzahl der Array-Elemente in einer eckigen Klammer): C#[4]NameX [100][][]
(Datenname plus je Dimension in eckigen Klammern die Anzahl der Array-Elemente): C/C++,[5] Java[6]NameX array (100)
(Schlüsselwort 'array' plus Anzahl der Elemente in runder Klammer): Modula-2NameX occurs 100.
(Schlüsselwort 'OCCURS' plus Anzahl der Elemente plus ggf. Klausel ‚Indexed by‘): CobolDim NameX (100,...)
(Schlüsselwort 'Dim' plus Variablenname plus Anzahl Elemente je Dimension (in einer runden Klammer)): VBA, 'Dimension' bei Fortran90/95Mit Hilfe eines Arrays 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-Array ist im Gegensatz zum assoziativen Array auf ganzzahlige Indizes zur Adressierung festgelegt. Ein Index beginnt, bei einem (eindimensionalen) Array 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).
Ein dynamisches Array oder eine Array-Liste, eine Listendatenstruktur mit variabler Größe und wahlfreiem Zugriff, wo Elemente hinzugefügt oder entfernt werden können. Es wird von Standardbibliotheken vieler moderner Programmiersprachen zur Verfügung gestellt.
Ein dynamisches Array ist nicht dasselbe wie ein dynamisch zugewiesenes Array, bei dem es sich um ein Array handelt, dessen Größe bei der Zuweisung des Arrays festgelegt wird, obwohl ein dynamisches Array ein solches Array mit fester Größe möglicherweise als Back-End verwendet.
Ein einfaches dynamisches Array kann durch Zuweisen eines Arrays mit fester Größe erstellt werden, das normalerweise größer ist als die Anzahl der unmittelbar erforderlichen Elemente. Die Elemente des dynamischen Arrays werden am Anfang des zugrunde liegenden Arrays zusammenhängend gespeichert, und die verbleibenden Positionen gegen Ende des zugrunde liegenden Arrays werden reserviert oder nicht verwendet. Elemente können am Ende eines dynamischen Arrays in konstanter Laufzeit unter Verwendung des reservierten Speicherplatzes hinzugefügt werden, bis dieser Speicherplatz vollständig belegt ist.
Wenn der gesamte Speicherplatz belegt ist und ein zusätzliches Element hinzugefügt werden soll, muss das zugrunde liegende Array mit fester Größe vergrößert werden. Normalerweise ist die Größenänderung teuer, da ein neues zugrunde liegendes Array zugewiesen und jedes Element aus dem ursprünglichen Array kopiert werden muss. Elemente können in konstanter Zeit vom Ende eines dynamischen Arrays entfernt werden, da keine Größenänderung erforderlich ist. Die Anzahl der Elemente, die vom Inhalt des dynamischen Arrays verwendet werden, ist seine logische Größe, während die Größe des zugrunde liegenden Arrays als Kapazität oder physische Größe des dynamischen Arrays bezeichnet wird. Dies ist die maximale mögliche Größe, die verwendet werden kann, ohne Daten zu verschieben.
Ein dynamisches Array wird benötigt, wenn die maximale logische Größe nicht festgelegt ist oder nicht berechnet werden kann, bevor der Speicherplatz für das Array reserviert wird.
Eine Sonderform bildet das „assoziative Array“, auch „Zuordnungstabelle“ genannt. Es verwendet keine notwendigerweise ganzzahligen numerischen Indizes, sondern Schlüssel zur Adressierung der Elemente. Diese Schlüssel können prinzipiell beliebigen Typs sein, zum Beispiel Zeichenketten, müssen aber ein Element eindeutig identifizieren. Beispiel: Die Produktnummer ist der Index, mit dem Daten zu einem bestimmten Produkt in einer Produkttabelle indiziert werden, z. B.: Produkt = ProdBezeichn (ProdNr)
.
„Assoziativ“ werden solche Arrays nur genannt, wenn der die tatsächliche Datenadresse berechnende Suchalgorithmus von der Programmiersprache automatisch generiert wird. Am häufigsten werden assoziative Felder als Hashtabelle umgesetzt.
In statisch typisierenden Programmiersprachen sind Array-Inhalte teilweise 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.
In den meisten Programmiersprachen kann ein Array – und damit die darin gespeicherten Daten – nicht nur ein-, sondern mehrdimensional sein. Bei mehrdimensionalen Feldern wird zur Adressierung ihrer Elemente für jede Dimension ein eigener Index verwendet. Zum Begriff der Dimension können die nachfolgenden Varianten unterschieden werden. In den Beispielen wird ein symbolischer Beispielcode verwendet, der Startindex sei 1.
Die Feldelemente werden wie in einer Liste als elementares Datenfeld oder als Verbund mit mehreren untergeordneten Elementarfeldern geführt. Der Zugriff auf die Informationen erfolgt über 'ArrayName (Index)'.
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(Index).ProdNr, Produkt(Index).Einkaufspreis
liefern die genannten Werte für das Produkt, auf das der Index zeigt.Mit dieser Variante lassen sich Informationen wie Elemente einer zweidimensionalen Fläche oder eines dreidimensionalen Würfels vorstellen. Dabei „beinhaltet nur die letzte Dimension die Elemente,“[7] jede Einzelinformation ist somit allen Dimensionen, z. B. Breite, Höhe, Tiefe, gleichermaßen zuzurechnen. Der Zugriff erfolgt unter Angabe aller Indizes ('<AttrName>(i1,i2,...)'). ISO_IEC 11404 nennt diese Arrays unter den ‚General Purpose Datatypes‘ „inhärent mehrdimensional“. Diese mehrdimensionalen Arrays werden, vor allem im Bereich des Deep Learning, nach ihrer mathematischen Entsprechung auch als Tensoren bezeichnet.[8]
1. zweidimensional (wie eine Matrix oder eine Tabelle):
Schachbrett := array(8,8) of String
array
deklariert Schachbrett
als Array („Feld“) mit 8 mal 8 Einträgen, of
deklariert den Typ des Eintrags, hier String
.Schachbrett := ((„w_Turm“ ,"w_Springer","w_Läufer","w_König","w_Dame" ,"w_Läufer","w_Springer","w_Turm" ), („w_Bauer“,"w_Bauer" ,"w_Bauer" ,"w_Bauer","w_Bauer","w_Bauer" ,"w_Bauer" ,"w_Bauer"), ("" ,"" ,"" ,"" ,"" ,"" ,"" ,"" ), ("" ,"" ,"" ,"" ,"" ,"" ,"" ,"" ), ("" ,"" ,"" ,"" ,"" ,"" ,"" ,"" ), ("" ,"" ,"" ,"" ,"" ,"" ,"" ,"" ), („s_Bauer“,"s_Bauer" ,"s_Bauer" ,"s_Bauer","s_Bauer","s_Bauer" ,"s_Bauer" ,"s_Bauer"), („s_Turm“ ,"s_Springer","s_Läufer","s_König","s_Dame" ,"s_Läufer","s_Springer","s_Turm" ))
w_
=weiß, s_
=schwarz. D. h. oben sitzt der Spieler der weißen Figuren und unten der der schwarzen.Schachbrett[Zeilenindex,Spaltenindex]
. Der Spaltenindex „läuft schneller“.Schachbrett[z,s]
dem Feld („a“–„h“)[9-s
]z
.Schachbrett[5,4]*1 := Schachbrett[5,2]*2
und Schachbrett[5,2]*1 := ""
liefern den Eröffnungszug „d2–d4
“.2. mehrdimensional (hier mit 4 Dimensionen):
temperatur := array(50,50,50,1000) of float
= temperatur( 7 , 12 , 48 , 617 )
Hierbei enthält ein Array als Element – neben meist anderen Datenfeldern – wiederum ein Array usw. mit gegebenenfalls weiteren Stufen. Diese Variante wird auch verzweigtes Array genannt.[9][10] Im Array gespeicherte Informationen gehören dabei jeweils zu genau einer Dimension, und zu genau einer ihrer Indexausprägungen. Die Anzahl der Dimensionen ergibt sich aus der „Schachtelungstiefe“ des innersten Arrays. ISO_IEC 11404 nennt diese Arrays „induziert mehrdimensional“. Zugriffe auf Informationen im äußeren Array erfolgen zum Beispiel mit '<Attr_in_Dim1>(i)', auf Informationen im inneren Array (z. B. bei dreidimensional) mit '<Attr_in_Dim3>(i1,i2,i3)'.
Regal: // umfasst das ganze Regal Regalboden := array(10) // Es gibt 10 Regalböden = Array der 1. Dimension RB_Bezei := Text(20) // wie der jeweilige Regalboden genannt/beschriftet wird … // ggf. weitere Daten je Regalboden, z. B. max. Gesamtgewicht WZ_Box := array(5) // Je Regalboden max. 5 Werkzeugboxen, 2. Dimension WZ_Bezei := Text(20) // Bezeichnung der Werkzeuge, die in der Box gelagert bzw. zu lagern sind WZ_Anz := numeric(4) // die Anzahl der darin gelagerten Werkzeuge … // ggf. weitere Daten je WZ-Box, u. U. weiteres Array 3. Dim.
'RB_Bezei (I1), "Box-Nr:" & I2, WZ_Bezei [I1,I2], WZ_Anz [I1,I2] ...'
// liefert die Werkzeug-Bezeichnung und ihre Anzahl, die in einer bestimmten Box // (Regalboden und Box-Nr) gelagert sind.
'RB_Bezei (I1)'
// liefert die Bezeichnung des Regalbodens.'WZ_Bezei (I1,I2) = "Rohrzangen", WZ_Anz (I1, I2) = 10'
legt eine neue WZ-Box mit 10 Rohrzangen an.'WZ_Anz (I1,I2) -1
aktualisiert die Anzahl bei Entnahme eines Werkzeugs aus der Box.In den Anweisungen sind Indizes für die inneren Dimension(en) (> 1) nur anzugeben, wenn aus ihnen Informationen angesprochen/abgerufen werden, z. B. RB_Bezei(x) oder WZ_Bezei(x,y).
Sollte das Lager aus mehreren (z. B. 4) Regalen bestehen, müsste vor 'Regalboden' eine weitere Dimension 'Regal := array (4)' – optional mit ‚eigenen‘ Info-Elementen (wie etwa Breite) – definiert und bei Zugriffen der Index für diese neue Dimension 1 zusätzlich spezifiziert werden.
Die Speicheradresse eines durch einen Index bezeichneten Inhalts wird, ausgehend von der für das erste Element festgelegten Speicheradresse plus indexabhängige Distanz (berechnet über den aktuellen Index-Inhalt minus Index-Erstwert, multipliziert mit der Länge des Inhalts der Array-Datengruppe) gebildet.
Trotz der meist räumlich dargestellten Inhalte von Arrays, besonders bei mehrdimensionalen, werden auch die in einem Array 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 Array werden entsprechend viele Matrizen hintereinander abgelegt usw.
Bei den meisten Programmiersprachen wird das Adressieren von Arrays vollständig vom Compiler behandelt. In Assembler muss es im Quellcode explizit programmiert werden.
Ein Programm, das auf Elemente eines Arrays zugreifen will, muss deren Speicheradresse errechnen.
Beispiel
Gegeben: Ein 2-dimensionales Array mit 4 Zeilen (1..4) und 7 Spalten (1..7). Jedes Element sei 4 Byte groß. Es soll zugegriffen werden auf das Element an (Zeile = 3, Spalte = 6). Das Array beginne bei Speicheradresse base.
Da auf ein Element der Zeile 3 zugegriffen wird, müssen 2 Zeilen „übersprungen“ werden:
In der Zeile 3 soll auf Spalte 6 zugegriffen werden, also sind zusätzlich 5 Elemente zu „überspringen“:
Das gewünschte Element beginnt also an Adresse (base + 56 + 20) = (base + 76) und ist 4 Byte lang.
Allgemein
In einem -dimensionalen Array wird die Adresse eines Elements beispielsweise mit Hilfe der Formel berechnet. Man nennt diese Formel auch Speicherabbildungsfunktion.
Die dargestellte Formel ist nur eine von mindestens zwei Alternativen, je nachdem, in welcher Reihenfolge die Indizes 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 und im jeweiligen Befehl zu verwenden, egal nach welcher Variante.
Da die Produkte in obiger Formel konstant sind, können sie einmalig berechnet werden. Der daraus resultierende Dope-Vektor d ermöglicht anschließend über die Formel eine sehr schnelle Berechnung der Adresse eines jeden gespeicherten Elements.
Die Verarbeitung von Daten innerhalb eines Arrays erfordert – im Gegensatz zu ohne Index adressierbaren Datenfeldern – zusätzlichen Aufwand zur Berechnung der tatsächlichen Speicheradresse verwendeter Datenfelder. Die dazu nötigen, meist von einem Compiler erzeugten Berechnungsbefehle kann der Programmierer zum Teil beeinflussen und optimieren – sofern dies nicht bereits durch den Compiler geschieht. Die folgenden Beispiele nennen Details, deren Anwendung zu effizienterem Code führen kann, Details und weitere Beispiele siehe.[11]
Dim(101)
definieren, Vor der Verarbeitung Inhalt(index) dorthin übertragen und in Einzelbefehlen Elemente mit Index-Direktwert ‚101‘
adressieren: Dabei ist die Adressberechnung nur einmal erforderlich.Die Zweckmäßigkeit oder Notwendigkeit derartiger Effizienzmaßnahmen, die aus Gründen der Lesbarkeit eines Programms stets gut dokumentiert sein sollten, hängt von verschiedenen Faktoren ab: Nicht relevant sind sie, wenn der verwendete Compiler entsprechende Optimierungen automatisch vornimmt, weniger relevant zum Beispiel, wenn das Programm nur selten ausgeführt wird, wenn es jeweils nur eine kurze Laufzeit hat, wenn die Array-bezogenen Befehle nur einen geringen Teil der Gesamtverarbeitung ausmachen.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.