Dynamisches Array - Dynamic array

Image
Mehrere Werte werden am Ende eines dynamischen Arrays durch geometrische Expansion eingefügt. Graue Zellen zeigen Platz an, der für die Erweiterung reserviert ist. Die meisten Einfügungen sind schnell (konstante Zeit), während einige aufgrund der Notwendigkeit einer Neuzuweisung langsam sind (Θ( n )-Zeit, gekennzeichnet mit Schildkröten). Die logische Größe und Kapazität des endgültigen Arrays werden angezeigt.

In der Informatik , ein dynamisches Array , wachstumsfähigen Anordnung , Größe veränderbar Array , dynamische Tabelle , änderbare Array oder Array - Liste ist eine Direktzugriffs variabler Größenliste Datenstruktur , die Elemente hinzugefügt werden oder entfernt werden kann. Es wird mit Standardbibliotheken in vielen modernen Mainstream-Programmiersprachen geliefert. Dynamische Arrays überwinden eine Grenze von statischen Arrays , die eine feste Kapazität haben, die bei der Zuweisung angegeben werden muss.

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 als Back-End verwenden kann.

Dynamische Arrays und Kapazität mit begrenzter Größe

Ein einfaches dynamisches Array kann konstruiert werden, indem ein Array fester Größe zugewiesen wird, typischerweise größer als die Anzahl der sofort benötigten Elemente. Die Elemente des dynamischen Arrays werden zusammenhängend am Anfang des zugrunde liegenden Arrays gespeichert, und die verbleibenden Positionen am Ende des zugrunde liegenden Arrays werden reserviert oder nicht verwendet. Elemente können am Ende eines dynamischen Arrays in konstanter Zeit hinzugefügt werden, indem der reservierte Speicherplatz verwendet wird, bis dieser Speicherplatz vollständig verbraucht ist. Wenn der gesamte Speicherplatz verbraucht 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 wird. 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 oder Größe , während die Größe des zugrunde liegenden Arrays als Kapazität oder physikalische Größe des dynamischen Arrays bezeichnet wird , was die maximal mögliche Größe ohne Verlagerung von Daten ist.

Ein Array mit fester Größe reicht in Anwendungen aus, bei denen die maximale logische Größe festgelegt ist (zB durch Spezifikation) oder berechnet werden kann, bevor das Array zugewiesen wird. Ein dynamisches Array kann bevorzugt werden, wenn:

  • die maximale logische Größe ist unbekannt oder schwer zu berechnen, bevor das Array zugewiesen wird
  • Es wird davon ausgegangen, dass sich eine durch eine Spezifikation angegebene maximale logische Größe wahrscheinlich ändern wird
  • die amortisierten Kosten für die Größenänderung eines dynamischen Arrays wirken sich nicht wesentlich auf die Leistung oder Reaktionsfähigkeit aus

Geometrische Erweiterung und fortgeführte Kosten

Um zu vermeiden, dass die Kosten für eine mehrfache Größenänderung anfallen, ändern dynamische Arrays die Größe um einen großen Betrag, beispielsweise durch Verdoppeln der Größe, und verwenden den reservierten Speicherplatz für zukünftige Erweiterungen. Das Hinzufügen eines Elements zum Ende kann wie folgt funktionieren: 

function insertEnd(dynarray a, element e)
    if (a.size == a.capacity)
        // resize a to twice its current capacity:
        a.capacity ← a.capacity * 2 
        // (copy the contents to the new memory location here)
    a[a.size] ← e
    a.size ← a.size + 1

Wenn n Elemente eingefügt werden, bilden die Kapazitäten einen geometrischen Verlauf . Das Erweitern des Arrays um einen beliebigen konstanten Anteil a stellt sicher, dass das Einfügen von n Elementen insgesamt O ( n ) Zeit in Anspruch nimmt, was bedeutet, dass jedes Einfügen eine amortisierte konstante Zeit benötigt. Viele dynamische Arrays geben auch einen Teil des zugrunde liegenden Speichers frei, wenn seine Größe unter einen bestimmten Schwellenwert fällt, beispielsweise 30 % der Kapazität. Dieser Schwellenwert muss strikt kleiner als 1/ a sein, um Hysterese bereitzustellen (ein stabiles Band bereitzustellen, um wiederholtes Anwachsen und Schrumpfen zu vermeiden) und gemischte Sequenzen von Einfügungen und Entfernungen mit amortisierten konstanten Kosten zu unterstützen.

