TList / dyn. Array - Was steckt dahinter?

[Mr_G]

Hallo zusammen,
mein Info-Lehrer hat mir gesteckt, dass sich hinter dynamsichen Arrays auch nur verkettete Listen verbergen und ich habe herausgefunden, dass die TList wiederum nur das OOP Pendant zu einem dynamischen Array ist.
Nun hätte ich mal rein interessehalber die Frage, wie das denn nun funktioniert.
Gruß Mr_G

[Nikolas]

Das ein dynamisches Array ein verkettete Liste ist, glaube ich nicht. Das interessante bei einem Array ist doch die konstante Zugriffszeit. Bei einer Liste hast du immer eine Zugriffzeit, die linear zur Größe der Liste ist.
Ich habe gelernt, dass ein dynamisches Array ein normales Array ist, dessen Größe automatisch verdoppelt wird, wenn es voll ist, bzw halbiert, wenn es nur noch zu 25% gefüllt ist. (Werte ohne Gewähr, sollte auch von der Implmenetierung abhängen.)
Damit hast du (amortisiert) alle Aktionen (lesen, schreiben, löschen) in konstanter Zeit.

[grenzgaenger]

'n dyn. array ist keine verkettet liste. denn die verkettete liste ist eine dynamische datenstruktur, das dyn.array nicht.

das dyn.array ist nix anderes als eine array of pointer, welche dynamisch vergrössert und verkleinert wird. das macht man entweder mit der hand oder man lässt es machen (z.b. tList, welches die entsprechenden routinen bereits integriert hat).

[SirThornberry]

Ein dynamisches Array ist in Delphi definitiv keine verkettete Liste. Es handelt sich bei Arrays in Delphi um zusammenhängenden Speicher. Schreibt man also über Elemte X drüber hinaus schreibt man in Element X+1 hinein. Da die Elemente direkt hintereinander liegen macht es auch keinen Sinn zusätzlich diese miteinander durch Pointer zu verketten da durch Berechnung klar ist wo ElementX liegt.

Zitat:

das dyn.array ist nix anderes als eine array of pointer

Auch das stimmt nicht wobei ich denke das du das richtige meinst. Ein dynamisches Array ist kein Array of Pointer sondern ein Pointer auf zusammenhängenden Speicher welcher durch den Compiler als Array angesprochen werden kann.

[Nikolas]

Wird bei einer Vergrößerung dann das alte Array in einen anderen Bereich kopiert oder besteht dass Array dann aus verschiedenen Stücken auf der Platte?

[Mr_G]

Danke für die zügigen Antworten!
Ich habe mir das irgendwie schon gedacht. Also entweder habe ich mich verhört oder mein Lehrer(:shock:) hat unrecht...

Zitat:

Zitat von grenzgaenger

...das dyn.array ist nix anderes als eine array of pointer...

Wieso of Pointer? Bei der Deklaration wird doch ein gewünschter einheitlicher Datentyp angegeben.

[grenzgaenger]

dein info lehrer hat unrecht.

ganz einfach, weil du in das array alles mögliche verpacken kannst. vorteil von der array struktur ist, dass du auf die jeweiligen elemente direkt zugreifen kannst, das ging mit einer liste oder baum nicht, somit hast du die möglichkeit effiziente sortieralgorithmen darauf zu implementieren.

'n pointer ist einfach die effizienteste datengrösse, welche dein prozessor abarbeiten kann (integer), und ist einfach eine adresse im speicher... nicht mehr, nicht weniger.

[DeddyH]

Zitat:

Zitat von grenzgaenger

'n pointer ist einfach die effizienteste datengrösse, welche dein prozessor abarbeiten kann (integer), und ist einfach eine adresse im speicher... nicht mehr, nicht weniger.

Und eben deshalb so extrem flexibel, da die dahinterstehenden Daten von einem beliebigen Typ sein können.

[Zacherl]

Natürlich ist ein Array auch ein Pointer aber praktisch alle Datentypen in Delphi sind Zeiger, auch wenn man davon meist nichts direkt mitbekommt.
Die treffenste Beschreibung hier ist der zusammenhängende Speicherbereich. Da der Datentyp ja feststeht hat der Speicherbereich die Größe der Summe aller Elemente mal der Datentypgröße. (n * SizeOf(TDatenTyp))

[SirThornberry]

Zitat:

Zitat von Nikolas

Wird bei einer Vergrößerung dann das alte Array in einen anderen Bereich kopiert oder besteht dass Array dann aus verschiedenen Stücken auf der Platte?

