Datenstruktur des Arrays - Array data structure

In der Informatik ist eine Array-Datenstruktur oder einfach ein Array eine Datenstruktur, die aus einer Sammlung von Elementen ( Werten oder Variablen ) besteht, die jeweils durch mindestens einen Array-Index oder -Schlüssel identifiziert werden . Ein Array wird so gespeichert, dass die Position jedes Elements aus seinem Indextupel durch eine mathematische Formel berechnet werden kann. Die einfachste Art der Datenstruktur ist ein lineares Array, auch eindimensionales Array genannt.

Zum Beispiel kann ein Array von 10 32-Bit (4-Byte) Integer-Variablen mit den Indizes 0 bis 9 als 10 Wörter an den Speicheradressen 2000, 2004, 2008, ..., 2036 (in hexadezimal : 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4), sodass das Element mit dem Index i die Adresse 2000 + ( i × 4) hat.

Die Speicheradresse des ersten Elements eines Arrays wird als erste Adresse, Foundation-Adresse oder Basisadresse bezeichnet.

Da das mathematische Konzept einer Matrix als zweidimensionales Gitter dargestellt werden kann, werden zweidimensionale Arrays manchmal auch als Matrizen bezeichnet. In einigen Fällen wird der Begriff "Vektor" in der Berechnung verwendet, um sich auf ein Array zu beziehen, obwohl Tupel anstelle von Vektoren das mathematisch korrektere Äquivalent sind. Tabellen werden oft in Form von Arrays implementiert, insbesondere Lookup-Tabellen ; das Wort table wird manchmal als Synonym für array verwendet .

Arrays gehören zu den ältesten und wichtigsten Datenstrukturen und werden von fast jedem Programm verwendet. Sie werden auch verwendet, um viele andere Datenstrukturen wie Listen und Strings zu implementieren . Sie nutzen die Adressierungslogik von Computern effektiv aus. In den meisten modernen Computern und vielen externen Speichergeräten ist der Speicher eine eindimensionale Anordnung von Wörtern, deren Indizes ihre Adressen sind. Prozessoren , insbesondere Vektorprozessoren , werden oft für Array-Operationen optimiert.

Arrays sind vor allem deshalb nützlich, weil die Elementindizes zur Laufzeit berechnet werden können . Diese Funktion ermöglicht unter anderem, dass eine einzelne iterative Anweisung beliebig viele Elemente eines Arrays verarbeitet. Aus diesem Grund müssen die Elemente einer Array-Datenstruktur dieselbe Größe haben und dieselbe Datendarstellung verwenden. Die Menge der gültigen Indextupel und die Adressen der Elemente (und damit die Elementadressierungsformel) sind normalerweise, aber nicht immer, während der Verwendung des Arrays festgelegt.

Der Begriff Array wird oft verwendet, um Array-Datentyp zu bezeichnen , eine Art Datentyp, der von den meisten höheren Programmiersprachen bereitgestellt wird und aus einer Sammlung von Werten oder Variablen besteht, die durch einen oder mehrere zur Laufzeit berechnete Indizes ausgewählt werden können. Array-Typen werden oft durch Array-Strukturen implementiert; in einigen Sprachen können sie jedoch durch Hash-Tabellen , verknüpfte Listen , Suchbäume oder andere Datenstrukturen implementiert werden .

Der Begriff wird insbesondere in der Beschreibung von Algorithmen auch verwendet, um assoziatives Array oder "abstraktes Array" zu bezeichnen, ein theoretisches Informatikmodell (ein abstrakter Datentyp oder ADT), das die wesentlichen Eigenschaften von Arrays erfassen soll.

Geschichte

