Effiziente Reihe Schnittpunkt einer Sammlung von Sätzen in C++

Habe ich eine Sammlung von std::set. Ich möchte zu finden, die Schnittmenge aller sets in dieser Sammlung, in der schnellsten Art und Weise. Die Anzahl der Sätze in der Sammlung ist in der Regel sehr klein (~5-10), und die Anzahl der Elemente in jedem Satz ist in der Regel weniger als 1000, kann aber gelegentlich gehen bis etwa 10000. Aber ich brauche zu tun diese Kreuzungen Zehntausende von Zeit, so schnell wie möglich. Ich versuchte benchmark ein paar Methoden wie folgt:

In-place-Kreuzung in eine std::set Objekt, das zunächst kopiert den ersten Satz. Dann für den folgenden Sätzen, es iteriert über alle element der selbst-und der I-TEN Reihe von der Auflistung und entfernt Elemente aus sich selbst, wie benötigt werden.
Mit std::set_intersection in eine temporäre std::set -, swap-Inhalte zu einem aktuellen Satz, dann wieder suchen Schnittpunkt der aktuelle Satz mit dem nächsten Satz und einfügen in die temp einstellen, und so weiter.
Manuell iterieren über alle Elemente aller Mengen, wie in 1), aber mit einem vector als Ziel-container statt std::set.
Gleichen wie in 4, aber mit einem std::list statt einer vector den Verdacht, dass ein list wird eine schnellere Löschungen aus der Mitte.
Mit hash-sets (std::unordered_set) und überprüfen Sie für alle Elemente in allen sets.

Wie sich herausstellte, mit einem vector ist geringfügig schneller, wenn die Anzahl der Elemente in jeder Gruppe ist klein, und list ist geringfügig schneller für größere sets. In-place-mithilfe set ist wesentlich langsamer als die beiden, gefolgt von set_intersection - und hash-sets. Gibt es einen schnelleren Algorithmus/datastructure/tricks das zu erreichen? Ich kann nach code-snippets, falls erforderlich. Danke!

Die Frage hängt wirklich davon ab, ob oder nicht von Ihnen erwartet, finden viele gemeinsame Elemente, oder nicht, wie dies verändert die "beste" Struktur, die man mit oben kommen kann. Zum Beispiel, ein 6. Methode ist einfach zu benutzen und std::unordered_map und zählen der Anzahl der vorkommen der einzelnen Elemente. Es ist O(N) und die Gesamtzahl der Elemente. Sie dann, wählen Sie nur die Elemente, die insgesamt gleich der Anzahl der Sätze, O(M) die Anzahl der unterschiedlichen Elemente. Keine Ahnung, wie gut es durchführen würde.
Ich sehe. Ich geben diesem einen Versuch, obwohl ich vermute, es wird nicht schneller sein als ein std::list durch das hashing und die sonstigen Gemeinkosten. Danke!
Dieser Methode geben Sie die Ergebnismenge in unsortierter Reihenfolge. Zum Glück habe ich zwei Anwendungsfälle, eines für das Ergebnis in der Reihenfolge sortiert, und eine, die nicht. Wenn diese Methode ist Recht schnell, ich kann es atleast für den Fall, wo die Kreuzung ist nicht nötig, um sortiert werden.
Ich habe versucht, diesen Ansatz, und für meine Daten, das war nur geringfügig schneller als mein Ansatz 5 (mit unordered_set).
Sie könnten versuchen, die Idee. Schlimmsten Fall linear (lässt sich nicht vermeiden, dass, wenn die sets haben meist die gleichen Elemente), aber wenn die Schnittmenge klein ist, kann es viel schneller.
Danke!!! Aufgrund Dietmar, die Antwort unten, ich hatte auch darüber nachgedacht, eine binäre Suche wenn tut, Suche in arrays. Aber der Schlimmste Fall Verlangsamungen war eine Sorge. Sie schlagen vor, eine sehr schöne Heuristik/Einschätzung zu machen dies zu einem hybrid-Ansatz. In der Tat, dies ist nur geringfügig langsamer als die vector-Ansatz (pt 3 oben) durch kleine zusätzliche Berechnungen, aber klar der Schnellste unter allen, wenn Sie die Größen der nachfolgenden Sätze ist ausreichend größer als das aktuelle! Sehr schöne Idee!
Ich hätte akzeptiert, wenn es eine Antwort gab.
könnten wir einen Blick auf die Quelle des Tests?

