Auf meinem Computer (Quadcore, 8 GB RAM), der Vista x64 Business mit Visual Studio 2008 SP1 ausführt, versuche ich, zwei Zahlengruppen sehr schnell zu schneiden.
Ich habe zwei Ansätze in C ++ und einen in C # implementiert. Der C # -Ansatz ist bisher schneller, ich möchte den C ++ - Ansatz verbessern, also ist er schneller als C #, was ich von C ++ erwarten kann.
Hier ist die C # -Ausgabe: (Release build)
%Vor%Hier ist die ursprüngliche C ++ - Ausgabe für zwei verschiedene Ansätze (Release x64 build):
%Vor%Hier ist die neueste C ++ - Ausgabe für drei Ansätze (Release x64 build):
Neueste Benchmark:
%Vor%Also ist der set_intersection-Ansatz jetzt ungefähr 2x langsamer als C #, aber 2x schneller als die anfänglichen C ++ - Ansätze.
Letzter C ++ Code:
%Vor%C # -Code:
%Vor%C ++ - Code:
%Vor%Ok, hier ist das Neueste, mit einigen Änderungen:
C ++ (Release, x64) Ergebnisse:
%Vor%Also ist es 2x langsamer als C #. @Jalf: Du bekommst ein paar ziemlich schnelle Zahlen. Gibt es etwas, das ich hier falsch mache?
C ++ Code:
%Vor%Es gibt mehrere Probleme mit Ihrem Test.
Zuerst testen Sie nicht die Schnittmenge, sondern "erstellen ein paar Felder, füllen sie mit Zufallszahlen und führen dann den Schnittpunkt". Sie sollten nur den Teil des Codes takten, an dem Sie wirklich interessiert sind. Selbst wenn Sie diese Dinge tun wollen, sollten sie hier nicht bewertet werden. Messen Sie eine Sache nach der anderen, um die Unsicherheit zu reduzieren. Wenn Sie möchten, dass Ihre C ++ - Implementierung besser funktioniert, müssen Sie zuerst wissen, welcher Teil langsamer als erwartet ist. Das bedeutet, dass Sie den Setup-Code vom Schnittpunkttest trennen müssen.
Zweitens sollten Sie den Test viele Male ausführen, um mögliche Caching-Effekte und andere Unsicherheiten zu berücksichtigen. (Und wahrscheinlich eine Gesamtzeit für, sagen wir, 1000 Läufe, anstatt einer einzelnen Zeit für jeden ausgeben. Auf diese Weise verringern Sie die Ungewissheit von der Zeitschaltuhr, die Auflösung begrenzt haben könnte und ungenaue Ergebnisse berichten, wenn im 0-20ms-Bereich verwendet / p>
Außerdem, soweit ich aus den Dokumenten lesen kann, sollte die Eingabe in set_intersection sortiert werden, was set2 nicht sein wird. Anscheinend gibt es keinen Grund, unordered_map zu verwenden, wenn unordered_set viel besser für das passt, was Sie tun.
Über den Setup-Code, der benötigt wird, beachten Sie, dass Sie wahrscheinlich nicht brauchen, um Vektoren zu füllen, um die Kreuzung zu führen. Sowohl Ihre eigene Implementierung als auch set_intersection arbeiten bereits an Iteratoren, sodass Sie ihnen einfach ein Paar Iteratoren an die Datenstrukturen übergeben können, in denen Ihre Eingaben bereits enthalten sind.
Ein paar genauere Kommentare zu Ihrem Code:
++iterator anstelle von iterator++
unordered_set (nicht unordered_map ) Bearbeiten:
Ich habe Ihre C # Version nicht ausprobiert, daher kann ich die Zahlen nicht richtig vergleichen, aber hier ist mein modifizierter Test. Jedes wird 1000 Mal auf einem Core 2 Quad 2,5 GHz mit 4 GB RAM ausgeführt:
%Vor%Der letzte ist ein bisschen unfair, weil er die Vektoren kopieren und sortieren muss. Im Idealfall sollte nur die Sorte Teil des Benchmarks sein. Ich habe versucht, eine Version zu erstellen, die ein Array von 1000 unsortierten Vektoren verwendet (ich würde also nicht die unsortierten Daten in jeder Iteration kopieren müssen), aber die Leistung war ungefähr gleich, oder etwas schlechter, da dies zu konstanten Cache-Fehlern führen würde Also bin ich zu dieser Version zurückgekehrt
Und mein Code:
%Vor% Es gibt keinen Grund, warum C ++ immer schneller sein sollte als C #. C # hat einige wichtige Vorteile, die mit großer Sorgfalt in C ++ konkurrieren müssen.
Der erste, den ich mir vorstellen kann, ist, dass dynamische Zuweisungen im .NET-Land lächerlich billig sind. Jedes Mal, wenn ein C ++ - Vektor, set oder unordered_set (oder ein anderer Container) die Größe ändern oder erweitern muss, ist dies eine sehr kostspielige Operation malloc . In .NET ist eine Heap-Zuweisung wenig mehr als das Hinzufügen eines Offsets zu einem Zeiger.
Wenn also die C ++ - Version konkurrieren soll, müssen Sie wahrscheinlich das Problem lösen, indem Sie Ihren Containern die Größe anpassen, ohne die Heapzuweisungen vornehmen zu müssen, wahrscheinlich mithilfe benutzerdefinierter Zuordnungen für die Container (möglicherweise boost :: pool) eine gute Wette sein, oder Sie können versuchen, Ihre eigenen rollen)
Ein weiteres Problem ist, dass set_difference nur bei sortierten Eingaben funktioniert. Um Testergebnisse zu reproduzieren, die eine Sortierung beinhalten, müssen wir in jeder Iteration eine neue Kopie der unsortierten Daten erstellen, was sehr kostspielig ist. die Verwendung von benutzerdefinierten Zuordnern wird viel helfen). Ich weiß nicht, welche Form Ihre Eingabe nimmt, aber es ist möglich, dass Sie Ihre Eingabe direkt sortieren können, ohne sie zu kopieren, und dann set_difference direkt darauf ausführen. (Das wäre leicht zu tun, wenn Ihre Eingabe zumindest ein Array oder ein STL-Container ist.)
Einer der Hauptvorteile der STL ist, dass sie so flexibel ist, dass sie nahezu jede Eingabesequenz verarbeiten kann. In C # müssen Sie die Eingabe in eine Liste oder ein Dictionary kopieren, aber in C ++ können Sie möglicherweise std::sort und set_intersection auf der unformatierten Eingabe ausführen.
Versuchen Sie schließlich, den Code über einen Profiler auszuführen und genau zu sehen, wo die Zeit verbracht wird. Sie können auch versuchen, den Code stattdessen über GCC auszuführen. Ich habe den Eindruck, dass die STL-Leistung in MSVC manchmal ein bisschen schrullig ist. Es könnte sich lohnen, unter einem anderen Compiler zu testen, nur um zu sehen, ob Sie ähnliche Zeiten dort bekommen.
Schließlich finden Sie diese Blogposts relevant für die Leistung von C ++ vs C #: Ссылка
Die Moral von diesen ist im Wesentlichen, dass ja, Sie können bessere Leistung in C ++ bekommen, aber es ist eine erstaunliche Menge an Arbeit.
Ein Problem, das ich sofort sehe, ist, dass Sie die Mengen in C ++ als Wert und nicht als Konstante übergeben. Sie kopieren sie also jedes Mal, wenn Sie sie weitergeben!
Ich würde auch keinen Satz für das Ziel von set_intersection verwenden. Ich würde etwas wie
Dieser Code wird jedoch immer noch innerhalb der Funktion zugewiesen. Noch schneller wäre
%Vor%Und dann Scratch zuweisen, bevor Sie den Timer starten.
Wenn Sie nur nach der Größe suchen, kann eine handgeschriebene for-Schleife in Kombination mit set :: find noch bessere Ergebnisse liefern.
Ich würde den C ++ "runIntersectionTest" ändern, um Const-Referenzen auf die Container zu nehmen, statt sie bei jedem Aufruf kopieren zu lassen. (Der C # -Code verwendet Refs.)
Es kann sich auch lohnen, den Boost-Container Disjoint Set zu betrachten, welches speziell für bestimmte Arten von großen Mengenoperationen optimiert ist.
Es funktioniert, indem eine Gruppe von Mengen als Vereinigungen mehrerer disjunkte Mengen behandelt wird, was es möglich macht, andere Mengen, wie Kreuzungen oder Vereinigungen sehr billig zu bauen, sobald die ursprüngliche Menge von disjunkten Mengen konstruiert ist. Wenn Sie erwarten, viele Set-Operationen an Sets durchzuführen, die sich nicht viel ändern, können Sie wahrscheinlich erwarten, dass dies sehr schnell geht. Wenn Sie andererseits jedes Set einmal benutzen und wegwerfen, wird es wahrscheinlich nicht zu viel tun.
Wie auch immer, du würdest dir selbst einen Gefallen tun, um wenigstens damit zu experimentieren, um zu sehen, ob es dir in deinem speziellen Fall einen Stoß gibt.
Übrigens, wenn Sie große sortierte Mengen haben, ist std :: set_intersection nicht der schnellste Algorithmus. std :: set_intersection benötigt bis zu 2 * (m + n) -1 Vergleiche, aber Algorithmen wie der von Baeza-Yates können schneller sein. Für kleine m ist Baeza-Yates O (m * log (n)), während für n = alpha * m O (n) ist. Die Grundidee besteht darin, eine Art 2-seitige binäre Suche durchzuführen.
Experimentelle Analyse eines schnellen Schnittalgorithmus für sortierte Sequenzen Ricardo Baeza-Yates und Alejandro Salinger
ODER
R. Baeza-Yates. Ein Fast Set Intersection Algorithmus für sortierte Sequenzen. Im Proceedings des 15. jährlichen Symposiums über kombinatorische Pattern Matching (CPM 2004), Springer LNCS 3109, S. 400-408, Istanbul, Türkei, Juli 2004.
Unten finden Sie eine Erklärung und eine Implementierung von Erik Frey, wo er mit einer binären Sonde signifikant schnellere Ergebnisse als mit std :: set_intersection zeigt. Ich habe seinen Code noch nicht ausprobiert.
Ссылка
;
%Vor%
// probe.hpp
/ ** * binäre Sonde: Wählen Sie das nächste Element, indem Sie den halben Punkt zwischen niedrig und hoch wählen * / Vorlage & lt; Klasse RandomAccessIterator, Klasse T & gt; struct binary_probe { RandomAccessIterator operator () (RandomAccessIterator begin, RandomAccessIterator end, const T & amp; value) { Rückkehr beginnen + ((Ende - Anfang) & gt; & gt; 1); } };
/ ** * lower_bound: wie stl's lower_bound, aber mit verschiedenen Arten von Sondierungen * Beachten Sie das Aussehen der seltenen Vorlagenvorlage! * / Vorlage & lt; Template-Klasse Probe, Klasse RandomAccessIterator, Klasse T & gt; RandomAccessIterator lower_bound (RandomAccessIterator begin, RandomAccessIterator end, const T & amp; value) { RandomAccessIterator-Grube; Sonde & lt; RandomAccessIterator, T & gt; pfunc; // Probe-Funktor (will funktionieren)
while (Anfang & lt; Ende) { pit = pfunc (Anfang, Ende, Wert); if (* pit & lt; Wert) begin = Grube + 1; sonst Ende = Grube; } Rückkehr beginnen; }
/ * * diesmal mit einem Komparator! * / Vorlage & lt; Template-Klasse Probe, Klasse RandomAccessIterator, Klasse T, Klasse Comparator & gt; RandomAccessIterator lower_bound (RandomAccessIterator begin, RandomAccessIterator end, const T & amp; value, Comparator cmp) { RandomAccessIterator-Grube; Sonde & lt; RandomAccessIterator, T & gt; pfunc;
while (Anfang & lt; Ende) { pit = pfunc (Anfang, Ende, Wert); if (cmp (* pit, Wert)) begin = Grube + 1; sonst Ende = Grube; } Rückkehr beginnen; }
Da Sie Visual Studio verwenden, sollten Sie überprüfen, ob _SECURE_SCL auf 1 gesetzt ist (normalerweise, wenn Sie es nicht explizit festgelegt haben, ist es 1). Wenn es gesetzt ist, wird der gesamte STL-Code auch in Release-Builds range-geprüft. In der Regel wird der Code um 10-15% verlangsamt.
Es scheint, dass Microsoft nicht wusste, dass zum Beispiel std :: vector bereits eine Schnittstelle hat, wenn Sie die Bereichsüberprüfung wünschen: std :: vector :: at ()!
(Entschuldige, ich musste es von meiner Brust nehmen).
Wie auch immer, die größte Ineffizienz ist, dass Sie die Container kopieren, anstatt sie nach Wert zu übergeben. Verwenden Sie Referenzen zu (versuchen Sie es) vergleichen Sie Äpfel und Äpfel statt Äpfel und Bananen.
Ich weiß, dass Ihre Lösung gut funktioniert, aber Sie haben versucht, die STL-Implementierungen zu verwenden:
Es könnte bereits für Ihre Platform optimiert sein, also würde ich es versuchen
Ok, nach vielen Rückmeldungen habe ich die ursprüngliche Frage mehrmals aktualisiert:
Das Ergebnis davon ist, dass C # immer noch ~ 5x schneller ist als C ++.
Vielen Dank für Ihre Ideen / Vorschläge.
Aktualisierung:
Ich habe den set_intersection-Code modifiziert, um Vektoren zu verwenden, und um sie zu sortieren (anstatt die sortierte Mengenklasse zu verwenden), und jetzt ist es VIEL schneller:
%Vor%Beachten Sie: Der größere Satz wird sortiert erstellt, sodass die Sortierung in diesem Beispiel nicht viel Zeit in Anspruch nehmen kann.
C ++ Code:
%Vor%Sie übergeben die Vektoren immer noch nach Wert. Was wäre in Ordnung, wenn Sie sie nicht auch kopieren würden.
Inserter hat die Werte nicht am Ende des Vektors platziert, wo es schnell ist. Es tat dies nur bei der ersten Einfügung, danach fügte es den Wert am Anfang des Arrays ein (wo das Ende verwendet wurde).
Sie haben den Wert in der Hash-Map-Version zweimal nachgeschlagen, als Sie den Wert aktualisiert haben. Warum wird dieses Wert-Ereignis aktualisiert?
Führe diesen Code aus und poste deine Timings.
%Vor%Neueste Benchmark:
%Vor%Ich denke, der Unterschied zwischen 504 und 495 tritt auf, weil es ein paar Duplikatwerte gibt.
%Vor%Tags und Links c++ stl performance intersection