Die ersten digitalen Computer verwendeten Maschinensprachenprogrammierung, um Array-Strukturen für Datentabellen, Vektor- und Matrixberechnungen und für viele andere Zwecke einzurichten und darauf zuzugreifen. John von Neumann schrieb 1945 das erste Array-Sortierprogramm ( Mergesort ), als er den ersten speicherprogrammierbaren Computer baute . ^{P. 159} Array-Indizierung wurde ursprünglich durch selbstmodifizierenden Code und später durch Indexregister und indirekte Adressierung durchgeführt . Einige Mainframes, die in den 1960er Jahren entwickelt wurden, wie der Burroughs B5000 und seine Nachfolger, verwendeten die Speichersegmentierung , um die Überprüfung der Indexgrenzen in der Hardware durchzuführen.

Assemblersprachen haben im Allgemeinen keine spezielle Unterstützung für Arrays, außer dem, was die Maschine selbst bereitstellt. Die frühesten höheren Programmiersprachen, einschließlich FORTRAN (1957), Lisp (1958), COBOL (1960) und ALGOL 60 (1960), unterstützten mehrdimensionale Arrays, ebenso wie C (1972). In C++ (1983) existieren Klassenschablonen für mehrdimensionale Arrays, deren Dimension zur Laufzeit festgelegt ist, sowie für laufzeitflexible Arrays.

Anwendungen

Arrays werden verwendet, um mathematische Vektoren und Matrizen sowie andere Arten von rechteckigen Tabellen zu implementieren . Viele kleine und große Datenbanken bestehen aus (oder enthalten) eindimensionalen Arrays, deren Elemente Datensätze sind .

Arrays werden verwendet, um andere Datenstrukturen wie Listen, Heaps , Hash-Tabellen , Deques , Queues , Stacks , Strings und VLists zu implementieren. Array-basierte Implementierungen anderer Datenstrukturen sind häufig einfach und platzsparend ( implizite Datenstrukturen ), benötigen wenig Platz- Overhead , können jedoch im Vergleich zu baumbasierten Datenstrukturen eine geringe Platzkomplexität aufweisen, insbesondere wenn sie modifiziert werden (vergleiche ein sortiertes Array mit ein Suchbaum ).

Manchmal werden ein oder mehrere große Arrays verwendet, um die dynamische Speicherzuweisung im Programm , insbesondere die Speicherpoolzuweisung , zu emulieren . Historisch gesehen war dies manchmal die einzige Möglichkeit, "dynamischen Speicher" portabel zuzuweisen.

Arrays können als kompakte Alternative zu (ansonsten sich wiederholenden) Mehrfachanweisungen verwendet werden, um einen teilweisen oder vollständigen Kontrollfluss in Programmen zu bestimmen IF. Sie sind in diesem Zusammenhang als Kontrolltabellen bekannt und werden in Verbindung mit einem speziell entwickelten Interpreter verwendet, dessen Kontrollfluss entsprechend den im Array enthaltenen Werten geändert wird. Das Array kann enthalten Subroutine Zeiger (oder relative Unterprogrammnummern , die auf durch beaufschlagbar ist SWITCH - Anweisungen), das den Weg der Ausführung leiten.

Elementbezeichner und Adressierungsformeln

Wenn Datenobjekte in einem Array gespeichert werden, werden einzelne Objekte durch einen Index ausgewählt, der normalerweise eine nicht negative skalare ganze Zahl ist . Indizes werden auch als Indizes bezeichnet. Ein Index ordnet den Array-Wert einem gespeicherten Objekt zu.

Es gibt drei Möglichkeiten, wie die Elemente eines Arrays indiziert werden können:

0 ( nullbasierte Indizierung )

Das erste Element des Arrays wird mit einem Index von 0 indiziert.

1 ( einsbasierte Indizierung )

Das erste Element des Arrays wird mit dem Index 1 indiziert.

n ( n-basierte Indizierung )

Der Basisindex eines Arrays kann frei gewählt werden. Normalerweise erlauben Programmiersprachen, die eine n-basierte Indizierung ermöglichen, auch negative Indexwerte und andere skalare Datentypen wie Aufzählungen oder Zeichen können als Array-Index verwendet werden.

