Der Unterschied zwischen zwei vector A und B

Question

Ich habe zwei vector<MyType*> Objekte genannt A und B bekam. Die MyType Klasse hat ein Feld ID und ich möchte die MyType* erhalten, die in A sind aber nicht in B. Ich arbeite an einer Bildanalyse-Anwendung und ich habe gehofft, dass eine schnelle / optimierte Lösung zu finden.

Answer 1

Der ungeordnete Ansatz wird typischerweise quadratische Komplexität, wenn die Daten vorher sortiert (durch Ihr ID-Feld), in welchem ??Fall es linear und würde erfordert nicht wiederholt durchsucht B.

struct CompareId
{
    bool operator()(const MyType* a, const MyType* b) const
    {
        return a>ID < b->ID;
    }
};
...
sort(A.begin(), A.end(), CompareId() );
sort(B.begin(), B.end(), CompareId() );

vector<MyType*> C;
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C) );

Eine andere Lösung ist eine geordnete Container wie std verwenden :: Set mit CompareId für die StrictWeakOrdering Template-Argument verwendet. Ich denke, das wäre besser, wenn Sie eine Menge von Mengenoperationen anwenden müssen. Das hat seinen eigenen Kopf (als ein Baum), aber wenn Sie wirklich, dass finden ein Effizienzproblem sein, könnten Sie einen schnellen Speicherzuordner implementieren Elemente einzusetzen und zu entfernen super schnell (Anmerkung: Dies ist nur möglich, wenn Sie das Profil und bestimmen zu ein Engpass).

. Achtung: in etwas kompliziert Gebiet bekommen

Es gibt eine andere Lösung, die Sie betrachten können, die sehr schnell sein könnten, wenn anwendbar, und Sie haben nie Sorgen um Daten zu sortieren. Grundsätzlich stellen jede Gruppe von MyType Objekte, die die gleiche ID-Speicher einen gemeinsamen Zähler Anteil (ex: Zeiger auf unsigned int).

Dies wird eine Karte von IDs Zähler erfordern das Erstellen und erfordern Abrufen der Zähler von der Karte jedes Mal, wenn ein MyType Objekt auf die ID erstellt basiert. Da Sie MyType Objekte mit doppelten IDs haben, sollten Sie nicht so oft auf die Karte einfügen, wie Sie erstellen MyType Objekte (die meisten wahrscheinlich nur einen vorhandenen Zähler holen).

Zusätzlich dazu, einen globalen ‚Traversal‘ Zähler, der erhöht wird, wenn es geholt ist.

static unsigned int counter = 0;
unsigned int traversal_counter()
{
    // make this atomic for multithreaded applications and
    // needs to be modified to set all existing ID-associated
    // counters to 0 on overflow (see below)
    return ++counter;
}

Nun gehen wir zurück, wo Sie A und B-Vektoren haben MyType * speichern. Um die Elemente in einem Abruf, der nicht in B sind wir erste Anruf traversal_counter (). Unter der Annahme, es ist das erste Mal, dass wir es nennen, das gibt uns einen Traversal-Wert von 1

Jetzt durch Iterierte jeden MyType * Objekt in B und setzte die gemeinsamen Zähler für jedes Objekt von 0 auf den Wert Traversal, 1.

Jetzt durch Iterierte jeden MyType * Objekt in A. Diejenigen, die einen Zählerwert aufweisen, der nicht mit dem aktuellen traversal Wert übereinstimmt (1) sind die Elemente in A, die nicht in B enthalten ist.

Was passiert, wenn Sie überfluten den Traversal Zähler? In diesem Fall wir durchlaufen alle Zähler in der ID-Karte gespeichert und setzen sie zusammen mit dem Traversal Zähler selbst auf Null zurück. Dies wird nur noch einmal treten bei etwa 4 Milliarden Querungen, wenn es eine 32-Bit unsigned int.

Hier geht es um die schnellste Lösung, die Sie auf Ihr bestimmtes Problem anwenden können. Es kann in der linearen Komplexität auf unsortierte Daten eines beliebige Menge Betrieb tun (und immer, nicht nur in Best-Case-Szenarien wie eine Hash-Tabelle), aber es hat einige Komplexität einführen, so dass es nur prüfen, wenn Sie es wirklich brauchen.

Answer 2

Sortieren beider Vektoren ( std::sort ) nach ID und dann verwenden std::set_difference . Sie müssen eine benutzerdefinierte Komparator definieren, um diese beiden Algorithmen passieren, zum Beispiel

struct comp
{
    bool operator()(MyType * lhs, MyType * rhs) const
    {
        return lhs->id < rhs->id;
    }
};

Answer 3

Erster Blick auf das Problem. Sie wollen "alles in A nicht in B". Das heißt Sie gehen „alles in A“ zu besuchen zu haben. Sie werden auch zu Besuch alles in B haben Kenntnis davon zu haben, was ist und nicht in B., so dass es schlägt vor, sollte eine O(n) + O(m) Lösung sein, oder die Freiheit, dass die Differenz zwischen n und m, O(2n) elide.

Lassen Sie uns betrachten die std::set_difference Ansatz. Jede Art ist O(n log n) und set_difference ist O(n). So der Art-Art-set_difference Ansatz ist O(n + 2n log n). Nennen wir, dass O(4n).

Ein weiterer Ansatz auf dem ersten Platz in einem Satz die Elemente von B sein würde (oder Karte). Iteration über B ist der Satz O(n) zuzüglich Einfügungs O(log n) jedes Element zu erzeugen, gefolgt von Iteration über eine O (n), mit einer Lookup für jedes Element von A (log n), ergibt insgesamt: O(2n log n). Nennen wir, dass O(3n), die etwas besser ist.

Schließlich mit einem unordered_set (oder unordered_map) und unter der Annahme, wir durchschnittlichen Fall von O(1) Insertion und O(1) Nachschlag bekommen, haben wir einen Ansatz, den O(2n) ist. A-ha!

Der eigentliche Sieg hier ist, dass unordered_set (oder Karte) ist wahrscheinlich die natürlichste Wahl, um Ihre Daten in erster Linie zu vertreten, das heißt, die richtige Gestaltung ergibt die optimierte Implementierung. Dass nicht immer der Fall, aber es ist schön, wenn es funktioniert!

Answer 4

Wenn B bereits vorhanden auf A, dann während A bevölkern, können Sie in einem C-Vektor bookkeep.