Wenn wir ein Array erstellen, können wir seine Größe nicht ändern; es ist repariert. OK, scheint nett, wir können ein neues größeres Array erstellen und die Werte eins nach dem anderen kopieren, und das ist wenig langsam. Was ist der technische Hintergrund davon?Warum sind Arrays nicht erweiterbar?
Diese Frage nicht erwähnt eine Sprache, also werde ich C-basierte Arrays für meine Antwort wählen.
Arrays werden als einzelner Speicherblock zugewiesen. Das Wachsen eines Arrays ist problematisch, weil der einzige Weg, es richtig zu machen, es am Ende wachsen kann. Für ein Wachstum der Größe N müssen am Ende des Arrays vor der nächsten zugewiesenen Adresse mindestens N freie Bytes vorhanden sein.
Wenn diese Art der Zuweisung unterstützt wird, müssen die Zuweisungen über den virtuellen Adressraum verteilt werden. Dies beseitigt sowohl die Vorteile, Speicherzuweisungen näher beieinander zu haben, als auch die Fragmentierung zu erhöhen. Dies steht im Widerspruch zu den meisten Speicherverwaltern, die versuchen, Speicher zusammenzupacken und Fragmentierung zu reduzieren.
Das Zuweisen eines neuen Arrays an einen Platz im Speicher mit ausreichend Speicherplatz und das Kopieren des Arrays gibt es einfach nicht als eine allgemeine Lösung. Der Grund dafür ist, dass die vorherige Position des Arrays für die Konsumenten durch Zeiger sichtbar ist.
int* array = malloc(int*someSize);
int* pointer1 = &(arr[2]);
growArray(&array, 12); // Can't move because pointer1 knows the address of the array
Ich denke du warst bis zum letzten Absatz gut. Es ist * möglich, du musst nur aufpassen, dass du keine herabhängenden Zeiger hinterlässt. Er hat das trotzdem als Java gespeichert. – mpen
@Mark, ich habe es geändert, um "als allgemeine Lösung" in den Text aufzunehmen, um diesen Punkt ein wenig deutlicher zu behandeln. – JaredPar
+1 Große Antwort. – helpermethod
Ein Array an seinen Wurzeln ist ein zusammenhängendes "Array" von Speicher. Andere Daten können Daten vor und nach diesem Speicherbereich belegen, daher kann die Größe nicht dynamisch geändert werden, ohne dass ein neuer, anderer Speicherbereich zugewiesen wird, der zu der neuen, größeren Größe passt.
Es hängt von der Sprache ab.
In C (und ähnlichen Sprachen wie Java), wenn Sie ein Array wie int ary[10] deklariert haben, legte das System genau genug Speicher zur Verfügung, um zehn ganze Zahlen Rücken an Rücken zu halten. Es war nicht einfach, es zu erweitern, da das System keinen zusätzlichen Speicherplatz reserviert hat (da es keine Ahnung hat, ob Sie es erweitern möchten oder um wie viel) und den Speicher, der direkt nach der Verwendung des Arrays verwendet wurde durch etwas anderes. Die einzige Möglichkeit, ein größeres Array zu erhalten, bestand darin, einen neuen Speicherblock bereitzustellen, der das erweiterte Array enthält, dann den alten Inhalt zu kopieren und die neuen Elemente hinzuzufügen.
Sie haben Recht, dass dies langsam sein kann. Eine Möglichkeit ist es, deine Arrays größer zu deklarieren, als du sie brauchst, um dir Raum zum Wachsen zu geben. Vor allem auf älteren Computern könnte dies dazu führen, dass ein Programm eine Menge Speicher verbraucht, die es nie benutzt hat.
Eine andere Möglichkeit ist es, eine höhere Sprache zu verwenden, die erweiterbare Arrays bietet. Mit Ruby können Sie beispielsweise mehr Elemente zu einem Array hinzufügen, ohne dass Sie Speicher deklarieren oder Array-Inhalt kopieren müssen.
Sie sollten jedoch beachten, dass die Arrays in einer Sprache mit Arrays variabler Größe wahrscheinlich immer noch von einem Speicher mit fester Größe unterstützt werden, der bei Bedarf erweitert und kopiert wird. (Oder es ist als eine verkettete Liste implementiert, die die Notwendigkeit zum Kopieren vermeidet, aber andere Nachteile in Bezug auf den Zugriff auf beliebige Indizes hat.) –
Ruby macht einfach die Speicherzuweisung und Datenkopie für Sie. Es gibt keinen Weg um das Problem auf der Hardware-Ebene. Oder vielleicht nutzt es eine Datenstruktur, die eine langsamere Zugriffszeit hat, aber ohne Neuzuweisung größer werden kann. – phkahler
@JS Bangs, phkahler- Beide gute Punkte. Mein wichtigster Punkt war, dass Sie sich keine Sorgen machen müssen, es selbst zu tun. – bta
Abhängig von Ihrer Sprache, aber Arrays sind in der Regel als eine Reihe von sequenziellen Leerzeichen im Speicher angeordnet. Auf diese Weise müssen Sie keine Speicherorte für jeden Punkt im Array speichern, Sie speichern nur einen Speicherplatz (den Anfang des Arrays) und fügen dann einen Offset hinzu (der Offset wäre die Größe jedes Eintrags multipliziert mit dem Index) Sie wollten herausfinden, wo sich ein bestimmter Eintrag im Speicher befindet.
Dies ist auch der Grund, warum Arrays typischerweise nur einen Typ enthalten, sonst könnten Sie eine solche einfache Berechnung nicht durchführen. Sprachen, in denen Sie mehrere Typen speichern können, erstellen tatsächlich ein normales Array und platzieren Zeiger auf jeden Eintrag im Array - alle Zeiger haben normalerweise die gleiche Größe. Dieses Niveau der indirekten Kosten und deshalb sind "einfachere" Sprachen tendenziell ein bisschen langsamer.
Wie auch immer, wenn Sie mehr Speicher zuweisen, möchten Sie den neuen Speicher direkt am Ende des Arrays setzen - sonst würden Sie Ihren Speicher mit einem Loch segmentieren - warum würden Sie das tun?
Sie können also nicht einfach das Array erweitern, ohne es physisch zu bewegen.
Computer tun dies seit Jahren, so dass die meisten Sprachen eine Möglichkeit haben, einen neuen Speicherblock zuzuweisen und dann die CPU anweisen, alle Einträge auf den neuen Block zu kopieren und den Zeiger zu ändern, um dies zu berücksichtigen, aber oft (C, Java, ...) überlassen sie dies den Programmierern mit speziellen Befehlen, um das Array zu kopieren, anstatt es für Sie zu tun (möglicherweise nur um Sie wissen zu lassen, dass das Erweitern eines Arrays nicht "frei" ist) Es wäre möglich, einen Zeiger am Ende des Arrays hinzuzufügen, um zu einem Block des neuen Speichers zu springen, den Sie am Ende eines Arrays hinzufügen möchten, aber jetzt ist Ihr Array-Lookup um einen ziemlich beträchtlichen Betrag langsamer geworden
Viele Sprachen umschließen Arrays einfach als Sammlungen, die diese Art von Funktionalität ermöglichen. Zum Beispiel wird eine Java Vector/ArrayList automatisch Speicher für Sie neu zuordnen.Eine verkettete Liste weist eigentlich nur jeweils ein einzelnes Element mit einem Zeiger auf den nächsten zu. Macht es sehr schnell, Elemente hinzuzufügen, aber wirklich langsam zu Element 5000 zu gehen (Sie müssen jedes einzelne Element lesen, während mit einem Array Element 1 ist so schnell wie Element 5000)
Generell Programmiersprache haben irgendwo eine Abstraktion von etwas, das einen festen Teil des Speichers zuzuordnen. Aus dieser Abstraktion können dann andere Abstraktionen erzeugt werden, die die Komplexität der Speicherverwaltung verbergen, möglicherweise durch Verschieben/Kopieren von Daten.
Die meiste Zeit sind array fixiert - eine (irgendwie) Abstraktion Low-Level - und lists oder collectionsoben auf Arrays aufgebaut sind und wissen, wie sie sich dynamisch ändern.
Es ist praktisch, solche Low-Level-Abstraktion zu haben, um effiziente Algorithmen/Optimierungen manchmal zu implementieren. In den meisten Fällen können Sie jedoch Listen und Sammlungen verwenden, ohne sich um die Leistung zu sorgen.
Ob Sie die Größe eines Arrays ändern können, hängt davon ab, welche Sprache Sie verwenden. In den Sprachen, in denen Sie die Größe eines Arrays nicht erhöhen können, liegt der Grund darin, dass Arrays an aufeinanderfolgenden Speicherorten angeordnet sind und der Compiler nicht garantieren kann, dass die dem Array-Ende folgenden Speicherorte dem Array hinzugefügt werden können. Viele Programmiersprachen unterstützen erweiterbare Array-Typen, die jedoch lediglich die Neuzuweisung und das Kopieren des zugrunde liegenden Speichers für Sie übernehmen.
Zum Beispiel gibt es in der Curl-Programmiersprache einen FastArray-Typ, der eine Größe und eine maximale Größe hat. Die maximale Größe gibt die maximale Größe des Arrays an und bestimmt, wie viel Speicher dem Array zugewiesen wird. Es gibt einen allgemeineren Array-Typ, der ein FastArray als zugrunde liegende Implementierung verwendet und die FastArray-Instanz ersetzt, wenn das Array über die maximale Größe des zugrunde liegenden FastArray hinaus erweitert werden muss.
Zurück in der Assemblersprache musste man den benötigten Speicherplatz für eine Variable deklarieren. Dies war reservierter Speicher in der Data Segment (DS) -Registrierung.
So suchen etwa wie so (Borland Turbo Assembler):
.DATA
myStringVariable DB "Hello world!", 13, 10
myArrayVariable DW " " 'Reserving 20 bytes in memory (in a row)
.CODE
MOV AX, @DATA
MOV DS, AX
' ...
Dann, wenn die.Das Datensegment wurde abgegrenzt, es konnte nicht geändert werden, da das CODE-Segment (CS) bei einigen wenigen Bytes weiter begann.
Also, wenn ein Array erweiterbar gewesen wäre, wie Sammlungen in .NET sind, würden die Daten den Code überschrieben, so dass das Programm zum Absturz usw.
C/C++ (3,0), Pascal (7.0), QBasic-, PowerBasic- und COM-Debug-Programme basierten auf dieser Architektur und konnten besser als Assembler erlauben.
Heute, mit der flexibleren Technologie, sind wir nun in der Lage, Speicheradressen im Bedarfsfall spontan zuzuordnen und einen Verweis auf sie mit nur einer Variablen zu behalten, so dass Arrays mit Sammlung erweiterbar sind. Aber es gibt eine Situation, in der Sie eine genaue Menge an Bytes einhalten müssen, wie zum Beispiel Netzwerkpakete usw., wo Arrays immer noch nützlich sind. Ein anderes Beispiel ist das Speichern von Bildern in einer Datenbank. Sie wissen genau, dass mow large in Bytes ein Bild ist, also können Sie es in einem Byte-Array (Byte []) speichern.
Vielleicht fehlen mir hier ein paar Präzisionen, ich habe geschrieben, woran ich mich aus meinen alten Lieblings-Programmiersprachen erinnere. Vielleicht können einige Leute etwas detailliertere Sachen aufbringen.
Hoffe, das hilft! =)
Welche Sprache benutzen Sie? –
Sie möchten die Programmiersprache, mit der Sie sprechen, spezifizieren. – Kzqai
Das ist eine sehr weit gefasste Frage. Um wirklich zu verstehen, müssen Sie die inneren Abläufe des Computers kennen. – ChaosPandion