DynamischesArray
Aus Fgbdev
Es ist ja wohl bekannt, daß bei vielen Änderungen der Arraygröße eine Menge Zeit draufgeht.
Dagegen gibt es eigentlich nur ein Mittel > die Anzahl der Änderungen muß verringert werden, so daß nicht gleich bei jeder kleinen Änderung der gesamte Arrayinhalt hin- und herkopiert wird.
Als Erstes könnte man es mal mit einem anderem Memory-Manager versuchen (z.B. FastMM), allerdings ist es da nicht möglich das Verhalten an eigene Bedürfnisse anzupassen.
Also wäre es wohl nicht schlecht, wenn selber das Verhalten geändert wird.
1.) Verwendete und tatsächliche Größe unabhängig verwalten: Wozu noch eine extra Variable für den verwendeten Bereich nötig wäre.
// Definition Var MyArray: Array of XXX; MyArray_Length: Integer; // SetLength(MyArray, NewLength); MyArray_Length := NewLength; SetLength(MyArray, (NewLength + $1FFF) and not $1FFF); // Length(MyArray) MyArray_Length // High(MyArray) MyArray_Length - 1 // MyArray[Index] MyArray[Index]
2.) Verwendete Größe mit Array speichern: z.B. am Ende/nach den Array-Daten Keine weitere Variable nötig, somit wären die Funktionen auf mehrere Arrays anwendbar.
// Definition
Type TMyArray = Array of XXX;
Var MyArray: TMyArray;
Function Length_(Const A: TMyArray): Integer;
Begin
If A = nil Then Result := 0
Else Result := PInteger(@A[High(A)])^;
End;
Function High_(Const A: TMyArray): Integer;
Begin
Result := Length_(A) - 1;
End;
Procedure SetLength_(Var A: TMyArray; i: Integer);
Begin
If A <> nil Then PInteger(@A[High(A)])^ := 0;
If i > 0 Then Begin
SetLength(A, ((i + $1FFF) and not $1FFF) + 1);
PInteger(@A[High(A)])^ := i;
End Else A := nil;
End;
// SetLength(MyArray, NewLength);
SetLength_(MyArray, NewLength);
// Length(MyArray)
Length_(MyArray)
// High(MyArray)
High_(MyArray)
// MyArray[Index]
MyArray[Index]
Dieses Beispiel ist nur für SizeOf(XXX) >= 4, wenn SizeOf(XXX) kleiner als SizeOf(Integer) ist, dann muß natürlich mehr als nur ein Feld für die zu speichernde Größenangabe verwendet werden.
Function Length_(Const A: TMyArray): Integer;
Begin
If A = nil Then Result := 0
Else Result := PInteger(@A[Length(A) - 2{4}])^;
End;
Procedure SetLength_(Var A: TMyArray; i: Integer);
Begin
If A <> nil Then PInteger(@A[Length(A) - 2{4}])^ := 0;
If i > 0 Then Begin
SetLength(A, ((i + $1FFF) and not $1FFF) + 2{4});
PInteger(@A[Length(A) - 2{4}])^ := i;
End Else A := nil;
End;
// 2 für SizeOf(XXX)=2, oder SizeOf(XXX)=3
// 4 für SizeOf(XXX)=1
3.) Größenangabe direkt im Array ändern: Vorteil zum vorherigen (2) Vorgehen wäre, daß hier nur SetLength geändert werden muß.
// Definition
Type TMyArray = Array of XXX;
Var MyArray: TMyArray;
Procedure SetLength_(Var A: TMyArray; i: Integer);
Begin
If A <> nil Then PInteger(Integer(A) - SizeOf(Integer))^ :=
(PInteger(Integer(A) - SizeOf(Integer))^ + $1FFF) and not $1FFF;
SetLength(A, (i + $1FFF) and not $1FFF);
If A <> nil Then PInteger(Integer(A) - SizeOf(Integer))^ := i;
End;
// SetLength(MyArray, NewLength);
SetLength_(MyArray, NewLength);
// Length(MyArray)
Length(MyArray)
// High(MyArray)
High(MyArray)
// MyArray[Index]
MyArray[Index]
4.) Wer nicht direct im Array "rumpfuschen" möchte, könnte es auch mit einer Klasse versuchen. Allerdings wird hierfür dann zusätzlich noch der Constructor und Destructor benötigt.
Type TMyArrayClass = Class
Private
A: Array of XXX;
ALen: Integer;
Function GetField(i: Integer): XXX;
Procedure SetField(i: Integer; Value: XXX);
Public
Procedure SetLen(i: Integer);
Function Len: Integer;
Property LenX: Integer Read Len Write SetLen;
Property Field[i: Integer]: XXX Read GetField Write SetField; Default;
End;
Function TMyArrayClass.GetField(i: Integer): XXX;
Begin
Result := A[i];
End;
Procedure TMyArrayClass.SetField(i: Integer; Value: XXX);
Begin
A[i] := Value;
End;
Procedure TMyArrayClass.SetLen(i: Integer);
Begin
SetLength(A, (i + $1FFF) and not $1FFF);
ALen := i;
End;
Function TMyArrayClass.Len: Integer;
Begin
Result := ALen;
End;
Var MyArray: TMyArrayClass;
// Initialisieren
MyArray := TMyArrayClass.Create;
// SetLength(MyArray, NewLength);
MyArray.SetLen(NewLength);
{oder} MyArray.LenX := NewLength;
// Length(MyArray)
MyArray.Len
{oder} MyArray.LenX
// High(MyArray)
MyArray.High
// MyArray[Index]
MyArray[Index]
{oder} MyArray.Field[Index]
// Finalisieren
MyArray.Free;
Fazit: Aus OOP-Sicht wäre 4. zu bevorzugen, auch wenn da vieles zu beachten und zu verändern ist.
Bei 1. ist zwar guz zu sehn was gemacht wird, allerdings mu da jedes SetLength, Length und High geändert werden.
2. ist im Grunde nicht zu empfehlen, da dort das Array besser mit SelLength_(MyArray, 0) freigegeben werden sollte, vorallem wenn im Typ dynamische Stukturen enthalten sind, welche von FinalizeArray behandelt werden (z.B. Strings), da es sonst Probleme mit dem Typ-Fremden Integer (der Längenangabe am Ende) geben könnte. Schließlich wird aus gutem Grund die Größenangabe aus dem Array gelöscht, bevor die Größe geändert wird.
If A <> nil Then PInteger(@A[High(A)])^ := 0;
Ich selber verwende gerne 3., da hierbei nur SetLength ersetzt werden muß und alles andere unverändert bleibt. Außerdem kann dieses Array überall so verwendet werden, als wäre es ein ganz normalles Array. Manchmal auch 1., da es ja im Grunde genau das Selbe wie 2. ist, nur halt etwas schneller.
Schrittweite: In den Beispielen wird die Arraygröße jeweils in Schritten von 1024 geändert.
Es sind natürlich auch andere Werte möglich, aber im allgemeinen sind 2er-Potenzen idealer, da dort binär (mit AND) gerechnet werden kann, wärend sonst mathematische Rechnungen (mit MOD und *) nötig sind.
Also einmal ein "schnelles" AND (das NOT wird mit einkopiliert), oder zweimal "langsame" DIV/MUL.
// binär (nur bei 2er-Potenzen)
(i + (AllocSize - 1)) and not (AllocSize - 1)
{=} (i + $*****) and not $*****
// matematisch
((i + (AllocSize - 1)) div AllocSize) * AllocSize
