Wann sollten keine STL-Algorithmen verwendet werden? Beispiel geben

Genossen, guten Abend! Sie haben die erste Ausgabe des Buches " C ++ 17 STL. Standard Template Library " so kühl von uns auseinander genommen und analysieren die zweite weiter, dass wir uns schließlich entschlossen haben, hier eine alternative Sichtweise vorzustellen. Der Autor des heutigen Artikels ist Ivan Čukić, dem auch das Buch Functional Programming in C ++ gehört, das für die Veröffentlichung im Manning Publishing House vorbereitet wird. Wir bieten an, seine skeptischen Gedanken, seinen Code und seine Berechnungen zu bewerten

Präambel

Ich wollte diesen Beitrag "Über die Bösartigkeit von STL-Algorithmen" nennen, um meine eigenen Fähigkeiten beim Provozieren von Klicks zu testen. Aber dann entschied er, dass es besser sei, einen Artikel für die Zielgruppe zu schreiben und keinen solchen Beitrag zu schreiben, in dem diejenigen zusammenkommen würden, die über meine ungeheuren Thesen streiten möchten.

Daher kann ich davon ausgehen, dass Sie sich für Algorithmen und deren Komplexität interessieren und den perfektesten Code schreiben möchten.

Algorithmen

In der modernen professionellen C ++ - Community wird häufig empfohlen, Ihr Programm sicherer, schneller, ausdrucksvoller usw. zu machen. - Verwenden Sie die Algorithmen aus der Standardbibliothek. Ich versuche auch, diesen Rat in meinen Büchern, Reden, Seminaren bekannt zu machen ... wo immer es ein geeignetes Publikum gibt.

Natürlich ist es absolut richtig, dass wir, wenn wir eine for Schleife schreiben wollen, um das vor uns liegende Problem zu lösen, zuerst darüber nachdenken müssen, ob die vorhandenen Algorithmen der Standardbibliothek (oder des Boosts) dafür geeignet sind, und nicht blind handeln.

Wir müssen noch wissen, wie diese Algorithmen implementiert sind, welche Anforderungen und Garantien mit ihnen verbunden sind, wie räumlich und zeitlich sie komplex sind.

Wenn wir vor einer Aufgabe stehen, die genau den Anforderungen des STL-Algorithmus entspricht und direkt angewendet werden kann, ist dieser Algorithmus normalerweise die effektivste Lösung.

Ein Problem kann auftreten, wenn wir die Daten auf irgendeine Weise vorbereiten müssen, bevor wir den Algorithmus anwenden.

Schnittmenge von Mengen

Angenommen, wir schreiben ein Tool für C ++ - Entwickler, das Tipps zum Ersetzen der Standarderfassungsoptionen (über [=] und [&] ) in Lambda-Ausdrücken gibt und explizit eine Liste der erfassten Variablen anzeigt.

 std::partition(begin(elements), end(elements), [=] (auto element) { ^~~ -  -  ,   [threshold] return element > threshold; }); 

Beim Parsen einer Datei benötigen wir eine Sammlung, in der Variablen aus dem aktuellen und dem benachbarten Bereich gespeichert werden. Sobald wir auf einen Lambda-Ausdruck mit einer Standarderfassung stoßen, müssen wir sehen, welche Variablen dort verwendet werden.

Als Ergebnis haben wir zwei Mengen: In einer gibt es Variablen aus den umgebenden Sichtbarkeitsbereichen und in der anderen Variablen, die im Hauptteil des Lambda-Ausdrucks verwendet werden.

Die Liste der Erfassungsoptionen, die wir zum Ersetzen anbieten, sollte der Schnittpunkt dieser beiden Mengen sein (Lambda-Ausdrücke können globale Variablen verwenden, die nicht erfasst werden müssen, und nicht alle Variablen aus dem umgebenden Bereich werden im Lambda-Ausdruck verwendet).

Und wenn wir eine Kreuzung benötigen, können wir den std::set_intersection .

Dieser Algorithmus ist in seiner Einfachheit ziemlich schön. Es akzeptiert zwei sortierte Sammlungen und führt sie gleichzeitig von Anfang bis Ende aus:

• Wenn das aktuelle Element in der ersten Sammlung dem aktuellen Element in der zweiten Sammlung entspricht, wird es zum Ergebnis hinzugefügt, das der Algorithmus einfach zum nächsten Element in beiden Sammlungen verschiebt.
• Wenn der tatsächliche Artikel in der ersten Sammlung kleiner als der tatsächliche Artikel in der zweiten Sammlung ist, überspringt der Algorithmus einfach den aktuellen Artikel in der ersten Sammlung.
• Wenn der tatsächliche Artikel in der ersten Sammlung größer ist als der tatsächliche Artikel in der zweiten Sammlung, überspringt der Algorithmus einfach den aktuellen Artikel in der zweiten Sammlung.

Mindestens ein Element (aus der ersten oder zweiten Eingabesammlung) wird in jeder Iteration übersprungen - daher ist die Komplexität des Algorithmus linear - O(m + n) , wobei m die Anzahl der Elemente in der ersten Sammlung und n die Anzahl der Elemente in der zweiten Sammlung ist .

Einfach und effektiv. Solange die Eingabesammlungen sortiert sind.

Sortieren

Hier ist das Problem: Was ist, wenn die Sammlungen nicht vorsortiert sind?

Im vorherigen Beispiel ist es ratsam, Variablen aus den umgebenden Sichtbarkeitsbereichen in einer stapelartigen Struktur zu speichern, in der der Parser einfach neue Elemente hinzufügen und einen neuen Bereich eingeben und die Variablen des aktuellen Bereichs löschen kann, sobald er den Bereich verlässt.

