Ich habe ein dynamisch zugewiesenes 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.
Mein Code sieht momentan so aus:
%Vor%(Der echte Code ist eine Methode einer Klasse mit FSortedList und FCount als Felder.)
Die Verwendung einer temporären Liste und die Verwendung von Move anstatt einer for-Schleife zum Verschieben der Daten haben die Performance bereits erheblich verbessert, da das Array nicht zweimal kopiert werden muss, wenn es vergrößert werden muss (einmal in SetLength auf dem vorhandenen Array) Zeit mit Move).
Aber der schlimmste Fall Insert (SomeValue, 0) verschiebt immer noch alle vorhandenen Werte.
Bisher habe ich nach einem Offset am Anfang des Arrays gesucht, anstatt jedes Mal, wenn ein neuer Wert an der Front eingefügt wird, alle vorhandenen Werte zu verschieben, kann ich das nur tun, wenn der Offset erreicht ist 0. ZB:
%Vor%(Dieser Code ist nicht getestet und wahrscheinlich fehlerhaft) Dies kann natürlich erweitert werden, um zu überprüfen, ob der Einfügepunkt näher am Anfang oder am Ende ist und je nachdem, ob sich der erste oder der letzte Wert um eine Position bewegt, so dass im Durchschnitt nur 1/4 der Einträge verschoben werden müssen eher als 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 für einige Sortier- und Indexierungscodes von zentraler Bedeutung, die auf Arrays unterschiedlicher Größe, von einigen Dutzend Einträgen bis zu den oben genannten Millionen von Einträgen, funktionieren.
Momentan läuft das Programm ungefähr 2 Stunden (vor meinen Optimierungen waren es fast 5 Stunden) und ich weiß bereits, dass die Anzahl der Einträge im Array sich mindestens verdoppeln wird. Da die Insert-Leistung 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 hätte gerne Vorschläge, wie Sie die Performance optimieren können. Speicherverbrauch ist derzeit kein großes Problem, aber Laufzeit ist definitiv.
(Dies ist Delphi 2007, aber das sollte keinen großen Unterschied machen, es sei denn, neuere Delphi-Versionen haben bereits eine optimierte Bibliothek für das oben genannte. Classes.TList ist nicht optimiert.)
Edit1: Habe gerade die Sparse-Array-Implementierung gefunden, die ich oben erwähnt habe: 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 ihre RecNo wird in sortierter Reihenfolge in das Array eingefügt.
Unmittelbar nach dem Betrachten Ihrer Prozedur bemerkte ich einige Fehler. Um den Fortschritt zu sehen, habe ich zuerst die Geschwindigkeit Ihrer bestehenden Prozedur im Worst-Case-Szenario gemessen (indem Sie die Nummer immer auf 0 setzen).
%Vor%Messung: n = 500000 47,6 ms
A) Einfachheit
Ich habe einige unnötige Zeilen aus Ihrer Prozedur gelöscht (OldList ist völlig unnötig, SetLength behält Speicher bei).
Verbesserung A:
%Vor%Geschwindigkeitsverstärkung 6% (44,8 ms)
B) Alles zählt
%Vor%Verbesserung B:
%Vor%Geschwindigkeitsverstärkung 1% (44,3 ms).
Hinweis: Statt Inc by 100000 können Sie einen progressiven Algorithmus implementieren.
C) Engpass
Wenn wir uns jetzt die Prozedur ansehen, ist nichts mehr übrig, nur eine Menge Speicherbewegungen. Wenn wir den Algorithmus nicht ändern können, müssen wir die Speicherbewegung verbessern.
Es gab tatsächlich fastmove challenge (fastcode.sourceforge.net)
Ich habe eine Zip vorbereitet, mit genau den Dateien, die du brauchst (3 Dateien, Quellcode). Link & gt; & gt; & gt; Ссылка
Geschwindigkeitsverstärkung an meinem Gerät fast 50% (hängt von der verwendeten CPU ab).
Originalverfahren
%Vor%Verbessert, ohne Fastmove (-7%)
%Vor%Verbessert, mit fastmove (-46%)
%Vor%Letzte Kommentare:
%Vor%Wie gesagt, du kannst progressive FC-Kapazität erhöhen. Dies ist eine klassische Grow-Implementierung (fügen Sie einfach weitere hinzu, falls erforderlich, oder ändern Sie 100000 in einen passenderen Wert).
D) Update 2: Array als ^ TArray
%Vor%Geschwindigkeitsverstärkung von Schritt C) Keine!
Konslusion: FastMove oder Algorithmus ändern, "physisches" Limit der Speicherbewegungsgeschwindigkeit ist erreicht!
Ich benutze Delphi XE3 und in System.pas, Zeile 5307:
%Vor%In Delphi gibt es bereits einige Fastcode-Routinen, aber auch diejenigen, die direkt von ihrer Seite heruntergeladen wurden (oder von Link oben), machten die größte Differenz, fast 50% (seltsam).
Nicht ein Spielverderber zu sein, aber die Lösung ist schon in der Bearbeitung meiner Frage:
Nach dem Wechsel von einem Array zu TurboPowers StColl < Die Leistung verschlechtert sich nicht mehr mit großen Arrays und ist ziemlich schnell zu booten. Die Laufzeit ist von 2 Stunden auf weniger als 1/2 Stunde gesunken. Die Änderung war wirklich einfach. Ich wünschte, ich hätte mich viel früher an diese Bibliothek erinnert.
Ich benötigte die folgenden Dateien aus dem SourceForge-Repository (ich wollte nicht die gesamte Bibliothek herunterladen):
Eigentlich bin ich überrascht, dass es nicht mehr Interdependenzen gab. Die TurboPower-Jungs kannten ihr Handwerk. Ich frage mich, was sie heute tun, immer noch Spielautomaten für Casinos zu programmieren?
Tags und Links arrays delphi delphi-2007 dynamic-arrays