InformationsquelleAutor Paresh | 2012-10-13

algorithm c++set-intersection stl

10

Möchten Sie vielleicht versuchen, eine Verallgemeinerung der std::set_intersection(): der Algorithmus ist die Verwendung von Iteratoren für alle sets:
1. Wenn jeder iterator erreicht hat end() des entsprechenden set sind Sie fertig. Es kann somit davon ausgegangen werden, dass alle Iteratoren sind gültig.
2. Nehmen Sie die erste iterator-Wert wie der nächste Kandidat-Wert x.
3. Bewegen Sie sich durch die Liste von Iteratoren und std::find_if() das erste element mindestens so groß, wie x.
4. Wenn der Wert größer ist als x machen es die neuen Kandidaten Wert und suchen Sie erneut in der Reihenfolge der Iteratoren.
5. Wenn alle Iteratoren sind auf Wert x Sie finden ein element der Schnittmenge: Notieren Sie, erhöhen Sie alle Iteratoren, starten Sie vorbei.
- Ich würde nicht empfehlen std::find_if wenn man die Arbeit mit std::set schließlich std::set verfügt sowohl std::lower_bound und std::upper_bound sind in der Regel schneller.
- nicht in diesem Fall find_if im Durchschnitt müssen nie vorher mehr als zwei Elementen und ist somit O (1), während ???er_bound ist O (log n).
- Offensichtlich hängt es von der Schnittstelle des Algorithmus und ich würde den Betrieb auf einer Sequenz von Paaren von Eingabe-Iteratoren: std::set_intersection() als auch nicht. Interessanterweise, ich denke, die Komplexität der vorgeschlagene Ansatz ist O((n log n) * m) : won ist die maximale Größe des sets und m ist die Anzahl der Sätze. Mein Algorithmus hat Komplexität O(n * m). Ich denke, dass meine Vorgehensweise gewinnt.
- Danke! Ich Verstand nicht, warum find_if im Durchschnitt müssen nie vorher mehr als zwei Elemente?
- wie Paresh ich Frage mich, wo die 2 Elemente kommen aus (ich könnte etwas fehlen offensichtlich). Es scheint mir, es würde davon abhängen, wie die Daten verteilt sind, wäre es nicht ? Zum Beispiel angenommen, als ich einen Satz von 100 Elementen und einem anderen von 1000 Elementen deckt das gleiche Spektrum. Dann, im Durchschnitt, ich muss Sie überspringen rund 10 Elemente aus dem großen set bei jedem Schritt.
- Matthieu M.: tatsächlich, das war ein heuristisches argument, denken Sie über ich bin nicht davon überzeugt, dass mehr. Dann hält es, wenn alle Sätze halten etwa die gleiche Anzahl von Werten aus der gleichen zufällige Verteilung, aber wenn Sie eines der sets passiert, haben ziemlich viele Werte zwischen den Werten der ersten Reihe, es funktioniert nicht auf diese Weise.
- Paresh: trotzdem, ich denke, es sollte auch im Durchschnitt für die Klasse der Distributionen für jeden Satz separat, aber ich bin mir nicht sicher, ob ich kann, beweisen es.
- Ich denke, es hängt wirklich von der Verteilung der Daten. Mit zwei Sätze von 100 und 10000 Elemente, jedes, mein Ansatz beinhaltet 100 lookups in der 10000-Elemente-set (13-Vergleiche jeweils im Durchschnitt), also etwa 1300 Vergleiche. Ihr Ansatz beinhaltet 200000 Vergleiche.
- Links mit dem gleichen Problem, werde ich brauchen, zu denken, es wieder zu kommen morgen mit einem klaren Kopf :/
- Ich muss zugeben, ich mag Ihre Lösung, vor allem, weil es so simpel ist. Aber es nervt mich irgendwie, dass das "beste" Algorithmus hätte lineare Komplexität beim sprechen über sortierte Daten. Ich meine, vorausgesetzt, eine gute hash-Funktion, ist es die gleiche Komplexität könnten Sie erwarten, dass aus der Verwendung einer hash-set/hash-map-base-Mechanismus; obwohl es am besten in Bezug auf die Speicherzuordnung offensichtlich, da Sie nicht die Zuweisung nichts.
- Die meisten basic-Algorithmus (gehen durch die erste set-element durch element und auf der Suche nach Elementen in allen anderen) hat Komplexität O (n * (log n)^m). Sie können sich wahrscheinlich bauen Sie einen effizienten Algorithmus, mit lower_bound.
- Wenn ich das richtig verstanden habe, in Schritt 4, wenn auch für einige iterator, der Wert ist größer als x können wir halten Sie suchen und behalten den größten Wert gefunden, bis zum Ende, und machen, dass die neue x. Habe ich Recht dazu?
- Ah! lower_bound benutzt binäre Suche. Aber der exponent sieht beängstigend aus! 🙂 Ich denke, wenn ich dies umzusetzen, werde ich versuchen mit den beiden find_if und lower_bound.
- Ja, ich empfehle nicht den naiven Ansatz. Allerdings hatten wir Zugriff auf die Interna von der set-iterator, könnten wir überspringen eine Reihe von vergleichen -> ich bin nicht überzeugt, dass die visitation Mechanismus, der hier (Links sub-tree, das element, den rechten Teilbaum) ist das beste, was wir erreichen können.
- Sorry, die Komplexität des grundlegenden Algorithmus sollte O (n * (m-1) * log n). Ich bezweifle jedoch, dass Sie besser als das, weil Sie wahrscheinlich nicht zu vermeiden Blick auf jedes element mindestens ein mal gestellt. Überlegen Sie, z.B., wobei die Schnittmenge von {1,3,5}, {1,3,5}, und {2,4,6}. Wenn Sie Pech haben, werden Sie erkennen, die "mismatch" nur zu haben als alle anderen sets, die in jeden Schritt des Algorithmus. Die effiziente Optimierung sein könnte, immer beginnend mit den kleinsten Satz (d.h. die mit der geringsten Anzahl von Elementen [Links]).
- ja, Sie können verwenden den größten nächsten cslue als der nächste Kandidat: kein anderer Wert csn vielleicht in thr Kreuzung. Auch, wenn die Größen des sets verfügbar sind, kann es sinnvoll sein, bestellen Sie Sie durch die Größe, auf der Suche nach Kandidaten, beginnend bei den kleinsten. Auf diese Weise mit größeren Schritten auf die größeren cintaibers mit logarithmischer Suche kann ein Vorteil sein.
- Whoa! Für meine Daten, das erwies sich als das langsamste bisher - irgendwo zwischen 5x bis 50x langsamer. Ich bin ziemlich sicher, dass die Umsetzung war anständig (oder wenigstens so anständig wie für die anderen Methoden). Ich denke, das extra-log n-Faktor ist wirklich die Tötung der Leistung. Das nächste element sollte mehr als wahrscheinlich sein, die sehr in der Nähe der aktuellen position, also die binäre Suche geht sehr in der Nähe der vollen log n Vergleiche, in der Erwägung, dass vielleicht find_if wäre schneller. Ich bin versucht, es zu ändern, verwenden find_if statt lower_bound, aber am stuck zu machen, einen Komparator für die Prüfung mit dem derzeit besten.
- Es muss etwas falsch ist dies tatsächlich so langsam! Es sollte schneller als die Verwendung mehrerer std::set_intersection(). Erstellen Sie ein geeignetes Prädikat, Sie sollten in der Lage sein zu verwenden std::bind1st(std::less_equal<T>(), x).
- Anstelle der Verwendung von find_if ich manuell inkrementiert den iterator bis zum entsprechenden Wert (ich denke find_if tut genau dies). Auf diese Weise, die Zeit gebracht wurde deutlich. Es ist jetzt schneller als die wiederholte set_intersection, aber immer noch langsamer als die beiden schnellsten (3 und 4 in Frage). Alles, was ich Tat, war zu ändern iterators[i] = lower_bound(iterators[i], sets[i].end(), currentValue, comparator); zu while (iterators[i] != sets[i].end() && *(*iterators[i]) > *currentValue) ++iterators[i]; das ist im Grunde ersetzen lower_bound durch find_if
- Bitte beachten Sie das set ist in absteigender Reihenfolge, damit die > Zeichen anstelle des erwarteten < sign. Auch das set besteht aus Zeigern, damit die Doppelzimmer de-Referenzierung.
- Ich vermute, auf Kosten der Komplexität des Codes, dieser kann schneller gemacht werden, in der folgenden Weise: Wenn wir einen x größer als der aktuelle besten, wir erlöschen alle vorherigen Prüfungen, und für die nachfolgenden Iterationen, die Suche für diese neue x. Am Ende der Liste, die wir wieder von vorne anfangen, da Sie ungültig geworden sind aufgrund der aktuellen x größer als das, was überprüft wurde, auf Sie. Dies führt zu großen Sprüngen (es sind die kleinen Sprünge, die Probleme verursacht für die log n lower_bound). Die weitere Verbesserung könnte sein, die Sie vorgeschlagen: um die sets (noch nicht gemacht, dass in diesem)
- Ich habe etwas mehr Graben, und fand, dass die massive Zunahme der Zeit für die lower_bound Ansatz war, weil ich war mit dem global/algorithmen lower_bound. Wenn ich eingeschaltet, um die std::set::lower_bound der Zeit sank drastisch, die vergleichbar mit wiederholten set_intersect. Allerdings war es noch nicht schnell genug, als das lineare Inkrement ähnlich find_if wie oben beschrieben. Ich nehme an, die zwei lower_bound Funktionen verwenden iterator anders (random vs vorwärts), oder eine solche Gründen.
- Mit etwas mehr Feintuning, die lower_bound (binäre Suche) Ansatz ist schneller als find_if (linear), wenn die Anzahl der Kreuzungen sind kleiner, aber langsamer, wenn die Anzahl der Kreuzungen ist groß. Ich denke, das ist zu erwarten. Insgesamt, diese sind nah, aber langsamer als die Ansätze 3 und 4 in Frage, aber viel schneller als die anderen Ansätze aufgeführt.
- Akzeptieren dies, da es Spielraum für weitere Optimierung, und kann verwendet werden, für die vorzeitige Beendigung, wenn für einen Anwendungsfall, nur die ersten paar Elemente der Schnittmenge sind erforderlich.
InformationsquelleAutor Dietmar Kühl
5

