Optimierung der Object-pascal

Optimierung der Object-pascal

Optimierung der Object-pascal : Mehreren tausend Tipps, um Ihr Leben einfacher machen.

Eine Geschichte der Optimierung.

Optimierung von Object Pascal
Dieser Artikel untersucht die Optimierung Delphi Code basierend auf standard-Techniken, den Gegenstand des Programms und einen Fall von schier reines Glück vollständig zu verstehen. Eine Poker-Bibliothek wird benutzt, um diese Punkte zu illustrieren.
Dies ist eine Geschichte über eine einfache Poker-Bibliothek und Optimieren von Code in Delphi. Die Poker-Bibliothek begann als Turbo Pascal Projekt vor Jahren eine, die ich vorgehabt hatte, eine Zeitlang in Delphi konvertieren. Wie es der Zufall, Delphi 5 kam auf den Markt zuvor fand ich Zeit, um die Konvertierung zu machen.
Mein erster Schritt war, die Bibliothek als Objekt-orientiertes Projekt neu zu gestalten. Der ursprüngliche Code rein verfahrensrechtlichen gewesen. Im neuen Format enthält die Bibliothek drei Klassen für die Programmierung von Poker-Spiele. Dies sind seltsamerweise - eine Karte-Klasse, einer Klasse Deck und eine Hand-Klasse. Das Deck und die Hand sind Nachfahren der List-Klasse eine Karte. Die Bibliothek unterstützt Poker-Spiele, die Hände von fünf oder mehr Karten zu nutzen, hat Unterstützung für hohe und niedrige Variationen und unterstützt Wildcards. Es war diese letzte Funktion, die schwierigsten erwiesen. Ich landete Aufbau eine komplette Bibliothek mit keine Wildcard-Unterstützung und dies als Grundlage für die Wild-Card-Version verwendet.
Um die Bibliothek zu validieren, baute ich eine Reihe von neun Prüfanwendungen. Diese enthaltene Programme testen, die Schaffung und Mischen der Karten, gestatten Sie mir zu holen fünf Karten und bewerten als ein Pokerblatt, ein Programm, das behandelt und bewertet fünf Karten Hand alle standard-Typ, ein Programm, das für sieben Karten Hände gleich, ein video-Poker-Spiel und vier Benchmarks testen Sie die Geschwindigkeit der Bibliothek mit Wildcards und ohne hast.
Es dauerte ein paar Wochen, die Bibliothek zu bauen, und der Prozess verlief reibungslos. Ich konnte einen guten Teil der alten Pascal-Code verwenden. Dies erwies sich als gute und schlechte. Gut, denn es die Umwandlung entlang beschleunigt. Schlecht, weil ich einen kleinen Fehler gemacht, die ich später erklären werde. Das Projekt war in ein paar Wochen getestet und vollständig außer ein kleines Problem. Es war zu langsam, um von nutzen zu sein. So beginnt unser Abenteuer. Die Ergebnisse der ersten Speed-Trials sind in Tabelle 1 aufgeführt.