Daher werden Variablen nicht nach Namen sortiert, und wir können std::set_intersection nicht direkt für Operationen an ihnen verwenden. Wenn Sie die Variablen im Hauptteil eines Lambda-Ausdrucks verfolgen, können wir sie höchstwahrscheinlich nicht in sortierter Form speichern.

Da std::set_intersection nur mit sortierten Sammlungen funktioniert, tritt in vielen Projekten dieses Prinzip auf: Zuerst sortieren wir die Sammlungen und rufen dann den std::set_intersection .

Wenn wir vergessen, dass das Sortieren eines Variablenstapels in unserem Beispiel die gesamte Verwendung des von uns definierten Stapels vollständig abwertet, sieht der Schnittalgorithmus für unsortierte Sammlungen ungefähr so ​​aus:

 template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_1(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { std::sort(first1, last1); std::sort(first2, last2); return std::set_intersection(first1, last1, first2, last2, dest); } 

Was ist die Komplexität dieses gesamten Algorithmus? Das Sortieren dauert quasilinear, daher beträgt die Gesamtkomplexität dieses Ansatzes O(n log n + m log m + n + m) .

Kleiner sortieren

Kann man auf Sortieren verzichten?

Wenn beide Sammlungen nicht sortiert sind, müssen wir die zweite Sammlung für jedes Element von der ersten umgehen, um zu entscheiden, ob es in die Ergebnismenge aufgenommen werden soll. Obwohl dieser Ansatz in realen Projekten weit verbreitet ist, ist er noch schlimmer als der vorherige - seine Komplexität ist O(n * m) .

Anstatt alles in einer Reihe zu sortieren oder nichts zu sortieren, erinnere dich an Zen und wähle den dritten Pfad - wir sortieren nur eine Sammlung.

Wenn nur eine Sammlung sortiert ist, können wir alle Werte der unsortierten nacheinander durchlaufen und für jeden Wert prüfen, ob sie in der sortierten Sammlung enthalten sind. Wenden Sie dazu eine binäre Suche an.

In diesem Fall beträgt die zeitliche Komplexität O(n log n) zum Sortieren der ersten Sammlung und O (m log n) zum Sortieren und Überprüfen. Die Gesamtkomplexität beträgt O((n + m) log n) .

Wenn wir uns entscheiden würden, die zweite Sammlung und nicht die erste zu sortieren, wäre die Komplexität O((n + m) log m) .

Um maximale Effizienz zu erzielen, sortieren wir immer die Sammlung, in der weniger Elemente vorhanden sind, so dass die endgültige Komplexität unseres Algorithmus besteht
((m + n) log (min(m, n)) .

Die Implementierung sieht folgendermaßen aus:

 template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_2(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_2(first2, last2, first1, last1, dest); return; } std::sort(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return std::binary_search(first1, last1, FWD(value)); }); } 

In unserem Beispiel mit Erfassungslisten in Lambda-Ausdrücken wird die Sammlung der im Lambda-Ausdruck vorhandenen Variablen normalerweise sortiert, da sie wahrscheinlich kleiner ist als die Sammlung aller Variablen aus allen umgebenden Bereichen.

Hashing

Die letzte Option besteht darin, std::unordered_set (eine Hash-basierte ungeordnete Set-Implementierung) aus einer kleineren Sammlung zu erstellen, anstatt sie zu sortieren. In diesem Fall beträgt die durchschnittliche Komplexität der Suchvorgänge O(1) , es std::unordered_set Zeit, bis std::unordered_set . Die Gebäudekomplexität kann von O(n) bis O(n*n) reichen, und dies ist ein potenzielles Problem.

 template <typename InputIt1, typename InputIt2, typename OutputIt> void unordered_intersection_3(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_3(first2, last2, first1, last1, dest); return; } std::unordered_set<int> test_set(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return test_set.count(FWD(value)); }); } 

Der Hashing-Ansatz gewinnt vollständig, wenn Sie die Schnittpunkte mehrerer Sätze mit einem einzigen vordefinierten kleinen Satz berechnen müssen. Das heißt, wir haben die Menge A , die Mengen B₁ , B₂… und wir wollen A ∩ B₁, A ∩ B₂… berechnen A ∩ B₁, A ∩ B₂…

In diesem Fall können Sie die Komplexität des Konstrukts std::unordered_set ignorieren, und die Komplexität der Berechnung jedes Schnittpunkts ist linear - O(m) , wobei m die Anzahl der Elemente in der zweiten Sammlung ist.

Kontrolle

Natürlich ist es immer nützlich, die Komplexität des Algorithmus zu überprüfen, aber in solchen Fällen ist es auch ratsam, verschiedene Ansätze mithilfe von Prüfpunkten zu überprüfen. Besonders bei der Auswahl aus den letzten beiden Optionen, bei denen wir binäre Suchen und Hash-basierte Mengen vergleichen.
Mein einfachster Test hat gezeigt, dass die erste Option, bei der Sie beide Sammlungen sortieren müssen, immer die langsamste ist.

Das Sortieren einer kleineren Sammlung übertrifft std::unordered_set wenig, jedoch nicht besonders.

Sowohl der zweite als auch der dritte Ansatz sind etwas schneller als der erste, wenn beide Sammlungen die gleiche Anzahl von Elementen aufweisen, und viel schneller (bis zu sechsmal), wenn die Anzahl der Elemente in einer Sammlung etwa 1000-mal höher ist als in der zweiten.