Die Verwendung von nullbasierter Indizierung ist die Designwahl vieler einflussreicher Programmiersprachen, einschließlich C , Java und Lisp . Dies führt zu einer einfacheren Implementierung, bei der sich der Index auf einen Offset von der Startposition eines Arrays bezieht, sodass das erste Element einen Offset von Null hat.

Arrays können mehrere Dimensionen haben, daher ist es nicht ungewöhnlich, mit mehreren Indizes auf ein Array zuzugreifen. Zum Beispiel könnte ein zweidimensionales Array Amit drei Zeilen und vier Spalten A[1][3]im Fall eines nullbasierten Indexsystems den Zugriff auf das Element in der 2. Zeile und 4. Spalte durch den Ausdruck ermöglichen. Somit werden zwei Indizes für ein zweidimensionales Array verwendet, drei für ein dreidimensionales Array und n für ein n- dimensionales Array.

Die Anzahl der Indizes, die zum Angeben eines Elements erforderlich sind, wird als Dimension, Dimensionalität oder Rang des Arrays bezeichnet.

In Standard-Arrays ist jeder Index auf einen bestimmten Bereich aufeinanderfolgender Ganzzahlen (oder aufeinanderfolgende Werte eines Aufzählungstyps ) beschränkt, und die Adresse eines Elements wird durch eine "lineare" Formel für die Indizes berechnet.

Eindimensionale Arrays

Ein eindimensionales Array (oder eindimensionales Array) ist eine Art von linearem Array. Der Zugriff auf seine Elemente erfordert einen einzelnen Index, der entweder einen Zeilen- oder Spaltenindex darstellen kann.

Betrachten Sie als Beispiel die C-Deklaration, int anArrayName[10];die ein eindimensionales Array von zehn ganzen Zahlen deklariert. Hier kann das Array zehn Elemente vom Typ speichern int. Dieses Array hat Indizes, die von null bis neun beginnen. Beispielsweise sind die Ausdrücke anArrayName[0]und anArrayName[9]das erste bzw. letzte Element.

Für einen Vektor mit linearer Adressierung, wobei das Element mit dem Index i unter der Adresse befindet B + C × i , wobei B eine feste ist Basisadresse und c eine feste Konstante, die manchmal das gerufene Adresse Inkrement oder Schritt .

Beginnen die gültigen Elementindizes bei 0, ist die Konstante B einfach die Adresse des ersten Elements des Arrays. Aus diesem Grund legt die Programmiersprache C fest, dass Array-Indizes immer bei 0 beginnen; und viele Programmierer werden dieses Element eher als " nulltes " als als "erstes" bezeichnen.

Der Index des ersten Elements kann jedoch durch geeignete Wahl der Basisadresse B gewählt werden . Wenn das Array beispielsweise fünf Elemente enthält, die von 1 bis 5 indiziert sind und die Basisadresse B durch B + 30 c ersetzt wird , sind die Indizes dieser Elemente 31 bis 35. Wenn die Nummerierung nicht bei 0 beginnt, die Konstante B darf nicht die Adresse eines Elements sein.

Mehrdimensionale Arrays

Für ein mehrdimensionales Array hätte das Element mit den Indizes i , j die Adresse B + c · i + d · j , wobei die Koeffizienten c und d die Zeilen- bzw. Spaltenadresseninkremente sind.

Allgemeiner gesagt , in einem k - dimensionalen Array, die Adresse eines Elements mit Indizes i ₁ , i ₂ , ..., i _k ist

B + c ₁ · i ₁ + c ₂ · i ₂ + … + c _k · i _k .

Zum Beispiel: int a[2][3];

Das bedeutet, dass Array a 2 Zeilen und 3 Spalten hat und das Array vom Integer-Typ ist. Hier können wir 6 Elemente speichern, die linear gespeichert werden, aber beginnend mit der ersten Zeile linear und dann mit der zweiten Zeile fortfahren. Das obige Array wird als a ₁₁ , a ₁₂ , a ₁₃ , a ₂₁ , a ₂₂ , a ₂₃ gespeichert .