Tabelle 1. Wildcard-Bibliothek Benchmarks - sind die Zeiten in Sekunden
Delphi 5 auf einem 400 Mhz Pentium II mit 128 Megabyte RAM
Die Benchmark-Programme sind sehr einfach. Jedes Programm erstellt alle möglichen fünf-Karten-Hände in einem Kartenspiel. Es ruft dann die SetHighValues-Methode des Objekts Hand, wertet die Hand und eine hohe Bewertung und einen hohen Namen zurück. Die hohe Bewertung ist ein long Integer verwendet als Bitfeld. Die niedrigwertigen zwanzig Bits enthalten die Reihen der Karten in standard-Poker Reihenfolge. Die höherwertigen elf Bits enthalten den Hand-Typ. (Eine ausführlichere Erklärung, finden Sie die Bibliothek-Quelle, die steht zum Download bereit.) Dies ermöglicht ein Poker-Programm zum Vergleichen von zwei Händen durch ihre hohen Einschaltquoten vergleichen. Zum Beispiel:
Wenn Hand [1]. HiRating > Hand [2]. HiRating dann
Das Benchmark-Programm wird hohe Bewertung bestimmt den Typ der Hand und hält eine Anzahl auf alle standard-Typen und die Gesamtzahl der Hände. Dies dient als weitere Validierung der Bibliotheksroutinen. In einem standard-Deck von 52 Karten gibt es in 2.598.960 fünf-Karten-Händen, vier Royal Flushes, 5.108 Norm Flushs etc.. Wenn die Benchmark unterschiedliche Nummern meldet dann wissen wir, dass es ein Problem mit der Bewertung-Routinen.
Wie Sie sehen können, führt jeder Platzhalter verwendet, etwa einer 80 % igen Rückgang Geschwindigkeit. Ich habe nicht die Mühe die Deuces Wild-Benchmark ausgeführt. Die zwei Joker-Benchmark dauerte etwa eine Stunde und ein Viertel in Anspruch. Die Deuces Wild-Benchmark hätte eine geschätzte 25 Stunden in Anspruch genommen.
So dass es schneller
Der erste Schritt ist, was sind die Problembereiche zu finden. Die Benchmarks selbst deuten auf einen Bereich arbeiten muss. Die Methode verwendet, um Wild Card Hände beträgt das Wildcard in alle möglichen Ersatz Karten umzuwandeln und dann die eigentliche Bewertung-Routinen aufrufen zu bewerten. Es ist klar, dass dies einige Arbeit verwenden konnte.
Um andere Bereiche für Verbesserungen zu finden, stieg ich aus meinen treuen Codeprofiler. Ich benutze die Stoppuhr, Teil des Sleuth QA von TurboPower. Es gibt andere verfügbar und jeder Programmierer sollte man haben. Ich lief die keine Wildcards Benchmark unter dem Profiler und wartete auf den Bericht. Eigentlich ging ich zu Bett. Da die Bibliothek ein klein wenig langsamer ist, lief ich das Profil in der Nacht. Am nächsten Morgen waren 273 Millionen Funktionsaufrufe später die Ergebnisse. Siehe Tabelle 2.

