Halbdynamisches Array - verbessert die Performance von Größenänderungen erheblich

Ausgehend von dieser Diskussion: >>Performanceanalyse der neuen Datenstruktur "Map"<< habe ich mir Gedanken gemacht, wie man die Folgen eines ReDim minimieren kann.

Arrays verbrauchen in der Regel exakt so viel Speicher, wie Elemente in diesem enthalten sind.
Da diese Elemente immer direkt hintereinander stehen, führt dies zu Problemen wenn man Elemente hinzufügen möchte.
Es muss erst ein größerer Speicher reserviert werden, welcher Platz für das neue Array bietet und dann müssen alle Inhalte vom alten in das neue Array kopiert werden.
Diese Aufgabe übernimmt ReDim. Je größer so ein Array wird umso länger dauert dann jedes ReDim.
Ein klassisches Array ist also denkbar ungeeignet wenn man Elemente dynamisch hinzufügen möchte.
Zwar gibt es alternative Datenstrukturen wie ArrayLists. Diese haben zudem den Vorteil ganz fix neue Elemente innerhalb des Arrays einzufügen. Aber der Direktzugriff auf zufällige Elemente ist bei diesen deutlich langsamer.

Eine Idee die Folgen von andauerndem ReDim zu minimieren ist folgender:
Wenn ein Element hinzukommt dann wird die Größe des Arrays nicht um 1 erhöht sondern gleich verdoppelt wenn kein Platz mehr im Array vorhanden ist. Damit hat man dann noch Luft für weitere kommende Elemente.
Auf diesem Weg spart man sich einige ReDim ein. Analog verhält sich das Ganze beim Entfernen von Elementen.

Folgendes ignorieren - Funktionen wurden zu einer ausgewachsenen UDF ausgebaut: >>DynArray-UDF<<

Hierzu habe ich mal eine UDF erstellt (liegt im Anhang) welche folgende Funktionen beinhaltet:

_DynArrayPush         - neuen Wert ans Ende anhängen
_DynArrayPop          - letzten Wert zurückgeben und aus dem Array entfernen
_DynArrayInsert       - einen oder mehrere Werte innerhalb des Arrays einfügen
_DynArrayDelete       - einen oder mehrere Werte innerhalb des Arrays entfernen
_DynArraySearch       - Werte in einem unsortierten Array finden
_DynArrayBinarySearch - Werte in einem sortierten Array finden
_DynArraySort         - Array sortieren
_DynArrayMap          - eine beliebige Funktion auf alle Elemente des Arrays anwenden

Ein Beispiel zur Verwendung wäre folgendes:

Fassen wir mal die Vor-und Nachteile zusammen:

Vorteile:

• Deutlich gesteigerte Performance beim Hinzufügen von Elementen.

Nachteile:

• Doppelter Speicherverbrauch im Worst-Case
• Unstetiger Zeitbedarf für jedes Hinzufügen
  
• Zwang zur Notation der Elementanzahl im ersten Element

Was bringt nun aber _DynArrayPush() im Vergleich zu _ArrayAdd() im Endeffekt wirklich?

Hierzu kann man bei sich einfach mal folgendes Skript ausführen welches den Zeitbedarf beim dynamischen Hinzufügen von 1000 Elementen vergleicht:

Meine Ergebnisse hierbei waren folgende:

_DynArrayPush(): 	   10.1 ms
    _ArrayAdd(): 	  222.6 ms

Dieser Zeitvorteil steigt exponentiell mit der Elementanzahl

Zitat von BugFix

Das läßt sich umgehen, mit einer Statischen Variable in deiner Arrayfunktion. Ich würde ein Static Array einbinden und als zusätzlichen Parameter einen Index, damit die Funktion für mehrere Array gleichzeitig genutzt werden kann. Im Static Array am übergebenen Index den Zähler für das jeweilige zu ändernde Array eintragen.

Was ist die "Arrayfunktion" bei mir?
_DynArrayPush? Diese wird ja erst aufgerufen wenn das Array schon erstellt habe.
Und wenn ich das Array dann nicht mehr benötige und lösche? Vielleicht sogar mit einer Funktion _ArrayDelete(). Wie lösche ich dann dessen Eintrag in der statischen Variable?

Ok dann hätte man die Push-Funktion.
Pop geht dann aber nicht mehr da diese ja keinen Zugriff auf $aCounter in _DynArrayPush() hat.

Sicherlich geht es so aber es wird dann schon ziemlich unintuitiv. (Man muss sich den Index merken, dieser muss sicher vor Doppelbelegung sein, Löschen mit einer Push-Funktion... ;-))
Aber ja du hast Recht: prinzipiell geht es.

Hab das ganze mal zu einer UDF erweitert (siehe Startpost).