Nacht ist ein guter Berater und ich denke, vielleicht habe ich eine Idee 😉
- Speicher ist viel langsamer als die CPU in diesen Tagen, wenn alle Daten passen in den L1-cache keine große Sache, aber es ist leicht schwappt über L2 oder L3: 5 sets von 1000 Elementen ist bereits 5000 Elemente, d.h. 5000 Knoten, und einer Menge Knoten enthält mindestens 3 Zeigern + das Objekt (dh, mindestens 16 Byte auf einem 32-bit-Rechner und 32 Byte auf einem 64-bit-Maschine) => das ist mindestens 80k Speicher und die aktuellen CPUs nur noch 32k für die L1D so sind wir bereits verschütten in L2
- Die Vorherige Tatsache wird noch verstärkt durch das problem, die Knoten-sets sind wahrscheinlich die verstreut Speicher und nicht dicht gepackt zusammen, was bedeutet, dass ein Teil der cache-Zeile gefüllt ist, mit völlig anderen Sachen. Dies könnte abgemildert werden, indem, sofern eine Zuweisung, hält die Knoten in der Nähe der jeweils anderen.
- Und dies wird weiter durch die Tatsache verschärft, dass die CPUs sind viel besser als bei sequentiell liest (wo Sie können die prefetch-Speicher, bevor Sie es brauchen, so dass Sie nicht warten, bis es) eher als zufällig liest (und eine Baumstruktur, die leider führt zu Recht zufällig liest)
Dies ist der Grund, warum, wo Geschwindigkeiten Sache, ein vector (oder vielleicht ein deque) sind so große Strukturen: Sie spielen sehr gut mit der Erinnerung. Als solche, ich würde definitiv empfehlen die Verwendung von vector als unseren Vermittler-Strukturen; obwohl Pflege müssen getroffen werden, um immer nur einfügen/löschen von einer Extremität zu vermeiden Umzug.

