Andrei Alexandrescu ist eine echte lebende Legende. Dies ist eine Person, die einen bedeutenden Beitrag zur Geschichte moderner Programmiersprachen und verallgemeinerter und Metaprogrammiertechniken geleistet hat. Wie viele Exemplare wurden in Diskussionen
über moderne C ++ - Design- und
Codierungsstandards 101 (geschrieben mit Sutters außergewöhnlichem C ++ - Wappen) und anderen
Büchern und Artikeln gebrochen
? Als Mitautor
der D-Sprache hatte er die Möglichkeit, nicht nur zu theoretisieren, sondern auch seinen Traum zu verwirklichen - und, was charakteristisch ist,
verkörperte er .
Jetzt halten Sie einen
Bericht von der DotNext 2018 Piter-Konferenz in seinen Händen, in dem es um moderne Optimierungstechnologien geht. Was hat .NET damit zu tun? Dies ist ein grundlegender Bericht einer Person, die ihr ganzes Leben lang optimiert hat. Wenn Ihnen die Leistung wichtig ist, müssen Sie sie ansehen (oder diesen Artikel lesen). Willkommen bei Katze!
Die Kunst des Benchmarking
Ich möchte mit Ihnen einige Themen im Zusammenhang mit Benchmarking diskutieren. Lassen Sie uns zunächst einige grundlegende Dinge wiederholen.
Amdahls Gesetz gehört zu den Klassikern der Informatik, es wird hauptsächlich im parallelen Rechnen verwendet, funktioniert aber in jedem komplexen System. Wenn wir die Arbeit eines bestimmten Systems verbessern wollen, müssen wir dort beginnen, wo sich die Hauptprobleme dieses Systems konzentrieren. Das Gesetz selbst liegt auf der Hand: Wenn eine Komponente 20% des Systems ausmacht, beträgt die maximale Verbesserung der Systemleistung, die durch die Optimierung des Betriebs nur dieser Komponente erzielt werden kann, 20%. Zu oft muss ich Leute treffen (natürlich gehören unsere Leser nicht zu ihnen), die Dinge wie das Optimieren der Befehlszeilenanalyse optimieren. Diese Operationen dauern die ersten 10 Mikrosekunden Ihres Programms, und die Leute analysieren ihre algorithmische Komplexität und sind entsetzt, wenn die Zeit quadratisch ist.
Wie Sie wahrscheinlich wissen, müssen Sie vor Beginn der Optimierung ein Profil der Anwendung erstellen und Hotspots darin auswählen. Hier sollte über das
Gesetz von Ladma gesagt werden (dies ist kein richtiger Familienname, und Amdal, rückwärts gelesen). Sie müssen sich auf die Komponente konzentrieren, die zu der größten Zeitinvestition führt. Es muss außerhalb der Anwendung verschoben werden, die erforderlichen Arbeiten ausführen, zurückkehren und erneut testen. Der Grund, warum Sie dies tun müssen, ist, dass eine Leistungsverbesserung von 20% sehr oft das Ergebnis von zehn Verbesserungen von 2% ist. Und im Rahmen eines großen Systems ist es unmöglich, eine so kleine Verbesserung zu messen. Dazu muss die Komponente in einer Testsuite getestet werden. Eine 20% ige Verbesserung der Leistung einer der Hauptkomponenten des Systems kann eine 5% ige Verbesserung des gesamten Systems bedeuten, und für einige Bereiche ist dies ein hervorragendes Ergebnis. Vergessen Sie nicht, dass Optimierungen eine Reihe globaler Auswirkungen haben können. Basierend auf den Ergebnissen des selektiven Benchmarking sollten Sie daher sehr vorsichtig sein, um Schlussfolgerungen über den Betrieb des gesamten Systems zu ziehen.
Ein Fehler, den unsere Leser sicher nicht machen, der aber im Allgemeinen weit verbreitet ist: Die Leute messen die Geschwindigkeit des Debuggens von Assemblys. Dies sollte niemals getan werden. Dies ist vergleichbar mit der Aufregung wegen der geringen Geschwindigkeit der Schnecke bei den Rennen: Es ist nicht für einen solchen Wettbewerb gedacht, es hat andere Ziele im Leben. Ein weiterer, etwas weniger offensichtlicher Fehler: Die Benutzer messen zuerst die Grundleistung des Systems und führen unmittelbar danach ein Benchmarking durch. Nach dem Sammeln der Basislinie werden jedoch viele Ressourcen aufgewärmt. Beispielsweise werden geöffnete Dateien gepuffert und verbleiben im Speicher (zumindest unter Linux). Somit ist der zweite Test nur schneller, weil er nach dem ersten gestartet wird. Dies geschieht sogar bei Malloc-Anrufen. Nach diesen Aufrufen kehrt das System nicht in den ursprünglichen Zustand zurück, selbst wenn Speicherfreigabeaufrufe getätigt werden. Die interne Konfiguration, das Caching und die Funktionen, die vom Speicherzuweiser verwendet werden, ermöglichen es, dass die folgenden Malloc-Aufrufe viel schneller ausgeführt werden. Auch ohne Berücksichtigung der Auswirkungen des Caches erinnert sich malloc, dass beispielsweise einige Funktionen Speicher für Objekte mit 4 Kilobyte mehrmals zugewiesen haben, was bedeutet, dass Sie eine freie Liste mit einer Elementgröße von 4 Kilobyte benötigen. Oder ein anderes Beispiel: DNS-Lookups werden nach der ersten Abfrage zur Wiederverwendung zwischengespeichert. Wenn möglich, müssen Sie während des Benchmarking den gesamten Prozess jedes Mal von Anfang bis Ende neu starten.
Um beispielsweise das System vollständig in den ursprünglichen Zustand zurückzusetzen, müssen Dateien im Falle von Dateien auf einer separaten Festplatte geöffnet werden, die nach Abschluss des Tests entfernt werden muss (soweit ich weiß, kann dies unter Windows erfolgen). Die Bedienung ist nicht einfach, aber in den meisten Fällen notwendig.
Als ich das Gespräch über Fehler während der Optimierung fortsetzte, musste ich mich mit solchen Fällen befassen, in denen die Kosten für printf in den Testergebnissen enthalten sind. Es gibt Verfahrensfehler, wenn vor jeder Messung mehr als eine Sache geändert wird, was gegen die grundlegendsten Prinzipien eines wissenschaftlichen Experiments verstößt, da nicht klar ist, welchen Effekt Sie messen. Ein weiterer schwerwiegender Fehler besteht darin, dass einige seltene Fälle optimiert werden, was in anderen Situationen zu einer Pessimierung führt.
Hier ist ein Beispiel mit Stapelüberlauf. Der Autor sortiert häufig bereits sortierte Daten und ist überrascht, da die Funktion "is_sorted" offensichtlich viel schneller ist als "sortieren". Warum ist dann in `sort die erste Zeile nicht` wenn is_sorted return? Sie optimieren einen äußerst seltenen Fall, vollständig sortierte Daten, und alle anderen, die mindestens ein nicht sortiertes Element haben, müssen die Kosten für diese Optimierung tragen. Das ist es nicht wert.
Ich glaube, ich muss nicht lange beweisen, dass die heutigen konkurrierenden Architekturen äußerst komplex sind: dynamische Frequenzänderung, Unterbrechung durch andere Prozesse, Virtualisierung usw. Daher ist es fast unmöglich, beim Messen die gleiche Zeit zu erhalten. Ihre Indikatoren zittern immer. Daher sollte man sich nicht auf Dinge verlassen, die offensichtlich erscheinen. Angenommen, es scheint uns offensichtlich, dass weniger Anweisungen schnelleren Code bedeuten, und dies ist nicht immer der Fall. Es kann auch den Anschein haben, dass die Verwendung gespeicherter Daten immer schneller ist als die erneute Durchführung der Berechnungen. Wenn Sie also die Ergebnisse zwischenspeichern, ist dies in Ordnung. Wie im vorherigen Fall kann es nicht eindeutig angegeben werden, ebenso wie das Gegenteil nicht unbedingt angegeben werden kann - alles hängt vom Kontext ab. Natürlich sollten Sie nur eines haben: Alles muss gemessen werden. Wenn Sie alles messen, erhalten Sie bessere Ergebnisse als Experten mit Wissen, die keine Messungen durchführen.
Es gibt eine Reihe ziemlich zuverlässiger Praktiken, deren Diskussion Sie zu interessanten Gedanken führen kann. Wir müssen damit beginnen, dass die Mathematik Sie nicht im Stich lässt. Es kann gezeigt werden, dass Systeme mit unterschiedlichen Geschwindigkeiten gleichwertig sein können. Die Mathematik gibt Regeln vor, um die Äquivalenz einiger Dinge zu zeigen und einige Eigenschaften zu identifizieren, und obwohl sie nicht voreingenommen ist, spielt es keine Rolle, welche Dinge interessant sind und welche nicht. Viele Leute denken, dass die Optimierung auf der Kenntnis des Maschinencodes und der Arbeit mit Bits basiert, aber tatsächlich hat sie viel Mathematik, weil Sie beweisen, dass ein schnelleres System einem langsameren entspricht.
Eine andere allgemeine Regel ist, dass Computer Dinge lieben, die langweilig sind. Müssen Sie sich gegenseitig mit zwei Vektoren multiplizieren, jeweils eine Milliarde Elemente? Dies ist eine ideale Aufgabe für einen Computer. Alle darin enthaltenen Geräte sind speziell für diese Art von Aufgaben geschärft. Um diese Daten zu analysieren, basierend darauf, um einen regulären Ausdruck zu erstellen, möchte ich dies nicht tun. Computer mögen keine Dinge wie Zweige, Abhängigkeiten, indirekte Anrufe, kurz gesagt - sie mögen keinen intelligenten Code, sie mögen langweiligen Code. Computer mögen keine indirekte Aufzeichnung - ein komplexes Problem, mit dem Menschen, die mit Eisen zu tun haben, seit langem zu kämpfen haben und das sie nicht lösen können.
Eine andere Regel ist, dass Sie den am wenigsten leistungsfähigen Operationen den Vorzug geben sollten, mit anderen Worten, die Addition zur Multiplikation und die Multiplikation zur Exponentiation bevorzugen. Auch hier ist Mathematik nützlich.
Schließlich die letzte Regel - je kleiner, desto schöner. Durch die geringe Größe können Computer ihre Vorteile am besten nutzen, da sie es vorziehen, dass die Daten und insbesondere die Anweisungen nahe beieinander liegen. Die Ergebnisse mehrerer Messungen der Geschwindigkeit der Anwendung unterscheiden sich immer, Sie haben eine gewisse Verteilung der Ergebnisse. Normalerweise nehmen wir nur den Durchschnitt dieser wenigen Ergebnisse. Das Problem ist jedoch, dass der Durchschnitt aufgrund der Besonderheiten der Computer viel Lärm enthält. Wenn Bill Gates im Durchschnitt einen Bus fährt, ist jeder Passagier in einem Bus ein Milliardär. Es klingt großartig, ist aber für einen Obdachlosen, der mit demselben Bus fährt, wenig tröstlich. Eine ähnliche Situation tritt bei Unterbrechungen auf: Die Multiplikationsoperation dauert Nanosekunden, aber wenn Sie viele Messungen solcher Operationen durchführen, wird eine von ihnen zwangsläufig eine Unterbrechung von zwei Millisekunden haben. Der Unterschied beträgt drei Größenordnungen, und dennoch berücksichtigen Entwickler dies nicht immer.
Also wiederhole ich: Das Rauschen in Computern ist immer additiv; Für Menschen mag es unbedeutend erscheinen, aber für die Mikrobenchmarkierung ist es bedeutsam, und das arithmetische Mittel wird viel Rauschen enthalten. Anstelle des Durchschnitts benötigen Sie einen Indikator, der nur die Zeit misst, die Sie irgendwie beeinflussen können. Wenn wir uns diesem Problem aus mathematischer Sicht nähern, werden wir feststellen, dass wir einen Wert finden müssen, der der größten Anzahl von Messungen entspricht, die wir durchgeführt haben. Mit anderen Worten, wir brauchen einen Mod. Dies bringt uns sofort zum Problem: Was passiert, wenn Sie den Quicksort-Mod nehmen? Wenn der Algorithmus probabilistisch ist oder wenn die Daten zufällig sind, wird es fast nie eine Mode geben. Die Wertedichte ist im gesamten Spektrum nahezu gleich. In diesem Fall verwerfen wir einfach die 5% der größten Messungen und nehmen danach den Durchschnittswert - oder das Maximum. Im letzteren Fall haben wir eine Obergrenze, die in 95% der Fälle nicht überschritten wird. Fast immer sitzt ein Thema im alten Keller mit einem langsamen Modem, in das jede Seite eine Stunde lang geladen wird. Rein menschlich sympathisieren wir natürlich mit ihm, aber wir können technisch nicht jedem helfen - daher müssen die restlichen 5% der Fälle vernachlässigt werden. Im Allgemeinen konzentrieren wir uns bei der Lösung von Netzwerkproblemen häufig auf das 95. Perzentil, da es unmöglich ist, sich auf das 100. zu konzentrieren. Das hundertste Perzentil bedeutet das langsamste Ergebnis aller gesammelten Messungen - dies ist nicht informativ.
Ersetzen Sie Zweige durch Arithmetik
Wie, wie ich hoffe, klar wurde, dass die Messung kein einfaches Problem ist. Schauen wir uns einige Beispiele an und versuchen wir zunächst, die Verzweigung durch Arithmetik zu ersetzen. Wir sprechen über Fälle, in denen wir eine if-Anweisung benötigen, aber eine zu häufige Verwendung unerwünscht ist. Stattdessen integrieren wir das Verzweigungsergebnis als 0/1-Wert. Der Code sieht linear aus, der Computer muss ihn nur von Anfang bis Ende durchlaufen, ohne darüber nachzudenken, welchen Schritt Sie als Nächstes ausführen müssen.
Versuchen wir, das folgende Problem zu lösen: Übertragen Sie die Tiefs jedes Quartils des Arrays in das erste Quartil. Mit anderen Worten, das Array muss in vier Teile unterteilt werden, und der Mindestwert jedes Teils sollte am Anfang des Arrays stehen.
static void min4(double[] p) { int n = p.Length; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < n / 4; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Oben ist der Basiscode. Übrigens kann ich stolz berichten, dass ich diese Beispiele in C # übersetzt habe und sie erfolgreich kompiliert wurden. Der Code selbst ist recht einfach: `m wird der Index des kleinsten der beiden Werte zugewiesen, die sich an den Indizes` i und` j befinden, und dann wird eine ähnliche Zuordnung abhängig von den beiden anderen Indizes noch zweimal wiederholt. Schließlich wird der Wert am Index `m im Array mit dem Wert am Index` i umgekehrt. Wie Sie sehen können, umgehen wir das Array mit vier induktiven Variablen.
Das Problem des Testens eines solchen Algorithmus ist interessant und nicht offensichtlich. Wir müssen es nicht an einem Datensatz testen, sondern an Daten, die in verschiedenen Fällen auftreten können. Zum Beispiel bei Daten, die wie Pfeifen eines Organs aussehen: zuerst erhöhen, dann verringern; auf zufällige Daten mit einer gleichmäßigen Verteilung; bei einer zufälligen Menge von Nullen und Einsen - bei nur zufälligen Daten besteht der Unterschied darin, dass es viele doppelte Werte gibt; auf bereits sortierten Daten; Schließlich auf Daten, die durch reale Messungen eines physikalischen Phänomens erhalten wurden. Dies ist ein ernstzunehmender Ansatz zur Messung der Geschwindigkeit eines Algorithmus und wird allgemein von Personen akzeptiert, die Algorithmen studieren.
Versuchen wir, den Code zu verbessern, den wir gerade kennengelernt haben.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < q; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Als erste Optimierung werden wir versuchen, eine übermäßige Wiederholung von Operationen zu vermeiden. Dazu nehmen wir mehrere Divisionsoperationen aus der Schleife heraus - dividieren von `n durch 2 und 4 und dividieren von 3 *` n durch 4. Nach dieser Optimierung stellen wir jedoch fest, dass die Berechnungen nicht für waren uns das Hauptproblem: Der Code wird nicht schneller, obwohl er kompakter sein wird. Im besten Fall werden wir eine halbe Prozent Verbesserung erzielen.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = q, k = 2 * q, l = 3 * q; for (; i < q; ++i, ++j, ++k, ++l) { int m0 = p[i] <= p[j] ? i : j; int m1 = p[k] <= p[l] ? k : l; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Die zweite Änderung, die wir am Code vornehmen werden, besteht darin, Abhängigkeiten zu reduzieren. In der vorherigen Version des Algorithmus hängt die Zuweisung von "m" zu "k" oder "l" von dem Wert ab, der der obigen Zeile "m" zugewiesen wurde. Um die Anzahl der m-Abhängigkeiten zu verringern, berechnen wir m0 und m1 getrennt und vergleichen sie dann. Als ich diese Optimierung durchführte, hoffte ich auf eine signifikante Verbesserung der Geschwindigkeit des Algorithmus, aber am Ende stellte sich heraus, dass er Null war. Meiner Meinung nach ist es jedoch wichtig, die Anzahl der Abhängigkeiten auf ein Minimum zu beschränken. Deshalb habe ich den Code gespeichert.
static void min4(double[] p) { int q = p.Length / 4; for (int i = 0; i < q; ++i) { int m0 = p[i] <= p[i + q] ? i : i + q; int m1 = p[i + 2 * q] <= p[i + 3 * q] ? i + 2 * q : i + 3 * q; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Versuchen wir nun, die Anzahl der induktiven Variablen von vier auf eins zu reduzieren, und berechnen die restlichen drei arithmetisch, da sie in ständiger Beziehung zueinander stehen. Dies ist ganz einfach: Anstelle von "k" haben wir "i + q" anstelle der beiden anderen Variablen - "i + 2 * q" und "i + 3 * q". Ich hatte auch große Hoffnungen auf diese Optimierung, aber wie die vorherige gab es keine zeitlichen Ergebnisse. Dies beweist erneut die Bedeutung von Messungen: Ohne sie könnte ich mich rühmen, die Funktionsweise des Algorithmus erheblich verbessert zu haben, und ich hätte sehr wichtige Argumente.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2: ++i) { int m0 = p[i - q] < p[i] ? i - q : i; int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q; Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Als vierten Versuch strukturieren wir den Zyklus neu, um die Multiplikation mit 3 zu beseitigen. Dies führt zu einer Verbesserung von 3%. Das Ergebnis ist immer noch nicht beeindruckend. Versuchen Sie als nächstes, die ternären Operatoren loszuwerden.
Zu diesem Zweck möchte ich Ihnen eine neue Funktion vorstellen - `static int optional (bool flag, int value). Es konvertiert den booleschen Eingabewert in Int32, multipliziert ihn mit -1 und übergibt ihn zusammen mit dem zweiten Eingabewert an den bitweisen AND-Operator. Wenn das Eingabeflag falsch war, ist es in int32 0, und nach allen Konvertierungen am Ausgang erhalten wir immer noch 0. Wenn das Eingabeflag wahr war, ist es in int32 1, wenn es mit -1 multipliziert wird, erhalten wir FFFFFFFF, was nach dem Bit "Und" mit einer beliebigen Nummer gibt diese zweite Nummer an. Bitte beachten Sie, dass es nirgendwo eine if-Anweisung gibt, der Code ohne Verzweigung ist, für einen Computer langweilig ist (obwohl er uns kompliziert erscheint).
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2; ++i) { int m0 = i - optional(p[i - q] <= p[i], q); int m1 = i + q + optional(p[i + q2] < p[i + q], q); Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Wir werden ternäre Operatoren durch diese optionale Funktion ersetzen und sie in die Berechnung integrieren. Wir wenden es zweimal an und lassen im dritten Fall das Fragezeichen. Anstelle von vier Prüfungen in diesem Zyklus habe ich also nur eine.
Aus den Messergebnissen, die Sie auf der Folie sehen, geht hervor, wie wichtig es war, den Algorithmus an mehreren verschiedenen Datensätzen zu testen. An einem Set würden wir nichts verstehen. Bei zufälligen und realen Daten haben wir eine mehr als zweifache Beschleunigung, bei Orgelpfeifen und sortierten Daten eine leichte Verlangsamung. Dies liegt an der Tatsache, dass bei sortierten Daten für den Übergangsprädiktor keine Überraschungen auftreten und diese mit 100% iger Genauigkeit vorhergesagt werden. Bei Orgelpfeifen haben wir eine falsche Vorhersage in der Mitte des Datensatzes - wiederum eine sehr hohe Genauigkeit. Im Gegensatz dazu wird bei zufälligen Daten der Unterschied zwischen unseren beiden Ansätzen sehr groß sein. Wir haben alle unvorhersehbaren Prüfungen durch einfache Logik ersetzt. Hier kommen wir zu einer einfachen Wahrheit zurück: Computer sind für das Rechnen konzipiert, wie der Name schon sagt (Computer-Computing). Verzweigen, Bilder auf dem Bildschirm anzeigen - all dies ist viel schlechter. Das bitweise Ausführen von „Und“ für sie ist viel einfacher als das Übergeben der if-Anweisung.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = 0; i < q; ++i) { int m = i + optional(p[i + q] < p[i], q); m += optional(p[i + q2] < p[m], q); m += optional(p[i + q2 + q] < p[m], q); Swap(ref p[i], ref p[m]); } }
Nachdem wir durch die Optimierung endlich ein positives Ergebnis erzielt haben, werden wir versuchen, den letzten ternären Operator durch unsere Funktion `optional zu ersetzen. Diesmal ist der Geschwindigkeitsgewinn gering. Um zu verstehen, warum dies geschieht, müssen Sie sich den generierten Code ansehen. In der vorherigen Version des Codes, in der das Fragezeichen noch vorhanden war, hat der Compiler bereits eine Möglichkeit gefunden, den Code ohne Verzweigung auszuführen. Und wenn er zum ternären Operator kommt, kann er es bereits vorhersagen. Wenn Sie dieses letzte Stück durch "optional" ersetzen, erhalten Sie einen etwas schlechteren Code. Daher wiederhole ich, es ist wichtig, jedes Mal Messungen durchzuführen.
Eine weitere Funktion, die ich Ihnen empfehlen möchte, ist "ifelse ohne Zweige", die Sie jetzt auf dem Bildschirm sehen. Zwar konnte ich damit die Leistungsverbesserungen in unserem Beispiel nicht erreichen. Wenn 0 als Flag übergeben wird, ist die erste Zeile 0; im zweiten subtrahieren wir 1 von 0 in Int32 und erhalten FFFFFFFF, wonach dieser Wert zusammen mit dem Funktionsargument `v2 an das bitweise„ Und “übergeben wird, wodurch wir dieses Argument selbst ohne Änderungen erhalten; Schließlich werden die erste und die zweite Zeile an das bitweise "ODER" übergeben, was wiederum "v2" ergibt. Wenn das Flag 1 ist, ist die erste Zeile gleich `v1; im zweiten subtrahieren wir 1 von 1 und erhalten 0, wodurch die gesamte Zeile 0 ist und 0 und "v1 im bitweisen" ODER "v1 ergeben.
Ich hoffe, dass ein solches "ifelse ohne Verzweigungsfunktion" Leute interessiert, die am Backend beteiligt sind - moderne Compiler verwenden diesen Ansatz aus irgendeinem Grund derzeit nicht. Mit diesen Funktionen können Sie die Algorithmen neu organisieren, sodass die Compiler sie für Sie verstehen, da Sie intelligenter und kreativer als Ihr Compiler sind.
Große festgelegte Kreuzung
Wechseln Sie das Gesprächsthema ein wenig und gehen Sie zum Schnittpunkt großer Mengen über. Bis jetzt haben wir über einzelne Operatoren gesprochen, jetzt werden wir neue Algorithmen erstellen, also müssen wir von den Details ablenken und unseren Geist für eine größere Perspektive öffnen. Ich gehe davon aus, dass Sie mit der Sortierung von Zusammenführungen vertraut sind, zwei Vektoren multiplizieren und nach gemeinsamen Elementen zweier sortierter Vektoren suchen. Zwei sortierte Mengen werden durchlaufen, und wenn sich gleiche Elemente in ihnen befinden, wird dies als Übereinstimmung betrachtet. Wenn eines der beiden verglichenen Elemente kleiner ist, verschiebt es sich. Dieser Algorithmus ist recht einfach, aber sehr verbreitet - wahrscheinlich der weltweit am häufigsten verwendete. Es wird in allen Abfragen aus mehreren Wörtern verwendet. Jede solche Abfrage ist der Schnittpunkt zweier Mengen. Dieser Algorithmus verwendet insbesondere Google und sollte auch in allen Datenbankabfragen angewendet werden.
int Intersect(double[] a1, double[] a2, double[] t) { if (a1.Length == 0 || a2.Length == 0) return 0; int i1 = 0, i2 = 0, i = 0; for (;;) if (a1[i1] < a2[i2]) { if (++i1 == a1.Length) break; } else if (a2[i2] < a1[i1]) { if (++i2 == a2.Length) break; } else { t[i++] = a1[i1]; if (++i1 == a1.Length || ++i2 == a2.Length) break: } return i; }
Schauen Sie sich die grundlegende Implementierung dieses Algorithmus an. Wenn beide Eingabesätze leer sind, geben wir offensichtlich 0 zurück. Als nächstes starten wir eine Endlosschleife, in der wir bei Übereinstimmung das Ergebnis um 1 erhöhen und prüfen, ob der Zyklus abgeschlossen sein soll. Anstelle einer Endlosschleife könnte man die for-Anweisung verwenden und die Bedingung für das Beenden der Schleife darin angeben. Das würde aber zusätzliche Arbeit bedeuten. In der Implementierung, die Sie auf der Folie sehen, haben wir im ersten Zweig `if (a1 [i1] <a2 [i2]), wonach es eine Erhöhung von` i1 um 1 gibt, und wir können nur` i1 überprüfen. Ebenso müssen wir im zweiten Zweig nur `i2 überprüfen. Beide Werte müssen nur im dritten Zweig überprüft werden. Wenn diese Prüfung zu Beginn des Zyklus wäre, würden wir die zusätzliche Arbeit erledigen.
Versuchen wir, diese Implementierung zu verbessern. Derzeit ist die algorithmische Komplexität in Abhängigkeit von zwei Eingabeargumenten linear. Beim maschinellen Lernen muss man häufig den Schnittpunkt von Mengen finden, die sich in Größe oder Statistik stark voneinander unterscheiden. Sie haben beispielsweise einen langen Eingabevektor und einen kurzen Merkmalsvektor, gegen den Sie prüfen. In unserem Code können eine Million Datensätze in a1 und tausend in a2 enthalten sein. In diesem Fall sind wir nicht bereit, eine Million Schritte zu durchlaufen, um diesen Algorithmus zu vervollständigen. Die größte Last wird hier in der folgenden Codezeile sein: `if (++ i1 == a1.length) break. Kurz zuvor erfolgt ein Vergleich, und dann gibt es in dieser Zeile eine Erhöhung des Wertes; Dies ist im Wesentlichen eine lineare Suche. Wir iterieren über einen langen Vektor auf der Suche nach Elementen eines kurzen. Im schlimmsten Fall werden wir viele solcher Suchen durchführen und uns langsam entlang des Vektors bewegen.
Versuchen wir, diesen Algorithmus zu verbessern. Nun, wenn nicht lineare Suche, dann ist binär besser, oder? Verwenden wir binär. Sein Vorteil ist, dass es den Index des größten der kleineren Elemente gibt.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, a1[i1]); if (m == a2.Length) continue; --m; if (!(a2[m] < a1[i1])) t[i++] = a1[i1]; } return i; }
Der obige Code ist eine Implementierung unseres binären Suchalgorithmus. Aber es ist nicht sehr effektiv. Die schlimmste Situation ist hier, wenn die binäre Suche jedes Mal fehlschlägt. Und es wird in ganz wichtigen Szenarien auftreten - zum Beispiel wenn beide Sätze identisch sind. Sie schneiden wie ein Narr Kreise mit binärer Suche, während Sie nur den ersten linearen Algorithmus durchlaufen mussten. Warum binäre Suche, wenn das gewünschte Element - jedes Mal genau hier das erste in der Liste?
Wie kann der Algorithmus erfolgreich mit identischen und unterschiedlichen Daten arbeiten? Das Überprüfen aller Daten ist für Ressourcen zu kostspielig. Ich werde einen Vorbehalt machen, dass es sich nicht um völlig identische Daten handelt, sondern um sehr ähnliche, mit ähnlichen Statistiken, Größen können auch variieren. Sie können die folgenden Punkte überprüfen. Die offensichtliche Lösung besteht darin, Ihre Suche zu reduzieren. Wenn wir eine binäre Suche durchführen, sind wir, nachdem wir ein Element gefunden haben, nicht mehr an kleineren Elementen interessiert, da auch der zweite Vektor sortiert ist. Auf diese Weise können wir jedes Mal unseren Suchbereich verkleinern und alle Elemente weniger aus dem gefundenen Element entfernen.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i2 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, i2, a2.Length, a1[i1]); if (m == i2) continue; if (!(a2[m - 1] < a1[i1])) t[i++] = a1[i1]; i2 = m + 1; } return i; }
Hier ist die Implementierung dieses Ansatzes. Sie sehen, dass wir jedes Mal eine binäre Suche nach einem Teil des ursprünglichen Arrays durchführen, beginnend mit `i2 und endend mit` a2.length. Da `i2 mit jeder Suche zunimmt, wird der Suchbereich verkleinert.
Die nächste Optimierung, die ich hier implementieren möchte, bezieht sich auf den Galloping Search-Algorithmus. Im Wesentlichen ist dies eine binäre Suche mit einem anderen Schritt. Bei der binären Suche beginnen wir jedes Mal in der Mitte. Wenn wir jedoch nach einem Namen im Telefonbuch suchen, öffnen wir ihn nicht in der Mitte. Wenn der Nachname einer Person beispielsweise bei "B" beginnt, öffnen wir das Buch näher am Anfang. Dieses Prinzip wird in einer galoppierenden Suche implementiert: Wir beginnen mit dem Crawlen der Daten in aufsteigender Richtung mit einem Schritt, der nach jeder Prüfung exponentiell zunimmt: zuerst 1, dann 2, dann 4. Dies gibt uns eine gute algorithmische Komplexität. Wenn der Schritt linear wachsen würde, wäre die Komplexität quadratisch. Wenn wir das gesuchte Element „überspringen“, führen wir eine normale binäre Suche für das verbleibende Segment durch, die klein ist und die Ausführungszeit des Algorithmus nicht wesentlich beeinflusst. Somit kombinieren wir alle Vorteile beider Ansätze. Implementierung eines solchen Algorithmus:
int GBsearch(double[] a, int i, int j, double v) { for (int step = 1;; step *= 2) { if (i >= j) break; if (a[i] > v) break; if (i + step >= j) return Bsearch(a, i + 1, J, v); if (a[i + step] > v) return Bsearch(a, i + 1, i + step, v); i += step + 1; } return i; }
Wir diskutieren nun die Skalierung, dh versuchen, den Schnittpunkt von mehr als zwei Mengen zu finden. Für jede Suche nach mehreren Wörtern müssen wir den Schnittpunkt mehrerer Mengen finden. Dazu können wir zum Beispiel die ersten beiden Mengen vergleichen, dann ihren Schnittpunkt mit der dritten und so weiter. Dies ist jedoch keine optimale Lösung. Wir müssen die ersten Elemente aller Mengen nehmen und die kleinsten finden, die dann verschoben werden müssen. Wir brauchen eine Datenstruktur, die es uns ermöglicht, das kleinste der vielen Elemente zu finden, und die eine konstante Komplexität aufweist. Eine solche Datenstruktur ist ein Haufen. Aber es wird ein seltsamer Haufen sein, es wird nicht auf einem physischen Array basieren. Es wird imaginär sein, wir werden darin nur die ersten Elemente unserer Sets organisieren. Sobald wir das kleinste Element im Heap gefunden haben, können wir immer noch alle anderen Mengen durchsuchen.
Die Arbeit an den Themen, die wir heute in der Praxis diskutieren, hat eine eher handwerkliche Form. In der Praxis werden wir meistens mehrere Sets haben, nicht nur zwei, und es wurde ziemlich viel Arbeit zu diesem Thema geschrieben. Der klassische Algorithmus hier ist SVS, bei dem wir die Mengen gruppieren, die zwei kleinsten nehmen und die kürzesten als Kandidaten auswählen.
Hier finden Sie einen guten Überblick zu diesem Thema. Die Probleme, die mit sich überschneidenden Mengen, dem Skalarprodukt spärlicher Vektoren, dem Sortieren durch Zusammenführen und jeglichen Formen des Vergleichs mit dem Bild im Laufe der Zeit verbunden sind, werden immer interessanter. Der Algorithmus, den ich Ihnen gezeigt habe, hat sich als sehr nützlich erwiesen. Vielen Dank für Ihre Aufmerksamkeit.
Andrei Alexandrescu wird nicht zu DotNext 2018 Moskau kommen, aber Jeffrey Richter, Greg Young, Pavel Yosifovich und andere werden dort sein. Die Namen der Redner und Themen der Berichte finden Sie hier und Tickets hier . Jetzt mitmachen!