Wie berechne Differenz zwischen zwei Mengen, die in C?
Ich habe zwei arrays, sagen wir A und B mit |A|=8 und |B|=4. Ich will berechnen Sie den Unterschied zwischen A-B. Wie muss ich Vorgehen? Bitte beachten Sie, dass es keine wiederholten Elemente in den sets.
Edit: vielen Dank an alle für eine Vielzahl von eleganten Lösungen. Da bin ich noch in der Prototyp-Phase meines Projektes, für die ich jetzt implementiert die einfachste Lösung, sagte Brian und Owen. Aber ich Schätze die clevere Nutzung von Daten-Strukturen, wie Sie hier vorgeschlagen wird, indem der rest von Ihnen, Obwohl ich bin kein Informatiker sondern Ingenieur und nie studiert Datenstrukturen als natürlich. Sieht aus wie es ist an der Zeit, ich sollte wirklich anfangen zu Lesen CLRS, die ich schon so eine ganze Weile 🙂 nochmals vielen Dank!
- Es gibt keine solche Sache wie C-STL. Meinst du C++?
- Ich weiß. Ich wollte nur klarstellen, dass ich nicht wollte, STL-basierte Lösungen.
- Da die STL ist eine C++-einzige Sache, es ist genug zu sagen, du bist mit C und lassen Sie es zu, dass, wenn jemand die Antwort hat, empfehlen STL würden Sie downvoted (und das zurecht).
- Ich meine, nicht eine leichte gegen dich oder so, aber trotzdem ist es ein wenig komisch, wie Sie ging, um so große Schmerzen, um zu verhindern, dass Verwirrung, und dann—Hoppla!—die Dinge gingen in die andere Richtung und jemand verwirrt sowieso (Murphy ' s Law schlägt wieder zu, denke ich.)
- ist dieses Hausaufgaben?
- NÖ. Ich bin grad student und dieses problem kam in meiner Forschungsarbeit. Ich bisher verwendeten Python-sets für diesen Zweck, aber ich habe jetzt für die Implementierung in C.
- und BlueRaja, es ist ok und ich verstehe. Eigentlich habe ich wirklich wie wenn erfahrene Nutzer wie Sie Bearbeiten und korrigieren meine Fehler. Das ist alles, was stackoverflow ist!
- Was sind diese Sätze (Integer, strings,...)? Sind A und B sortiert? Wie groß sind Sie? (E. g-n^2-algorithmen zu tun? nlogn?) Wie oft brauchen Sie, um dieses set für einen Unterschied?
- A und B sind arrays von Zeigern (64-bit), die auf dynamisch zugewiesenen Objekte im Speicher, und Sie sind definitiv nicht sortiert. (Kann ich irgendwie Zeiger?) Um genau zu sein, Einer ist Größe 32 und B ist Größe 8 und diese ganze Betrieb eingestellt differenzierende getan werden Zehntausende von Zeit.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Iteriert über jedes element von A, wenn jedes dieser Elemente sind nicht in B, dann fügen Sie Sie zu einem neuen Satz C.
Bob das set ungeordnete (geben Sie eineO(n*m)Laufzeit) oder Sie können tun, eine binäre Suche aufBob das set bestellt (geben Sie eineO(n log m)Laufzeit)Sortieren von arrays A und B
das Ergebnis wird in ° C
lassen Sie sich ein - der erste elem Eines
lassen Sie b - die ersten elem B
dann:
1), während ein < b: insert a in C und a = Nächstes Element von A
2) während a > b: b = Nächstes Element von B
3) wenn a = b: a = Nächstes Element von A und b = Nächstes Element von B
4) wenn b geht zu Ende: rest einfügen von A zu C und stop
5) wenn eine geht zu Ende: stop
Es hängt davon ab, wie Sie wollen stellen Ihre sets, aber wenn Sie nur packed bits, dann können Sie bitweise Operatoren, z.B.
D = A & ~B;Ihnen würde der Unterschied zwischen A-B, wenn die sets passen in einen integer-Typ. Für größere Mengen verwenden Sie arrays von integer-Typen ein und iterieren, z.B.Im folgenden wird davon ausgegangen, die Sätze sind, werden als sortierte container (wie std::set).
Es ist ein weit verbreiteter Algorithmus für das Zusammenführen von zwei geordnete Listen zu einer Dritten. Die Idee ist, dass, wenn man sich die Köpfe der beiden Listen können Sie bestimmen, welche ist die untere, extrahieren, dass, und fügen Sie es der Schwanz von dem Ausgang, dann wiederholen.
Gibt es Varianten, welche die Erkennung der Fall, wo die zwei Köpfe gleich sind, und behandeln diese speziell. Set Kreuzungen und Gewerkschaften sind Beispiele dafür.
Mit einer Reihe asymmetrischer Unterschied, der entscheidende Punkt ist, dass für A-B, wenn Sie extrahieren Sie den Kopf von B, Sie verwerfen es. Wenn Sie ziehen den Kopf Ein, fügen Sie es an den Eingang , es sei denn den Kopf von B gleich ist, in welchem Fall extrahieren Sie das auch und verwerfen beide.
Obwohl dieser Ansatz ist konzipiert für sequential-access Daten-Strukturen (und tape-storage etc.), ist es manchmal sehr nützlich, das gleiche zu tun für einen random-access-Datenstruktur, so lange es halbwegs effiziente Zugriff sequentiell sowieso. Und du musst nicht unbedingt zu extrahieren Dinge für real - das können Sie kopieren und Schritt statt.
Der entscheidende Punkt ist, dass Sie Schritt für Schritt durch die Eingaben nacheinander, immer auf der Suche nach den niedrigsten Wert für die Verbleibende weiter, so dass (wenn die Eingänge haben keine Duplikate) Sie werden die übereinstimmenden Elemente. Sie daher immer wissen, ob Ihre nächsten niedrigsten Wert zu behandeln ist Ein Element aus einer mit kein match in B, und Artikel, die in B keine Entsprechung in Einer, oder ein Element, das gleich in beiden A und B.
Allgemein der Algorithmus für das set-Unterschied hängt von der Repräsentation des Satzes. Zum Beispiel, wenn das set wird dargestellt als ein bit-Vektor, der oben würde overcomplex und langsam Sie hatte gerade die Schleife durch die Vektoren zu tun bitweise Operationen. Wenn das set wird dargestellt als eine Hash-Tabelle (wie in der tr1 unordered_set) das oben ist falsch, da es erfordert bestellt Eingänge.
Wenn Sie haben Ihre eigenen binären Baum-code, die Sie verwenden für die sets, die eine gute Möglichkeit ist das konvertieren der beiden Bäume in verknüpften Listen, die Arbeit an den Listen, dann umwandeln des resultierenden Liste, um eine perfekt ausgewogene Struktur. Die verkettete Liste gesetzt-Unterschied ist sehr einfach, und die beiden Umbauten sind wiederverwendbar für andere ähnliche Operationen.
BEARBEITEN
Auf die Komplexität - mit diesen bestellt merge-algorithmen ist O(n), vorausgesetzt, Sie können tun, um die in-order traversals in O(n). Konvertierung in eine Liste und zurück ist auch O(n), wie jeder der drei Schritte ist in O(n) - Baum-Liste gesetzt-Unterschied und Liste-zu-Baum.
Baum-zu-Liste im Grunde genommen eine Tiefe-ersten traversal, die Dekonstruktion der Baum, wie es geht. Gibt es einen trick für die Herstellung dieser iterative, die Speicherung der "stack" in Teil-Knoten behandelt - das wechseln von einer linken-Kind-Zeiger in einer parent-Zeiger, kurz bevor Sie den Schritt zum linken Kind. Das ist eine gute Idee, wenn der Baum groß und unsymmetrisch.
Umwandlung einer Liste zu einem Baum, der im Grunde um einen depth-first-traversal von einem imaginären Baum (basierend auf der Größe, bekannt aus der start -) Gebäude es für real, wie Sie gehen. Wenn ein Baum hat 5 Knoten, zum Beispiel, können Sie sagen, dass der root-Knoten 3. Sie Rekursion zu bauen, ein zwei-Knoten Linker Teilbaum, dann greifen Sie das nächste Element aus der Liste für die Stamm -, dann die Rekursion zu bauen, einen zwei-Knoten-rechter Teilbaum.
Der Liste-zu-Baum-Konvertierung sollte nicht umgesetzt werden müssen iterativ - rekursive Ordnung ist als das Ergebnis ist immer perfekt ausbalanciert. Wenn Sie nicht umgehen kann die Rekursionstiefe log n, Sie kann das sicherlich nicht mit den vollen Baum sowieso.
Implementieren ein set-Objekt in C. kann Man es mit einer hash-Tabelle für die zugrunde liegenden Speicher. Dies ist offensichtlich eine nicht triviale übung, aber ein paar Öffnen Quelle Lösungen existieren. Dann müssen Sie einfach fügen Sie alle Elemente von A und dann die Iteration über B und entfernen Sie alle, die Elemente in Ihrem set.
Der entscheidende Punkt ist die Verwendung der richtigen Daten-Struktur für den job.
Für größere Mengen würde ich vorschlagen, die Sortierung der zahlen und Durchlaufen Sie durch die Emulation der code bei http://www.cplusplus.com/reference/algorithm/set_difference/ das wäre O(N*logN), aber da sind die Größen so klein ist, ist die Lösung gegeben durch Brian scheint in Ordnung, obwohl es theoretisch langsamer bei O(N^2).