Dynamische Arrays sind ein gängiges Beispiel beim Unterrichten der amortisierten Analyse .

Wachstumsfaktor

Der Wachstumsfaktor für das dynamische Array hängt von mehreren Faktoren ab, einschließlich einem Raum-Zeit-Kompromiss und Algorithmen, die im Speicherzuordner selbst verwendet werden. Für den Wachstumsfaktor a beträgt die durchschnittliche Zeit pro Einfügevorgang etwa a /( a –1), während die Anzahl der verschwendeten Zellen nach oben durch ( a –1) n begrenzt ist . Wenn der Speicherzuordner einen First-Fit-Zuordnungsalgorithmus verwendet, können Wachstumsfaktorwerte wie a = 2 dazu führen, dass der dynamischen Array-Erweiterung der Speicher ausgeht, obwohl möglicherweise noch eine beträchtliche Menge an Speicher verfügbar ist. Es gab verschiedene Diskussionen über ideale Wachstumsfaktorwerte, darunter Vorschläge für den Goldenen Schnitt sowie den Wert 1,5. Viele Lehrbücher verwenden jedoch a  = 2 aus Gründen der Einfachheit und zu Analysezwecken.

Im Folgenden sind Wachstumsfaktoren aufgeführt, die von mehreren beliebten Implementierungen verwendet werden:

Implementierung Wachstumsfaktor ( a )
Java ArrayList 1,5 (3/2)
Python PyListObject ~1.125 (n + n >> 3)
Microsoft Visual C++ 2013 1,5 (3/2)
G++ 5.2.0 2
Klang 3.6 2
Facebook Torheit/FBVector 1,5 (3/2)
Rost Vec 2
Geh Scheiben zwischen 1,25 und 2

Leistung

Vergleich von Listendatenstrukturen
Spähen Mutieren (einfügen oder löschen) bei … Überschüssiger Speicherplatz,
durchschnittlich
Anfang Ende Mitte
Verlinkte Liste Θ( n ) (1) Θ(1), bekanntes Endelement;
Θ( n ), unbekanntes Endelement 		Peek-Zeit +
Θ(1) 		Θ( n )
Array (1) N / A N / A N / A 0
Dynamisches Array (1) Θ( n ) Θ(1) abgeschrieben Θ( n ) Θ( n )
Ausgeglichener Baum Θ(log n) Θ(log n) Θ(log n ) Θ(log n ) Θ( n )
Random- Access-Liste Θ(log n) (1) N / A N / A Θ( n )
Hash-Array-Baum (1) Θ( n ) Θ(1) abgeschrieben Θ( n ) Θ(√ n )

Das dynamische Array hat eine ähnliche Leistung wie ein Array, mit dem Hinzufügen neuer Operationen zum Hinzufügen und Entfernen von Elementen:

  • Abrufen oder Festlegen des Werts an einem bestimmten Index (konstante Zeit)
  • Iteration über die Elemente der Reihe nach (lineare Zeit, gute Cache-Performance)
  • Einfügen oder Löschen eines Elements in der Mitte des Arrays (lineare Zeit)
  • Einfügen oder Löschen eines Elements am Ende des Arrays (konstante amortisierte Zeit)

Dynamische Arrays profitieren von vielen Vorteilen von Arrays, einschließlich guter Referenzlokalität und Datencachenutzung , Kompaktheit (geringer Speicherverbrauch) und Direktzugriff . Sie haben in der Regel nur einen geringen festen zusätzlichen Overhead für die Speicherung von Informationen über Größe und Kapazität. Dies macht dynamische Arrays zu einem attraktiven Werkzeug zum Aufbau Cache- freundlicher Datenstrukturen . In Sprachen wie Python oder Java, die Referenzsemantik erzwingen, speichert das dynamische Array jedoch im Allgemeinen nicht die tatsächlichen Daten, sondern Referenzen auf die Daten, die sich in anderen Speicherbereichen befinden. In diesem Fall beinhaltet der sequentielle Zugriff auf Elemente im Array tatsächlich den Zugriff auf mehrere nicht zusammenhängende Speicherbereiche, so dass die vielen Vorteile der Cache-Freundlichkeit dieser Datenstruktur verloren gehen.