Diese Formel erfordert nur k Multiplikationen und k Additionen für jedes Array, das in den Speicher passt. Wenn ein Koeffizient eine feste Potenz von 2 ist, kann darüber hinaus die Multiplikation durch Bitverschiebung ersetzt werden .

Die Koeffizienten c _k müssen so gewählt werden, dass jedes gültige Indextupel auf die Adresse eines bestimmten Elements abgebildet wird.

Wenn der zulässige Mindestwert für jeden Index 0 ist, ist B die Adresse des Elements, dessen Indizes alle null sind. Wie im eindimensionalen Fall können die Elementindizes durch Ändern der Basisadresse B geändert werden . Wenn also ein zweidimensionales Array Zeilen und Spalten hat, die von 1 bis 10 bzw. 1 bis 20 indiziert sind, führt das Ersetzen von B durch B + c ₁ − 3 c ₂ dazu, dass sie von 0 bis 9 und 4 bis 23 neu nummeriert werden , bzw. Diese Funktion nutzend, geben einige Sprachen (wie FORTRAN 77) an, dass Array-Indizes bei 1 beginnen, wie in der mathematischen Tradition, während andere Sprachen (wie Fortran 90, Pascal und Algol) dem Benutzer erlauben, den Mindestwert für jeden Index auszuwählen.

Dope-Vektoren

Die Adressierungsformel wird vollständig durch die Dimension d , die Basisadresse B und die Inkremente c ₁ , c ₂ , ..., c _{k definiert} . Es ist oft nützlich, diese Parameter in einen Datensatz zu packen, der als Deskriptor oder Stride-Vektor oder Dope-Vektor des Arrays bezeichnet wird . Die Größe jedes Elements und die für jeden Index zulässigen minimalen und maximalen Werte können auch in den Dotierungsvektor aufgenommen werden. Der Dope-Vektor ist ein vollständiges Handle für das Array und bietet eine bequeme Möglichkeit, Arrays als Argumente an Prozeduren zu übergeben . Viele nützliche Array-Slicing- Operationen (wie das Auswählen eines Unterarrays, das Vertauschen von Indizes oder das Umkehren der Richtung der Indizes) können sehr effizient durch Manipulieren des Dope-Vektors durchgeführt werden.

Kompakte Grundrisse

Häufig werden die Koeffizienten so gewählt, dass die Elemente einen zusammenhängenden Speicherbereich belegen. Das ist jedoch nicht notwendig. Auch wenn Arrays immer mit zusammenhängenden Elementen erstellt werden, können einige Array-Slicing-Operationen daraus nicht zusammenhängende Unter-Arrays erstellen.

Darstellung der Zeilen- und Spalten-Majorordnung

Es gibt zwei systematische kompakte Layouts für ein zweidimensionales Array. Betrachten Sie zum Beispiel die Matrix