Tabelle 2. Zehn am meisten Routinen aufgerufen, in der Poker-Bibliothek.
Stoppuhr gibt eine Menge Informationen. Es gibt Timings auf jede Routine aufgerufen und der Prozentsatz der Summe, die, der dies gleichkommt. In diesem Fall einige der wichtigsten Informationen ist in der obigen Tabelle.
Das erste, was der Note, ist, dass es fast 195 Millionen Aufrufe der GetCard-Methode. Dies dürfte. Jede Hand, die von der SetHighValues-Methode ausgewertet wird 25 Aufrufe von GetCard generiert. Jeder Aufruf von CopyCardFromDeck erzeugt zehn weitere. Die Summe ist korrekt. So ist die Summe für CopyCardFromDeck. Darüber hinaus zeigt ein kurzer Blick auf die Angebote gibt es nicht viel, die entweder dieser Routinen geändert werden können. Sie sind im Wesentlichen nur Zuweisungsanweisungen.
Es ist Zeit zu denken, wie ein Pokerspieler anstelle eines Programmierers. Es gibt 2.598.960 möglichen fünf-Karten-Hände in einen Standardsatz von Karten. Vierzig dieser Straight Flushes und vier von der Straight Flushes sind Royal Flushes. Es gibt 5.108 Straights und 10.200 Flushes in ein standard-Deck. Die Zahl der Anrufe, IsStraight, IsFlush und vor allem IsStraightFlush sind Weg aus der Reihe. Jede Hand wird drei Mal getestet, um festzustellen, ob es eine gerade ist. (Eigentlich 2.996336996336996336996336996337 Zeiten, aber warum Haarspalterei?)
SetHiValNoWC ist das 'Arbeitspferd' der Poker-Bibliothek für die Bewertung der hoher Händen. Es testet jede Hand, die an es übergeben und findet welche Art es ist. Sie formatiert die Hand, dann gibt es eine numerische Bewertung und einen passenden Namen. Dazu ruft es die IsStraight-Funktion, und einige andere. Sie tut dies in einer schönen sichere Weise die Vergleiche von der höchsten bis zur niedrigsten bestellt. Dort liegt eines unserer Probleme.
Jede Hand wird getestet, um festzustellen, ob ist fünf einer Art. Wenn es sich handelt, sind wir fertig. Wenn nicht es wird getestet, um festzustellen, ob es ein Royal Flush ist. Das bedeutet, zu testen, wenn es ein Straight, einen Flush, Straight Flush und schließlich eine Royal ist. Wenn sie ein Royal Flush ist, überprüft es ist dies eine natürliche Royal oder Wildcards verwendet. In jedem Fall sind wir fertig. Wenn es keine Royal ist, wurde es dann getestet, um festzustellen, ob es ein Straight Flush ist, so dass der Test für geraden wiederholt wird. Sehen Sie das Problem? Dies ist eine schlechte Algorithmus.
Optimierung 1
Unsere erste Verbesserung ist die Reihenfolge der Tests ändern. Diesmal, anstatt es des sicheren Weg, versuche ich es die clevere Art zu tun. Es gibt wahrscheinlich viele Lösungen. Wie viele Arten können zehn Prüfungen werden angeordnet? Autsch! Wieder ist es Zeit, auf mein Poker-Hut setzen.
Pokerhände können in zwei verschiedene Arten unterteilt werden. Der erste Typ enthält zwei oder mehr Karten des gleichen Ranges. Alle Paare, zwei Paar Hände, Reisen, Full House, Vierling und fünf von einem freundlichen Hände fallen in diese Kategorie. In der zweiten Kategorie sind alle Hände mit keine Karten von übereinstimmenden Rang. Dazu gehören Royal Flush, Straight flush, geraden, Flushes und hohe Karte Hände. (Eine hohe Karte Hand ist als fünf unabhängigen Karten definiert.)
Dies teilt das Problem in zwei kleinere Probleme. In jedem Fall wir eine Hand gegen einen bestimmten Typ nur einmal testen möchten, und wir würden gerne für die seltener Hände nach dem häufiger testen. Pseudo-Code für eine Teillösung ist in Codebeispiel 1.
Codebeispiel 1. Pseudocode für neue Hand testen bestellen.
{Test erste Gruppe - Hände mit Karten des gleichen Ranges}
Wenn IsOnePair dann
Wenn IsThreeOfAKind dann
Wenn IsFourOfAKind dann
Wenn IsFiveOfAKind dann
fünf von einer freundlichen Verarbeitung zu tun
Else {nicht fünf, sondern vier einer Art}
vier einer Art Verarbeitung zu tun
Ende
Ende
sonst
Wenn IsFullHouse dann
volles Haus-Verarbeitung zu tun
Else {Nein, nur Reisen}
drei einer Art Verarbeitung zu tun
Ende {wenn IsThreeOfAKind}
{keine Ausflüge, wie etwa zwei Paare}
sonst
Wenn IsTwoPairs dann
zwei Paare, die Verarbeitung zu tun
Ende {wenn IsTwoPairs}
sonst
ein paar Verarbeitung zu tun
Ende {wenn IsOnePair}
Dieses sieht wie es bessere Leistung eine sollte, aber es das Problem hat des Seins viel schwieriger, mit zu arbeiten. Nach der Implementierung dieses, ich es getestet und die neuen Bugs, die eingeführt wurden behoben. Verwenden keine wilden Karten, konnte die Bibliothek jetzt 25.800 Hände pro Sekunde bewerten. Das ist eine gute Verbesserung. Allerdings ist es immer noch nicht gut genug. Benchmarking für zwei Wildcards würde noch dauern, in der Nähe von einer Stunde - zehn Stunden für vier.
Optimierung 2
Gehen wir zurück zum Profil, sehe ich, dass SwapCards viel angerufen wird. Also sollten wir seinen Code Auschecken und finde die Orte, von denen es aufgerufen wird. Der Code ist einfach Vanille. Es gibt keine Möglichkeit hinter Assemblersprache um es schneller. Jedoch ist die Sortierroutine SwapCards aufrufen, anstatt eine eigene austauschen. Die Sort-Routine ist nachfolgend aufgeführt:
Procedure SortCardsLowToHigh (Var Hand: TcaaEvaluationHand);
var
LeftCardPos, RightCardPos: Integer;
beginnen
für LeftCardPos: = 2 bis 5 tun
für RightCardPos: = 5 Downto LeftCardPos tun
Wenn Hand [RightCardPos-1]. Rang >
Blatt [RightCardPos]. Dann Rang
SwapCards(Hand,rightCardPos-1,rightCardPos);
Ende;
Ändern des Codes für eigene austauschen sparen einen Funktionsaufruf, jedes Mal wird ein Swap hergestellt. Die Sort-Routine ist selbst über vier Millionen Mal aufgerufen. Das sollte uns etwas mehr Geschwindigkeit geben. Es möglicherweise auch möglich, die Art sich zu verbessern. Verbrachte ich ein wenig Zeit, versuchen andere Algorithmen, aber theoretisch schnelleren Arten erbrachte keine Verbesserungen und in vielen Fällen Dinge verlangsamt. Der Grund dafür ist, dass die Länge des Arrays mit den Aufwand viele andere Sortiermethoden zusammengefasst.
Optimierung 3 - Fehler beheben
Es ist Zeit, um die IsFlush-Funktion und alle seine Geschwister suchen. Der Code ist unten aufgeführt:
Funktion IsFlush(Hand: TcaaEvaluationHand): Boolean;
beginnen
Ergebnis: = False;
Wenn (Hand [1]. Anzug = Hand [2]. Anzug) und (Hand [1]. Anzug = Hand [3]. Anzug
und (Hand [1]. Anzug = Hand [4]. Suit)
und (Hand [1]. Anzug = Hand [5]. Anzug) dann Ergebnis: = True;
Ende;
Nichts viel hier zu tun. Oder gibt es? Der Hand-Parameter ist ein Array von Datensätzen und es als ein Standardparameter - was auf dem Stapel bedeutet übergeben wird. Hoppla. Dumme Fehler. Dies ist Code ich Form der ursprünglichen Pascal-Bibliothek kopiert. Die einzigen Änderungen, die ich gemacht wurden die Ergebnisvariable anstelle von den Namen der Funktion zuweisen. Ich tat etwas, das nicht notwendig anstatt etwas war, die geholfen haben würde. Herstellung von Hand einen konstanten Parameter wird die Geschwindigkeit erheblich verbessern.
Ich ging dann durch den Rest des Codes finden Arrays, Aufzeichnungen oder Zeichenfolgen an Funktionen als standard-Parameter übergeben wird. Ja, fand ich eine Menge von ihnen. Mit dieser festen kann die Bibliothek 38.900 Hände pro zweite Verwendung von keine Wildcards auswerten. Mit einem Joker, entsteht eine respektable 9.800 Hände pro Sekunde.
Optimierung 4
Ich schaute weiter was die Benchmark-Ergebnisse zu zeigen. Denken Sie daran, dass jede Wild-Karte über eine 80 % Geschwindigkeitsnachteil hinzufügen wird. Die Gründe dafür wurden bereits erläutert. Ich wartete, um es zu beheben, weil ich noch nicht herausgefunden, was zu tun ist. Schauen wir uns einen kleinen Teil des Codes.
Platzhalter: = NumWildCards(Hand);
Platzhalter der Fall
0: {nicht interessiert in diesem}
1: begin {eine Wild Card}
für wc5: = CaaClubAce CaaSpadeKing do
beginnen
TempHand: = Hand;
TempHand [5]. Rang: = TcaaRank((wc5) mod 13);
TempHand [5]. Anzug: = TcaaSuit((wc5) Div 13);
Brauche ich wirklich alle zweiundfünfzig mögliche Karten zu testen? Es ist sicherlich die sicherste Sache zu tun, als einen ersten Versuch. Es funktioniert. Aber es ist sicher nur langsam. Zeit, um wieder auf mein Poker-Hut zu setzen. Alle dreizehn Ränge müssen getestet werden. Muss ich alle vier Farben zu testen? Nein tue ich nicht. Hier ist der Grund. Die einzige Bedeutung hat der Anzug ist festzustellen, ob die Hand irgendeine Form von Flush ist. Nur so kann ein Anzug einen Unterschied machen kann ist, wenn es den Anzug der anderen Karten passt. Ich kann nur eine der Karten (Wild) zu überprüfen und verwenden nur diesen Anzug. Hier ist, was der neue Code aussieht.
Platzhalter: = NumWildCards(Hand);
Platzhalter der Fall
0: {nicht interessiert in diesem}
1: begin {eine Wild Card}
{Menge Start starten der Farbe Erstkarte}
StartCardPos: = Ord (Hand [1]. Suit) * 13;
EndCardPos: = StartCardPos + 12;

für wc5: = StartCardPos EndCardPos do
beginnen
TempHand: = Hand;
TempHand [5]. Rang: = TcaaRank((wc5) mod 13);
TempHand [5]. Anzug: = TcaaSuit((wc5) Div 13);
Jetzt statt testen zweiundfünfzig Varianten für jede Wild-Karte teste ich nur dreizehn. Diese gleichen Änderung muss für zwei Joker und drei Joker Hände auch gemacht werden. (Die Routinen für vier und fünf Wildcard-Hände, die gleiche Weise funktionieren nicht und müssen nicht geändert werden.) Die Geschwindigkeit Diskrepanz zwischen Wild Card und nicht Wild Card Karte Karte Auswertungen hat etwa halbiert worden. Mit einem Joker, wertet die Bibliothek jetzt 22.000 Hände pro zweite und 12.000 Hände pro Sekunde mit zwei Joker.
Optimierung 5
Die fünfte Optimierung stammt aus der 'Ich eher Glück als gut wäre' Schule der Programmierung. Ich war zufrieden mit der Geschwindigkeit zu diesem Zeitpunkt, also habe ich beschlossen, die Bibliothek in anderen Delphi-Versionen zu testen. Ich begann mit Delphi 1. Da der String-Typ in Delphi 1 fixiert ist und die Default-Deklaration eine Deklaration von String [255 entspricht], habe ich zwei neue String-Typen. Man würde den Kartennamen halten. Andererseits würde der Name Hand zu halten.
Meine Erfahrung mit kurzen Streichern bislang, dass sie extrem schnell sind. Inprise möchte wohl die kurze Schnur auslaufen zu lassen. Mehrere Zeichenfolgen-Datentypen erschweren die Umsetzung der Sprache. Dennoch, ich benutze sie oft in meinem Code und ich sah keinen Grund, nicht zu verwenden in allen Versionen der Bibliothek. Dies würde die Dinge einfach halten. Aber ich wollte zu erproben. Es erwies sich der einzelne größte 'Optimierung' ich machen könnte. (Auch rätselhaft! Ein Problem mit Codeposition in Erinnerung?)

Source-Code
Quellcode für die Wild-Card-Bibliothek, eine Begleiter-Videopoker-Bibliothek, ein Beispiel video Pokerspiel und die Dienstprogramme, die im Artikel beschriebene kann von https://charlesappel.home.mindspring.com/ heruntergeladen werden.