Im Vergleich zu verknüpften Listen haben dynamische Arrays eine schnellere Indizierung (konstante Zeit gegenüber linearer Zeit) und typischerweise eine schnellere Iteration aufgrund der verbesserten Referenzlokalität; dynamische Arrays benötigen jedoch lineare Zeit zum Einfügen oder Löschen an einer beliebigen Stelle, da alle folgenden Elemente verschoben werden müssen, während verknüpfte Listen dies in konstanter Zeit tun können. Dieser Nachteil wird durch den Lückenpuffer und die abgestuften Vektorvarianten gemildert, die unten unter Varianten diskutiert werden. Außerdem kann es in einem stark fragmentierten Speicherbereich teuer oder unmöglich sein, zusammenhängenden Platz für ein großes dynamisches Array zu finden, wohingegen verknüpfte Listen nicht erfordern, dass die gesamte Datenstruktur zusammenhängend gespeichert wird.

Ein ausgeglichener Baum kann eine Liste speichern, während er alle Operationen sowohl von dynamischen Arrays als auch von verknüpften Listen einigermaßen effizient bereitstellt, aber sowohl das Einfügen am Ende als auch die Iteration über die Liste sind theoretisch und praktisch langsamer als bei einem dynamischen Array, da nicht zusammenhängende Speicher- und Baumdurchquerungs-/Manipulations-Overhead.

Varianten

Lückenpuffer ähneln dynamischen Arrays, ermöglichen jedoch effiziente Einfüge- und Löschoperationen, die in der Nähe derselben willkürlichen Stelle geclustert sind. Einige Deque- Implementierungen verwenden Array deques , die ein amortisiertes Einfügen/Entfernen mit konstanter Zeit an beiden Enden ermöglichen, anstatt nur an einem Ende.

Goodrich präsentierte einen dynamischen Array-Algorithmus namens Tiered Vectors , der eine Leistung von O ( n 1/ k ) für Einfügungen und Löschungen von überall im Array und O ( k ) get und set bietet, wobei k ≥ 2 ein konstanter Parameter ist.

Der Hash-Array-Baum (HAT) ist ein dynamischer Array-Algorithmus, der 1996 von Sitarski veröffentlicht wurde. Der Hash-Array-Baum verschwendet n 1/2 Speicherplatz, wobei n die Anzahl der Elemente im Array ist. Der Algorithmus hat eine amortisierte Leistung von O (1), wenn eine Reihe von Objekten an das Ende eines Hash-Array-Baums angehängt wird.

In einer Arbeit von 1999 haben Brodnik et al. beschreiben eine gestufte dynamische Array-Datenstruktur, die zu jedem Zeitpunkt nur n 1/2 Platz für n Elemente verschwendet , und sie beweisen eine untere Grenze, die zeigt, dass jedes dynamische Array so viel Platz verschwenden muss, wenn die Operationen zeitkonstant amortisiert bleiben sollen . Darüber hinaus stellen sie eine Variante dar, bei der das Wachsen und Verkleinern des Puffers sich nicht nur amortisiert hat, sondern im schlimmsten Fall die konstante Zeit.

Bagwell (2002) präsentierte den VList-Algorithmus, der angepasst werden kann, um ein dynamisches Array zu implementieren.

Sprachunterstützung

C ++ ‚s std::vectorund Rust ‘ s std::vec::Vecsind Implementierungen von dynamischen Arrays, wie die ArrayListmitgelieferten Klassen mit dem Java - API und dem .NET Framework .

Die List<>mit Version 2.0 von .NET Framework bereitgestellte generische Klasse wird auch mit dynamischen Arrays implementiert. Smalltalk 's OrderedCollectionist ein dynamisches Array mit dynamischem Start- und Endindex, wodurch das Entfernen des ersten Elements auch O(1) macht.