Das kommt auf den Speichermanager an. Wenn ich mich recht entsinne wird ReAllocMem verwendet. Einige Speichermanager schauen dann ob dahinter noch platz ist und somit entsprechend das array vergrößert werden kann. Andere hingegen reservieren einfach neuen speicherplatz und geben den alten frei.

[3_of_8]

Genau. Ein array ist in Delphi ersteinmal ein Pointer auf dem Stack (oder in einem Prozessorregister), der auf einen Bereich im Heap zeigt. Dieser Bereich hat eine feste Größe. Wenn man setlength aufruft, verändert der Speichermanager diese Größe. Überschneidet sich die neue Größe mit anderen Daten, wird das Array - glaube ich - an eine andere Stelle kopiert, die groß genug ist, und dann vergrößert.

Dass ein Array in Delphi eine verkettete Liste ist, ist eine Aussage, für die man einen Infolehrer erschießen sollte. Ich kenne keine Sprache, in der das so ist.

[Mr_G]

Zitat:

Zitat von grenzgaenger

dein info lehrer hat unrecht.

... Es sei denn ich habe mich verhört und er hat das nicht so gesagt (ich werde das morgen mal prüfen...).

Und um nun ganz sicher zu sein:

Zitat:

Zitat von Zacherl

...Da der Datentyp ja feststeht hat der Speicherbereich die Größe der Summe aller Elemente mal der Datentypgröße. (n * SizeOf(TDatenTyp))

Zitat:

Zitat von grenzgaenger

'n pointer ist einfach die effizienteste datengrösse, welche dein prozessor abarbeiten kann (integer), und ist einfach eine adresse im speicher... nicht mehr, nicht weniger.

