Effizienter Schnitt einer Sammlung von Mengen in C ++

Question

Effizienter Schnitt einer Sammlung von Mengen in C ++

9

Ich habe eine Sammlung von std::set . Ich möchte die Schnittmenge aller Sätze in dieser Sammlung auf die schnellste Weise finden. Die Anzahl der Sätze in der Sammlung ist normalerweise sehr klein (~ 5-10), und die Anzahl der Elemente in jedem Satz ist normalerweise kleiner als 1000, kann aber gelegentlich bis zu ungefähr 10000 gehen. Aber ich muss diese Schnittpunkte zig machen Tausende von Zeit, so schnell wie möglich. Ich habe versucht, einige Methoden wie folgt zu bewerten:

In-place-Schnittpunkt in einem std::set -Objekt, das zunächst den ersten Satz kopiert. Dann iteriert es für nachfolgende Mengen über alle Elemente von sich selbst und den i-ten Satz der Sammlung und entfernt bei Bedarf Elemente von sich selbst.
Verwenden Sie std::set_intersection in einem temporären std::set , tauschen Sie den Inhalt gegen einen aktuellen Satz aus, suchen Sie dann erneut den Schnittpunkt des aktuellen Satzes mit dem nächsten Satz und fügen Sie ihn in den Temp-Satz ein usw.
Iterieren Sie manuell über alle Elemente aller Sets wie in 1), aber verwenden Sie vector als Zielcontainer anstelle von std::set .
Wie in 4, aber mit std::list anstelle von vector , wird das Verdächtigen von list schnellere Löschvorgänge von der Mitte aus ermöglichen.
Verwenden von Hash-Sets ( std::unordered_set ) und Prüfen auf alle Elemente in allen Mengen.

Wie sich herausstellte, ist die Verwendung von vector geringfügig schneller, wenn die Anzahl der Elemente in jedem Satz klein ist, und list ist bei größeren Mengen geringfügig schneller. In-Place mit set ist wesentlich langsamer als beide, gefolgt von set_intersection und Hash-Sets. Gibt es einen schnelleren Algorithmus / Datenstruktur / Tricks, um dies zu erreichen? Ich kann Code-Snippets bei Bedarf bereitstellen. Vielen Dank!

algorithm c++ stl set-intersection

Paresh 13.10.2012, 18:57

quelle

2 Antworten

4

Die Nacht ist ein guter Ratgeber und ich denke, ich habe vielleicht eine Idee;)

Speicher ist heutzutage viel langsamer als CPU, wenn alle Daten in den L1-Cache passen, keine große Sache, aber es kann leicht auf L2 oder L3 übertragen werden: 5 Sätze von 1000 Elementen sind bereits 5000 Elemente, was 5000 Knoten bedeutet, und a Set-Knoten enthält mindestens 3 Zeiger + das Objekt (dh mindestens 16 Bytes auf einer 32-Bit-Maschine und 32 Bytes auf einer 64-Bit-Maschine) = & gt; das ist mindestens 80k Speicher und die letzten CPUs haben nur 32k für die L1D, so dass wir bereits in L2 verschüttet sind
Die vorherige Tatsache wird durch das Problem verschärft, dass Knoten wahrscheinlich im Speicher verstreut sind und nicht dicht gepackt sind, was bedeutet, dass ein Teil der Cache-Zeile mit völlig unabhängigem Inhalt gefüllt ist. Dies könnte erleichtert werden, indem ein Zuordner bereitgestellt wird, der Knoten nahe beieinander hält.
Und das wird noch dadurch verstärkt, dass CPUs viel besser bei sequentiellen Lesevorgängen sind (wo sie Speicher vorzeitig abrufen können, bevor Sie ihn brauchen, also warten Sie nicht darauf) und nicht zufällig gelesen werden (und eine Baumstruktur führt leider dazu zu ziemlich zufälligen liest)

Deshalb ist, wo Geschwindigkeit zählt, ein vector (oder vielleicht ein deque ) so großartige Strukturen: Sie spielen sehr gut mit dem Gedächtnis. Daher würde ich definitiv empfehlen, vector als unsere zwischengeschalteten Strukturen zu verwenden; Es muss jedoch darauf geachtet werden, dass nur eine Extremität eingefügt / gelöscht wird, um eine Verlagerung zu vermeiden.

Also habe ich über einen ziemlich einfachen Ansatz nachgedacht:

%Vor%

Es scheint korrekt zu sein, aber ich kann seine Geschwindigkeit natürlich nicht garantieren.

Matthieu M. 14.10.2012 12:12

quelle

Tags und Links algorithm c++ stl set-intersection

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Hervorhebung von js-code in der PHP-Datei

score 10 · Accepted Answer

Sie können eine Verallgemeinerung von std::set_intersection() versuchen: Der Algorithmus verwendet Iteratoren für alle Mengen:

Wenn ein Iterator die end() der entsprechenden Menge erreicht hat, sind Sie fertig. Daher kann angenommen werden, dass alle Iteratoren gültig sind.
Nimm den Wert des ersten Iterators als nächsten Kandidatenwert x .
Durchlaufen Sie die Liste der Iteratoren und std::find_if() das erste Element mindestens so groß wie x .
Wenn der Wert größer als x ist, machen Sie ihn zum neuen Kandidatenwert und suchen Sie erneut in der Reihenfolge der Iteratoren.
Wenn alle Iteratoren den Wert x haben, haben Sie ein Element der Schnittmenge gefunden: Zeichnen Sie es auf, inkrementieren Sie alle Iteratoren, beginnen Sie von vorne.