was passiert bei ReDim() im Hintergrund?

[jogo]

moin zusammen,
beim Einlesen der Verzeichnisstrukturen auf mobilen Datenträgern schreibe ich die gefundenen Verzeichnispfade in ein Array.
Da ich ja vorher nicht weiß, wieviel Verzeichnisse ich finde, erweitere ich bei jeden neuen Verzeichnisfund mein Array mit ReDim() um ein weiteres Element, was auch funktioniert. Allerdings kommen so ggf. eine Menge ReDim's zusammen.

Was mich rein aus Neugier interessiert ist, was bei einem ReDim im Hintergrund passiert. Also im Bezug auf CPU- und Speicherauslastung.
Wird da wirklich einfach nur ein Element kurz und knackig "angeklebt" oder wird das neue Array erst aufgebaut und dann die Daten des bestehenden Arrays dort rein kopiert? Hat da Jemand etwas Hintergrundwissen darüber?

Ansonsten könnte ich das ja auch anders lösen - zB. erst die Verzeichnisse mit Pipe getrennt in einem String schreiben und zum Schluss das Array punktgenau dimmen und einmalig füllen. Oder Listen oder Maps nutzen...
Die Frage ist, was ist jetzt besser zwecks Ressourcen?

[mk-soft]

Ein Array hierfür zu nehmen ist nicht vorteilhaft.

Ein Array ist immer ein zusammen hängender Speicherbereich. Somit muss, wenn hinter dem Speicherbereich kein platz ist, ein neuer Speicherbereich angefordert werden und die vorhandenen Daten jedesmal umkopiert werden. Auch wenn es sich um ein Array of String handelt und somit intern ein Array of Pointer to String.

Eine LinkedList ist hier besser geeignet.

Was die Performance mit Array verbessert ist es das Array Blockweise zu vergrößern. Zum Beispiel wenn das Array zu klein ist um 100 vergrößern und mit einer weitern variable die vorhandene Anzahl der Eintragungen mitschreiben.

[jogo]

alles klar - sowas in der Richtung hab ich mir auch schon gedacht.
Werde mir mal das Handling mit LinkedList oder vllt. auch Maps für diesen Zweck anschauen.
Gezielte Zugriffe auf einzelne Einträge auf das gefüllte Array finden nicht statt. Ich verarbeite das gefüllte Array anschließend in einer Schleife.
Obwohl - das Array blockweise um 100-150 erweitern, ist auch verlockend. Ich müßte mal schauen, wieviel Einträge in der Praxis so zusammen kommen. Die Anfangsgröße/Blockgröße könnte ich ja dann einstellbar machen...

[jogo]

...Somit muss, wenn hinter dem Speicherbereich kein platz ist, ein neuer Speicherbereich angefordert werden und die vorhandenen Daten jedesmal umkopiert werden. Auch wenn es sich um ein Array of String handelt und somit intern ein Array of Pointer to String.

Also ist das so, dass bei einem Stringarray auf Grund der unbekannten Stringlänge die Stringelemente verstreut im Speicher platziert werden und das eigentliche zusammenhängende Array quasi nur die Stringadressen beeinhaltet?
Heißt also, dass bei ReDim() die Strings da bleiben, wo sie sind, jedoch das Array mit den Stringadressen umkopiert wird. Also wie es bei einem Integer- oder Longarray passieren würde, sozusagen.

[NicTheQuick]

Also ist das so, dass bei einem Stringarray auf Grund der unbekannten Stringlänge die Stringelemente verstreut im Speicher platziert werden und das eigentliche zusammenhängende Array quasi nur die Stringadressen beeinhaltet?
Heißt also, dass bei ReDim() die Strings da bleiben, wo sie sind, jedoch das Array mit den Stringadressen umkopiert wird. Also wie es bei einem Integer- oder Longarray passieren würde, sozusagen.

Das ist korrekt.

Bezüglich Arrays vergrößern: Um ein Array mit dynamischer Länge zu realisieren, verdoppelt man idealerweise die Größe eines Arrays immer dann, wenn es gerade voll wird und halbiert die Größe, wenn es nur noch zu einem Viertel gefüllt ist. Das ist wesentlich effizienter als blockweise 100 Elemente oder sowas anzuhängen.
Falls du des englischen mächtig bist, könntest du dazu das hier lesen: https://cs.stackexchange.com/questions/ ... -amortized
Oder noch ausführlicher und in Deutsch habe ich gerade das hier gefunden: https://de.wikibrief.org/wiki/Dynamic_array