Die listDatentypimplementierung von Python ist ein dynamisches Array.

Delphi und D implementieren im Kern der Sprache dynamische Arrays.

Das Ada.Containers.Vectorsgenerische Paket von Ada bietet eine dynamische Array-Implementierung für einen bestimmten Untertyp.

Viele Skriptsprachen wie Perl und Ruby bieten dynamische Arrays als integrierten primitiven Datentyp an .

Mehrere plattformübergreifende Frameworks bieten dynamische Array-Implementierungen für C , einschließlich CFArrayund CFMutableArrayin Core Foundation und GArrayund GPtrArrayin GLib .

Common Lisp bietet eine rudimentäre Unterstützung für größenveränderbare Vektoren, indem es ermöglicht, den eingebauten arrayTyp als anpassbar zu konfigurieren und den Ort der Einfügung durch den Füllzeiger .

Verweise

  1. ^ a b Siehe zum Beispiel den Quellcode der java.util.ArrayList-Klasse von OpenJDK 6 .
  2. ^ Lambert, Kenneth Alfred (2009), "Physische Größe und logische Größe" , Grundlagen von Python: Von den ersten Programmen durch Datenstrukturen , Cengage Learning, p. 510, ISBN 978-1423902188
  3. ^ a b Goodrich, Michael T. ; Tamassia, Roberto (2002), „1.5.2 Analysing an Extendable Array Implementation“, Algorithm Design: Foundations, Analysis and Internet Examples , Wiley, S. 39–41.
  4. ^ a b Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "17.4 Dynamische Tabellen". Einführung in Algorithmen (2. Aufl.). MIT Press und McGraw-Hill. S. 416–424. ISBN 0-262-03293-7.
  5. ^ a b c "C++ STL-Vektor: Definition, Wachstumsfaktor, Memberfunktionen" . Archiviert vom Original am 2015-08-06 . Abgerufen 2015-08-05 .
  6. ^ "Vektorwachstumsfaktor von 1,5" . comp.lang.c++.moderiert . Google-Gruppen.
  7. ^ Listen Sie die Objektimplementierung von github.com/python/cpython/ auf, abgerufen am 23.03.2020.
  8. ^ Brais, Hadi. "Sezieren des C++-STL-Vektors: Teil 3 - Kapazität und Größe" . Mikromysterien . Abgerufen 2015-08-05 .
  9. ^ "Facebook / Torheit" . GitHub . Abgerufen 2015-08-05 .
  10. ^ "rost-lang/rost" . GitHub . Abgerufen 2020-06-09 .
  11. ^ "golang/go" . GitHub . Abgerufen 2021-09-14 .
  12. ^ Tag 1 Keynote - Bjarne Stroustrup: C++11 Style bei GoingNative 2012 auf channel9.msdn.com ab Minute 45 oder Folie 44
  13. ^ Zahlenverarbeitung: Warum Sie nie wieder eine verlinkte Liste in Ihrem Code auf kjellkod.wordpress.com verwenden sollten
  14. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF) , Department of Computer Science, University of Waterloo
  15. ^ a b c Chris Okasaki (1995). "Rein funktionale Random-Access-Listen". Proceedings of the Seventh International Conference on Functional Programming Languages ​​and Computer Architecture : 86–95. doi : 10.1145/224164.224187 .
  16. ^ Goodrich, Michael T .; Kloss II, John G. (1999), "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences" , Workshop on Algorithms and Data Structures , Lecture Notes in Computer Science, 1663 : 205–216 , doi : 10.1007/3-540 -48447-7_21 , ISBN 978-3-540-66279-2
  17. ^ Sitarski, Edward (September 1996), "HATs: Hashed Array Trees" , Algorithm Alley, Dr. Dobb's Journal , 21 (11)
  18. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (PDF) (Technical Report CS-99-09), Department of Computer Science, University of Waterloo
  19. ^ Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays , EPFL
  20. ^ Javadoc aufArrayList
  21. ^ ArrayList-Klasse

Externe Links