Steht bei einem String/Integer/Record/*was auch immer* nun nur die Adresse im dynamischen Array oder der Wert (und ist das bei einem statsichen anders)?

[3_of_8]

Zitat:

Steht bei einem String/Integer/Record/*was auch immer* nun nur die Adresse im dynamischen Array oder der Wert (und ist das bei einem statsichen anders)?

String: Ja
Integer: Nein
Record: Nein
*was auch immer*: Wenn es ein String mit variabler Länge, eine Klasse oder ein dynamisches Array ist. Oder anders gesagt: Ein Datentyp, der irgendwie eine Finalisation benötigt, wenn ich mich nicht recht irre. Und bei statischen ist das auch nicht anders. Genaugenommen ist es nicht mal bei einer normalen Variable anders.

[Mr_G]

Wunderbar...
Dann ist die Struktur eines dynamsiches Arrays also genau die gleiche wie die eines statischen Arrays und der einzige Unterschied liegt darin, dass die Speicherallokation dynamisch zur Laufzeit stattfindet (wobei aber auch immer ein zusammenhängender Speicherbereich genutzt wird)?

P.S.: Sorry das ich mich hier andauernd rückversichere, aber ich habe meinen Lehrer komplett gegenteilig verstanden...

[grenzgaenger]

ja richtig, es wird immer ein ausreichender speicherbereich verwendet, sofern du ausreichend speicher hast. im anderen fall bekommst du 'n out of memory error.

[Khabarakh]

Zitat:

Zitat von 3_of_8

Dass ein Array in Delphi eine verkettete Liste ist, ist eine Aussage, für die man einen Infolehrer erschießen sollte. Ich kenne keine Sprache, in der das so ist.

Könnte man doch quasi als Definition für Arrays hernehmen ;) . In funktionalen Sprachen wirst du als grundlegenden Listentyp dagegen eine verlinkte Liste finden. Arrays sind immutable eben nicht sehr hilfreich.

Zitat:

Zitat von 3_of_8

Record: Ja

Nein :shock: !
Das ist doch der einzige Vorteil gegenüber Klassen: Records sind Wertetypen.

Also nochmal:

• Value Types:
  Primitive Typen
  Statische Arrays
  Records
  (object)
• Reference Types:
  Klassen (, Interfaces)
  Dynamische Arrays
  String (mit einigen Value-Type-Merkmalen)

[sirius]

Zitat:

Zitat von Mr_G

Dann ist die Struktur eines dynamsiches Arrays also genau die gleiche wie die eines statischen Arrays...

Jein.
Ja - Die Struktur ist dieselbe. Dein Array fängt irgendwo im speicher bei Adresse X an und jedes weitere Element N liegt bei X+N*sizeof(ArrayElement)

Der Unterschied liegt darin, dass beim Statischen Array deine Variable direkt den Wert X hat, beim dynamischen Array hast du einen Zeiger auf X.


(Ich hoffe ich habe jetzt nicht wieder verwirrt.)

[Mr_G]

Zitat:

Zitat von sirius

Der Unterschied liegt darin, dass beim Statischen Array deine Variable direkt den Wert X hat, beim dynamischen Array hast du einen Zeiger auf X.

Und das ist so weil das dynamsiche Array evtl. mal seine Position wechselt um bei einer Größenveränderung weiterhin in einem zusammenhängenden Speicherbereich zu stehen und dann der Zeiger einfach(er) umgebogen werden kann?

[DeddyH]

Auch, und weil die Größe eben dynamisch ist, das ist ja nur über Zeiger zu realisieren.

[grenzgaenger]

Zitat:

Zitat von Mr_G

Und das ist so weil das dynamsiche Array evtl. mal seine Position wechselt um bei einer Größenveränderung weiterhin in einem zusammenhängenden Speicherbereich zu stehen und dann der Zeiger einfach(er) umgebogen werden kann?

du kannst keinen zeiger umbiegen, sondern, er wird dir, bei ausreichenden speicher vorausgesetzt, umgebogen. das heisst, z.b. du darfst keine zeiger auf zeiger oder absolut zeiger verwenden um deine daten zu adressieren, sondern musst sie dir, auf der basis des gerade gültigen base-pointers jeweils neu berechnen.

wie das ansatzweise funktioniert, hat dir sirius kurz aufgezeigt. wobei nicht immer die grösse auch die grösse ist... da z.t. die zeiger wiederum auf eigene daten und/oder objekte zeigen können. aber das wollt ich ich meinen ersten post gar nicht erwähnen, um keine verwirrung zu stiften.

[3_of_8]

Zitat:

Zitat von Khabarakh

Zitat:

Zitat von 3_of_8

Record: Ja

Nein :shock: !
Das ist doch der einzige Vorteil gegenüber Klassen: Records sind Wertetypen.

Hoppala, hab ich da ernsthaft "ja" geschrieben? Das war in Versehen, ich ändere das gleich...

[Mr_G]

So, Lehrer interviewt und folgendes rausbekommen:
Wird ein dynamisches Array erstellt so wird der Speicher nach dem hier schon beschriebenen Muster alloziert. Wird das Array nun jedoch erweitert so wird lediglich ein "neuer" Speicherblock für die Erweiterung reserviert und am Ende des ersten Speicherblocks findet sich ein Zeiger auf den nächsten. Zur Indexberechnung wird dann zusätzlich eine "Tabelle" herangezogen, die den Startindex und die dazugehörige Adresse des Bereichs enthält. Diese Art der Verknüpfung ähnelt der verketteten Liste und hätte theoretisch den Vorteil, das keine riesigen Datenmengen durch den Speicher geschoben werden müssen.
Ich hab mal die kleine schematische Darstellung dieser Erklärung angehängt.
Was nun Delphi letztendlich aus dem dynamischen Array macht konnte mir mein Lehrer nicht mit Gewissheit sagen (evtl. könnte sich da im Laufe der Versionen was an der Implementierung verändert haben) aber ich finde das Prinzip schon einleuchtend. In wie weit hat denn nun wer Recht?

[sirius]

Wir haben natürlich Recht :mrgreen:

In Delphi ist es immer so, dass ein Array zusammenhängt. Dazu muss es, wenn es verlängert wird ggf. umkopiert werden.

[Medium]

Jub, Delphi kopiert um. Wäre das nicht so, könnte man Indizierung via Pointerarithmetik auch vergessen, und gelegentlich ist das auch heutzutage noch eine schön performante Alternative. Es mag sein, dass manche andere Sprachen diese Form von Fragmentierung eines dyn. Arrays betreiben, Delphi macht es allerdings definitiv nicht.

Spaßig ist in Delphi auch die mitgelieferte TList. Der Name suggeriert eine Linked-List, aber hinter TList steckt wieder nichts anderes als ein dyn. Array (of Pointer in diesem Fall). TList verwaltet lediglich das Wachsen/Schrumpfen des Arrays automatisch, und bietet ein ähnliches Interface wie eine doppelt verkettete Liste. Das hat seine Vor- aber auch Nachteile. Eine Liste im allgemeinen Sinne ist es jedoch nicht.
Hier gilt also: Im Spezialfall Delphi stimmt die Aussage, dass ein TList auf einem dyn. Array basiert - allgemein ist eigentlich eine Menge von Objekten gemeint, von denen jedes einen Verweis auf seinen Nachfolger (und ggf. Vorgänger) besitzt, und sonst keine Organisation in Arrays o.ä. passiert.