Aber wenn es dir im Endeffekt gar nicht darum geht per Index auf deine Daten zuzugreifen, dann sind LinkedLists meiner Meinung nach sinnvoller. Die Implementierung in Purebasic ist auch sehr gut gemacht und schnell. Außerdem bietet die LinkedList ja noch andere Vorteile wie z.B. das Löschen beliebiger Elemente, ohne dass die nachfolgenden Elemente nachrücken müssen.

[jogo]

ahh - ok. Danke für die Aufklärung. Diese technischen Hintergrundinfos sind für meine Entscheidungsfindung, wie und wann ich welche Arrays einsetze sehr hilfreich.
Für diesen einen speziellen Fall hab ich mich jetzt für LinkedLists entschieden - läuft gut

An einer anderen Stelle habe ich eine ähnliche Situation, jedoch brauche ich dort auch den direkten Zugriff.
Da macht die Verdopplung dann wohl Sinn..

Oder: Ich dimme das Array Anfangs so großzügig, daß ein Überlauf ausgeschlossen ist und wenn es endgültig fertig ist, kürze ich es punktgenau ein. Dies hätte dann den Vorteil, daß das Array nicht umkopiert werden muß, sondern der Array-Ende Zeiger einfach verkleinert wird. Allerdings "leihe" ich mir in der Aufbauphase temporär etwas mehr RAM (0.5-3 Sekunden). Wäre aber aus meiner Sicht das kleinste Übel, da ich nichts an Performance opfern muß.

[NicTheQuick]

Wenn du im Vornherein einschätzen kannst, was dein oberes Limit ist, dann kannst du das natürlich so machen. Ansonsten führt auch die Verdoppelungsstrategie zu einer amortisierten konstanten Laufzeit, ist halt nur ein klein wenig komplizierter zu implementieren.

[Benubi]

Es ist eigentlich immer besser Linked Lists zu benutzen wenn Elemente dynamisch hinzugefügt werden sollen. Ein Array hat den Vorteil, daß die Elemente-Zeiger direkt über den Array Index berechnet werden. PB pre-alloziert um die 500 Elemente für jede Liste in einem "Array" bzw. Block, sobald ein erstes Element eingefügt wird; so geht die Erzeugung eines einzelnen Listen Elements schneller als wenn jedes einzelne per AllocateMemory() erzeugt würde. Bei Listen ist der direkte Zugriff auf Elemente per Index aber nicht möglich, es wird dann die Liste durchgegangen was je nach Länge dauern kann.

Ich benutze einen Faktor 1,5 anstatt einer Verdoppellung bei ReDim Operationen sowie bei Dateien die im Speicher bearbeitet werden. Und beim Schrumpfen nehme ich 0,66 an Stelle von 0,5. Das macht kaum einen Unterschied in der Geschwindigkeit und ist etwas Speicher-ökonomischer.

[mk-soft]

Da gibt es viele Möglichkeiten / Spielereien mit LinkedList und Array mit Pointer auf die LinkedList Daten ...

[juergenkulow]

Code: Alles auswählen

; Ändert sich Feldaddresse durch ReDim immer? 
Dim Feld(1)
i=2 
While i<10000000
  ReDim Feld(i)
  Debug RSet(Str(i),8)+": "+Hex(@Feld(0))
  If i<65536 
    i+i
  Else
    i+i/2
  EndIf 
Wend
;        i: Addresse von Feld(0) 
;        2: F236F8
;        4: F148B8
;        8: F148B8
;       16: F148B8
;       32: F148B8
;       64: F148B8
;      128: F148B8
;      256: F148B8
;      512: F148B8
;     1024: F148B8
;     2048: F148B8
;     4096: F148B8
;     8192: F24178
;    16384: F24178
;    32768: 7F5529950048
;    65536: 7F55298CF048
;    98304: 7F55298CF048
;   147456: 7F55297AE048
;   221184: 7F55297AE048
;   331776: 7F5529525048
;   497664: 7F5529525048
;   746496: 7F5528F72048
;  1119744: 7F5528F72048
;  1679616: 7F55282A1048
;  2519424: 7F55282A1048
;  3779136: 7F55265CB048
;  5668704: 7F55265CB048
;  8503056: 7F55224EB048