Also dachte ich über einen Recht einfachen Ansatz:
```
#include <cassert>

#include <algorithm>
#include <set>
#include <vector>

//Do not call this method if you have a single set...
//And the pointers better not be null either!
std::vector<int> intersect(std::vector< std::set<int> const* > const& sets) {
    for (auto s: sets) { assert(s && "I said no null pointer"); }

    std::vector<int> result; //only return this one, for NRVO to kick in

    //0. Check obvious cases
    if (sets.empty()) { return result; }

    if (sets.size() == 1) {
        result.assign(sets.front()->begin(), sets.front()->end());
        return result;
    }


    //1. Merge first two sets in the result
    std::set_intersection(sets[0]->begin(), sets[0]->end(),
                          sets[1]->begin(), sets[1]->end(),
                          std::back_inserter(result));

    if (sets.size() == 2) { return result; }


    //2. Merge consecutive sets with result into buffer, then swap them around
    //   so that the "result" is always in result at the end of the loop.

    std::vector<int> buffer; //outside the loop so that we reuse its memory

    for (size_t i = 2; i < sets.size(); ++i) {
        buffer.clear();

        std::set_intersection(result.begin(), result.end(),
                              sets[i]->begin(), sets[i]->end(),
                              std::back_inserter(buffer));

        swap(result, buffer);
    }

    return result;
}
```
Scheint es richtig, kann ich nicht garantieren, seine Geschwindigkeit, obwohl, offensichtlich.
- Danke! Die Kompaktheit der Speicher war der Grund, ich habe versucht, die option 3 in der ursprünglichen Frage: mit einem vector als einen Zwischenbehälter, so wie Sie das getan haben. Der Unterschied ist, dass Sie verwendet die set_intersection, die erfordert zwei vectors, während ich gehalten 1 Vektor, mit dem Nachteil, dass musste ich löschen von der Mitte. Auch wenn Ihr Ansatz sollte idealerweise schneller gewesen, ich denke, die Komplex zusammenhängenden Faktoren wie Speicher, caching - (1-array vs 2) etc machen diese langsamer als die Optionen 3 und 4, die ich versuchte oben. Natürlich, Kilometerstand kann variieren, basierend auf den Daten.
- +1 für das denken in Bezug auf Speicher und Cache, und gibt eine schöne Erklärung! Als seitliche Anmerkung, ich überlege, die Verwendung von Vektoren anstelle von std::set und das einfügen in sortierter Reihenfolge in Vektoren, wenn das vergleichbar ist. Die Kompaktheit kann es ziemlich schnell und Kreuzungen wäre auf jeden Fall schneller sein.
InformationsquelleAutor Matthieu M.

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.