${\displaystyle A={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.}$

Im Zeilen-Major-Order-Layout (von C für statisch deklarierte Arrays übernommen) werden die Elemente in jeder Zeile an aufeinanderfolgenden Positionen gespeichert und alle Elemente einer Zeile haben eine niedrigere Adresse als jedes der Elemente einer aufeinanderfolgenden Zeile:

1

2

3

4

5

6

7

8

9

In Spalten-Major-Reihenfolge (traditionell von Fortran verwendet) sind die Elemente in jeder Spalte im Speicher aufeinanderfolgend und alle Elemente einer Spalte haben eine niedrigere Adresse als jedes der Elemente einer aufeinanderfolgenden Spalte:

1

4

7

2

5

8

3

6

9

Bei Arrays mit drei oder mehr Indizes setzt "row major order" zwei beliebige Elemente an aufeinander folgende Positionen, deren Indextupel sich im letzten Index nur um eins unterscheiden . "Spalte Großauftrag" ist analog zum ersten Index.

In Systemen, die Prozessor-Cache oder virtuellen Speicher verwenden , ist das Scannen eines Arrays viel schneller, wenn aufeinanderfolgende Elemente an aufeinanderfolgenden Positionen im Speicher gespeichert werden, anstatt nur spärlich verstreut. Viele Algorithmen, die mehrdimensionale Arrays verwenden, scannen sie in einer vorhersehbaren Reihenfolge. Ein Programmierer (oder ein hochentwickelter Compiler) kann diese Informationen verwenden, um für jedes Array zwischen einem Zeilen- oder Spalten-Major-Layout zu wählen. Wenn Sie beispielsweise das Produkt A · B von zwei Matrizen berechnen , ist es am besten, A in Zeilen- Matrix -Reihenfolge und B in Spalten- Matrix -Reihenfolge zu speichern .

Größenänderung

Statische Arrays haben eine beim Erstellen festgelegte Größe und erlauben daher kein Einfügen oder Entfernen von Elementen. Durch Zuweisen eines neuen Arrays und Kopieren des Inhalts des alten Arrays in dieses ist es jedoch möglich, eine dynamische Version eines Arrays effektiv zu implementieren ; siehe dynamisches Array . Wenn dieser Vorgang selten durchgeführt wird, benötigen Einfügungen am Ende des Arrays nur amortisierte konstante Zeit.

Einige Array-Datenstrukturen weisen den Speicher nicht neu zu, speichern jedoch eine Zählung der Anzahl von Elementen des verwendeten Arrays, die als Zählung oder Größe bezeichnet wird. Dies macht das Array effektiv zu einem dynamischen Array mit einer festen maximalen Größe oder Kapazität; Pascal-Strings sind Beispiele dafür.

Nichtlineare Formeln

Gelegentlich werden kompliziertere (nichtlineare) Formeln verwendet. Für ein kompaktes zweidimensionales dreieckiges Array beispielsweise ist die Adressierungsformel ein Polynom vom Grad 2.

Effizienz

Beide speichern und wählen die konstante Zeit (deterministischer Worst-Case) aus . Arrays nehmen linearen ( O ( n )) Platz in der Anzahl der Elemente n ein , die sie enthalten.

In einem Array mit der Elementgröße k und auf einer Maschine mit einer Cachezeilengröße von B Byte erfordert das Iterieren durch ein Array von n Elementen das Minimum an Cache-Fehltreffern ( nk /B), da seine Elemente zusammenhängende Speicherplätze belegen. Dies ist ungefähr um einen Faktor von B/ k besser als die Anzahl von Cache-Fehlversuchen, die benötigt werden, um auf n Elemente an zufälligen Speicherstellen zuzugreifen . Infolgedessen ist die sequentielle Iteration über ein Array in der Praxis merklich schneller als die Iteration über viele andere Datenstrukturen, eine Eigenschaft namens Locality of reference (dies bedeutet jedoch nicht , dass die Verwendung eines perfekten Hashs oder trivialen Hashs innerhalb desselben (lokalen) Arrays , wird nicht noch schneller - und in konstanter Zeit erreichbar ). Bibliotheken bieten auf niedriger Ebene optimierte Einrichtungen zum Kopieren von Speicherbereichen (wie z. B. memcpy ), die verwendet werden können, um zusammenhängende Blöcke von Array-Elementen wesentlich schneller zu verschieben, als dies durch den Zugriff auf einzelne Elemente erreicht werden kann. Die Beschleunigung solcher optimierter Routinen variiert je nach Größe der Array-Elemente, Architektur und Implementierung.

Speichermäßig sind Arrays kompakte Datenstrukturen ohne Overhead pro Element . Es kann einen Overhead pro Array geben (zB um Indexgrenzen zu speichern), aber dies ist sprachabhängig. Es kann auch vorkommen, dass Elemente, die in einem Array gespeichert sind, weniger Speicher benötigen als die gleichen Elemente, die in einzelnen Variablen gespeichert sind, da mehrere Array-Elemente in einem einzigen Wort gespeichert werden können ; solche Arrays werden oft als gepackte Arrays bezeichnet. Ein extremer (aber häufig verwendeter) Fall ist das Bit-Array , bei dem jedes Bit ein einzelnes Element darstellt. Ein einzelnes Oktett kann somit in der kompaktesten Form bis zu 256 verschiedene Kombinationen von bis zu 8 verschiedenen Bedingungen aufnehmen.

Array-Zugriffe mit statisch vorhersagbaren Zugriffsmustern sind eine Hauptquelle für Datenparallelität .

Vergleich mit anderen Datenstrukturen

Dynamische Arrays oder erweiterbare Arrays ähneln Arrays, bieten jedoch die Möglichkeit, Elemente einzufügen und zu löschen. Das Hinzufügen und Löschen am Ende ist besonders effizient. Jedoch behalten sie linear ( Θ ( n )) zusätzliche Speicherung, während Arrays keine zusätzlichen Speicher reservieren.

Assoziative Arrays bieten einen Mechanismus für eine Array-ähnliche Funktionalität ohne großen Speicher-Overhead, wenn die Indexwerte spärlich sind. Ein Array, das nur Werte an den Indizes 1 und 2 Milliarden enthält, kann beispielsweise von der Verwendung einer solchen Struktur profitieren. Spezialisierte assoziative Arrays mit Integer-Schlüsseln umfassen Patricia-Tricks , Judy-Arrays und Van-Emde-Boas-Bäume .

Ausgeglichene Bäume benötigen O(log n ) Zeit für den indizierten Zugriff, erlauben aber auch das Einfügen oder Löschen von Elementen in O(log n ) Zeit, während erweiterbare Arrays lineare (Θ( n )) Zeit benötigen , um Elemente an einer beliebigen Position einzufügen oder zu löschen.

Verknüpfte Listen ermöglichen das konstante Entfernen und Einfügen in der Mitte, benötigen jedoch lineare Zeit für den indizierten Zugriff. Ihre Speichernutzung ist in der Regel schlechter als bei Arrays, aber immer noch linear.

Ein Iliffe-Vektor ist eine Alternative zu einer mehrdimensionalen Array-Struktur. Es verwendet ein eindimensionales Array von Verweisen auf Arrays mit einer Dimension weniger. Insbesondere für zwei Dimensionen wäre diese alternative Struktur ein Vektor von Zeigern auf Vektoren, einer für jede Zeile (Zeiger auf c oder c++). Somit würde auf ein Element in Zeile i und Spalte j eines Arrays A durch doppelte Indizierung ( A [ i ][ j ] in typischer Notation) zugegriffen . Diese alternative Struktur ermöglicht gezackte Arrays , bei denen jede Zeile eine andere Größe haben kann – oder allgemein, bei denen der gültige Bereich jedes Index von den Werten aller vorhergehenden Indizes abhängt. Es spart auch eine Multiplikation (mit dem Spaltenadreßinkrement), indem es sie durch eine Bitverschiebung ersetzt (um den Vektor der Zeilenzeiger zu indizieren) und einen zusätzlichen Speicherzugriff (Abrufen der Zeilenadresse), was bei einigen Architekturen lohnenswert sein kann.

Abmessungen

Die Dimension eines Arrays ist die Anzahl der Indizes, die benötigt werden, um ein Element auszuwählen. Wenn also das Array als Funktion einer Menge möglicher Indexkombinationen betrachtet wird, ist es die Dimension des Raums, dessen Domäne eine diskrete Teilmenge ist. Somit ist ein eindimensionales Array eine Liste von Daten, ein zweidimensionales Array ist ein Datenrechteck, ein dreidimensionales Array ein Datenblock usw.

Dies sollte nicht mit der Dimension der Menge aller Matrizen mit einer gegebenen Domäne verwechselt werden, d. h. der Anzahl der Elemente im Array. Ein Array mit 5 Zeilen und 4 Spalten ist beispielsweise zweidimensional, aber solche Matrizen bilden einen 20-dimensionalen Raum. In ähnlicher Weise kann ein dreidimensionaler Vektor durch ein eindimensionales Array der Größe drei dargestellt werden.

Siehe auch

Verweise