Ich habe ein dynamisch zugeordnetes Array von ganzen Zahlen, in die ich ganze Zahlen an beliebigen Positionen einfügen möchte. Viele ganze Zahlen wie in mehr als 2,5 Millionen.Wie kann ich effizient mehrere Einfügungen in ein Array behandeln?
derzeit Mein Code sieht wie folgt aus:
type
TIntegerArr = array of Integer;
var
FCount: Integer;
FSortedList: TIntegerArr;
procedure Insert(_Value: Integer; _InsertPos: integer);
var
OldList: TIntegerArr;
begin
OldList := FSortedList;
if Length(FSortedList) < FCount + 1 then begin
OldList := FSortedList;
FSortedList := nil;
SetLength(FSortedList, FCount + 100);
CopyMemory(@FSortedList[0], @OldList[0], SizeOf(Integer) * _InsertPos);
end;
MoveMemory(@FSortedList[_InsertPos + 1], @OldList[_InsertPos], SizeOf(Integer) * (FCount - _InsertPos));
FSortedList[_InsertPos] := _Value;
Inc(FCount);
end;
(Der eigentliche Code ist eine Methode einer Klasse, den FSortedList und FCount als Felder.) Eher
Mit einer temporären Liste und mit Verschieben als Eine for-Schleife zum Verschieben der Daten hat die Performance schon ziemlich verbessert, weil sie verhindert, dass das Array zweimal kopiert wird, wenn es wachsen muss (einmal in SetLength auf dem bestehenden Array und ein anderes Mal mit Move).
Aber der schlimmste Fall Insert (SomeValue, 0) verschiebt immer noch alle vorhandenen Werte.
Bisher dachte ich über die Einführung eines Offsets am Anfang des Arrays nach, anstatt jedes Mal, wenn ein neuer Wert an der Front eingefügt wird, alle vorhandenen Werte zu verschieben, könnte ich das nur beim Offset tun 0. zum Beispiel erreicht:
// simple case: inserting at Position 0:
if FOffset = 0 then begin
// [...] reallocate a new array as above
Move(@FSortedList[100], @OldList, SizeOf(Integer) * _InsertPos);
FOffset := 100;
end;
Dec(FOffset);
FSortedList[FOffset] := _NewValue;
(Dieser Code ist nicht getestet und wahrscheinlich Buggy) Dies natürlich erweitert werden kann, um zu überprüfen, ob der Einfügemarke näher am Anfang oder am Ende und in Abhängigkeit von dieser Bewegung entweder die ersten oder die letzten Werte um eine Position, so dass im Durchschnitt nur 1/4 der Einträge verschoben werden muss und nicht 1/2, wie es derzeit ist.
Eine andere Option wäre die Implementierung eines Sparse-Arrays. Ich erinnere mich, dass ich in den 1990er Jahren eine solche Implementierung in einer kommerziellen Bibliothek gesehen habe, aber ich kann mich nicht erinnern, welche es war (TurboPower?).
Dieses Verfahren ist von zentraler Bedeutung für einige Sortier- und Indexierungscodes, die auf Arrays unterschiedlicher Größe funktionieren, von einigen Dutzend Einträgen bis zu den oben genannten Millionen von Einträgen.
Derzeit läuft das Programm etwa 2 Stunden (vor meinen Optimierungen war es fast 5 Stunden) und ich weiß bereits, dass die Anzahl der Einträge im Array mindestens verdoppelt wird. Da die Insert-Performance immer schlechter wird, je größer das Array bereits ist, vermute ich, dass sich die Laufzeit bei doppelter Anzahl der Einträge mindestens vervierfacht.
Ich möchte einige Vorschläge, wie Sie die Leistung einstellen. Speicherverbrauch ist derzeit kein großes Problem, aber die Laufzeit ist definitiv.
(Dies ist Delphi 2007, aber das sollte nicht viel Unterschied machen, es sei denn neuere Delphi-Versionen bereits eine optimierte Bibliothek für die oben tun Classes.TList nicht optimiert ist..)
Edit1: fand gerade die spärliche Array-Implementierung Ich erwähnte oben: Es ist StColl von TurboPower SysTools.
Edit2: Ok, etwas Hintergrund: Mein Programm liest eine DBase-Tabelle mit aktuell 2,4 Millionen Einträgen und generiert aus diesen Einträgen mehrere neue Tabellen. Die neuen Tabellen sind normalisiert und werden indiziert, nachdem sie erstellt wurden (aus Leistungsgründen erzeuge ich die Indizes vor dem Einfügen der Daten nicht, vertraue mir, ich habe es zuerst versucht). Das Array ist das zentrale Codeelement, das eine interne Sortierung für die generierten Tabellen bereitstellt. Neue Datensätze werden nur an die Tabelle angehängt, aber ihr RecNo wird in sortierter Reihenfolge in das Array eingefügt.
Nach dem Umschalten von einem Array TurboPower's StColl die Leistung nicht verschlechtert länger mit großen Arrays und ist recht schnell zu booten:
See [ 'Verbesserter Geschnittene Array implementation'] (http://www.cromis.net/blog/2013/03/improved-sliced-array-implementation/) von [' @ Runner'] (http: // stackoverflow.com/users/118765/runner) wenn dies einen Input gibt, wie man das Sortieren besser macht. –
@LURD: Danke. Ich habe diesen Blogeintrag gelesen, als er es schrieb (der erste Kommentar auf dieser Seite gehört mir), hatte es aber schon vergessen. – dummzeuch
Erzähl uns mehr über Anwendungsfälle für dieses "einfügbares Array". Mögliche Lösungen hängen davon ab. – MBo