Berechnung der Mengenunterschiede zwischen zwei großen Mengen

14

Ich habe zwei große Mengen von ganzen Zahlen und BAB . Jeder Satz hat ungefähr eine Million Einträge, und jeder Eintrag ist eine positive ganze Zahl, die höchstens 10 Stellen lang ist.

Was ist der beste Algorithmus zur Berechnung von und B A ? Mit anderen Worten, wie kann ich die Liste der Einträge von A , die sich nicht in B befinden, effizient berechnen und umgekehrt? Was wäre die beste Datenstruktur, um diese beiden Mengen darzustellen und diese Operationen effizienter zu gestalten?ABBAAB

Der beste Ansatz ist, diese beiden Mengen als sortierte Listen zu speichern und jedes Element von linear mit jedem Element von B zu vergleichen . Können wir es besser machen?AB

user917279
quelle
Wenn Sie bereit sind, es anders zu speichern, können Sie möglicherweise bessere Ergebnisse erzielen.
Realz Slaw
Auch, wenn Sie bereit sind, die Ergebnisse als implizite Datenstruktur zu erhalten; Sie können einfach eine solche Struktur erstellen, die die beiden Mengen abfragt, um jede ihrer eigenen Abfragen zu beantworten.
Realz Slaw
1
@ user917279 Ein wichtiger Punkt ist: Sie können in der Regel die Vorverarbeitungs- / Konstruktionszeit, die Abfragezeit und die Speichernutzung gegeneinander abwägen. Bearbeiten Sie die Struktur selten, fragen Sie aber viel ab? Andersherum? Ist das Gedächtnis ein Problem oder nicht? Solche Fragen können aus praktischer Sicht beantwortet werden und geben Aufschluss über die Wahl des "richtigen" "theoretischen" Konstrukts.
Raphael
1
@Raphael Schlagen Sie vor, man könnte (in Bezug auf die Komplexität) eine bessere Leistung erzielen als die konsequent beständigen Mengen, indem man mehr Speicher verwendet und / oder mehr Zeit für die Vorbereitung aufbringt. Ich bin nur neugierig, ob Sie das für möglich halten. Ich sehe keine Nachschlagetabellen als Option für Eingabesätze dieser Größe.
Smossen
1
@ user917279 Betrachtet man das Beispiel von zwei großen Mengen, die identisch sind, dann würde jede mit Hash-Consing erstellte Datenstruktur den Gleichheitstest in O (1) unterstützen, da gleiche Strukturen beim Erstellen zusammengeführt werden und sich somit denselben Speicherort teilen. Die konsequent persistenten Mengen nutzen das Hash-Consing auch dann, wenn zwei Strukturen nahezu gleich sind. Die Komplexität ist die beste, die ich bisher für bestellte Sets gesehen habe.
Smossen

Antworten:

9

Wenn Sie bereit sind, die Mengen in einer spezialisierten Datenstruktur zu speichern, können Sie möglicherweise einige interessante Komplexitäten erhalten.

Sei I=O(min(|A|,|B|,|AΔB|))

Dann können Sie die Operationen und A Δ B jeweils in O ( I log | A | + | B |) setzenAB,AB,ABAΔBO(Ilog|A|+|B|I) erwartete Zeit. Sie erhalten also im Wesentlichen die minimale Größe der beiden Mengen oder die Größe der symmetrischen Differenz, je nachdem, welcher Wert geringer ist. Dies ist besser als linear, wenn der symmetrische Unterschied gering ist. dh wenn sie eine große Kreuzung haben. Tatsächlich ist dies für die beiden gewünschten Mengenunterschiedsoperationen praktisch ausgangssensitiv, da sie zusammen die Größe des symmetrischen Unterschieds ausmachen.

Siehe konfluent Persistent Sets und Karten von Olle Liljenzin (2013) für weitere Informationen.

Realz Slaw
quelle
Die Treaps in der Zeitung sind geordnete Suchbäume. Ich würde sie nicht als nicht sortierte Datenstrukturen zählen.
Smossen
@smossen stimmt, das habe ich rausgeschnitten.
Realz Slaw
6

Ein linearer Scan ist das Beste, was ich tun kann, wenn die Sätze als sortierte verknüpfte Listen dargestellt werden. Die Laufzeit ist .O(|A|+|B|)

Beachten Sie, dass Sie nicht jedes Element von paarweise mit jedem Element von B vergleichen müssen. Das würde zu einer Laufzeit von O ( | A | × | B | ) führenABO(|A|×|B|) , was viel schlimmer ist. Um die symmetrische Differenz dieser beiden Mengen zu berechnen, können Sie stattdessen eine Technik verwenden, die der "Zusammenführungs" -Operation in mergesort ähnelt und die so geändert wurde, dass Werte weggelassen werden, die beiden Mengen gemeinsam sind.

Im Einzelnen können Sie einen rekursiven Algorithmus wie den folgenden erstellen , um zu berechnen , vorausgesetzt, A und B werden als verknüpfte Listen mit ihren Werten in sortierter Reihenfolge dargestellt:ABAB

difference(A, B):
    if len(B)=0:
        return A # return the leftover list
    if len(A)=0:
        return B # return the leftover list
    if A[0] < B[0]:
        return [A[0]] + difference(A[1:], B)
    elsif A[0] = B[0]:
        return difference(A[1:], B[1:])  # omit the common element
    else:
        return [B[0]] + difference(A, B[1:])

Ich habe dies in Pseudo-Python dargestellt. Wenn Sie Python nicht lesen, A[0]ist es der Kopf der verknüpften Liste A, A[1:]der Rest der Liste und+ die Verkettung von Listen. Wenn Sie in Python arbeiten, möchten Sie es aus Effizienzgründen wahrscheinlich nicht genau so implementieren, wie oben beschrieben. Beispielsweise ist es möglicherweise besser, Generatoren zu verwenden, um das Erstellen vieler temporärer Listen zu vermeiden, aber ich wollte zeigen Ihnen die Ideen in möglichst einfacher Form. Der Zweck dieses Pseudocodes besteht nur darin, den Algorithmus zu veranschaulichen, und keine konkrete Implementierung vorzuschlagen.

Ich denke nicht, dass es besser geht, wenn Ihre Sets als sortierte Listen dargestellt werden und Sie möchten, dass die Ausgabe als sortierte Liste erfolgt. Man muss sich grundsätzlich jedes Element von und B ansehen . Informelle Rechtfertigungsskizze: Wenn es ein Element gibt, das Sie nicht angesehen haben, können Sie es nicht ausgeben. Daher können Sie nur dann auf die Betrachtung eines Elements verzichten, wenn Sie wissen, dass es sowohl in A als auch in B vorhanden ist. Aber woher wissen Sie, dass es vorhanden ist, wenn Sie seinen Wert nicht untersucht haben?ABAB

DW
quelle
Fantastisch, haben wir andere Möglichkeiten, wenn die Einschränkung, dass die Mengen als sortierte Listen gespeichert werden sollen, aufgehoben wird?
user917279
2

Wenn A und B gleich groß, disjunkt und verschachtelt sind (z. B. ungerade Zahlen in A und gerade Zahlen in B), ist der paarweise Vergleich von Elementen in linearer Zeit wahrscheinlich optimal.

Wenn A und B Blöcke von Elementen enthalten, die sich genau in A oder B oder in beiden befinden, ist es möglich, die Differenz, Vereinigung und Schnittmenge in sublinearer Zeit zu berechnen. Wenn sich beispielsweise A und B in genau einem Element unterscheiden, kann die Differenz in O (log n) berechnet werden.

http://arxiv.org/abs/1301.3388

smossen
quelle
1
Er sagt, dass die Sets sortiert sind, was bedeuten könnte, dass sie als Listen, Suchbäume oder etwas anderes gespeichert sind. Wenn Daten als Listen gespeichert werden müssen, ist es ziemlich uninteressant, nach dem "besten Algorithmus zum Berechnen von AB" zu fragen, wenn kein Algorithmus besser als das Durchsuchen der Listen in linearer Zeit (für den er bereits einen Algorithmus gefunden hat) geeignet ist.
Smossen
1
Meine Güte, du hast dasselbe Papier wie ich verlinkt (ich, genauso wie du, eher) ... nenne deine Links beim nächsten Mal: ​​D
Realz Slaw
@smossen fantastisch, soweit ich weiß (?), habe ich sie als sortierte Listen dargestellt, würde aber auch andere Vorschläge demütig begrüßen.
user917279
2

Eine Möglichkeit ist die Verwendung von Bitvektoren zur Darstellung der Mengen (wobei dienDie dritte Position stellt das Vorhandensein oder Fehlen eines Elements dar. Die Operationen vom Typ "Set" reduzieren sich dann auf Binäroperationen, die auf Digitalcomputern schnell (und mit mehreren Bits gleichzeitig) ausgeführt werden können. in diesem FallEIN-B = einb¯ wo ein,bsind die Bitvektoren. Die relative Effizienz dieser Technik gegenüber anderen Techniken hängt auch von der Sparsamkeit ab. Für dichtere Mengen kann es effizienter sein als andere Ansätze. Natürlich ist auch die gesamte Operation peinlich parallel, sodass festgelegte Operationen parallel ausgeführt werden können.

vzn
quelle
Mit 1010Eingabemöglichkeiten, Bitvektoren sind überhaupt nicht praktikabel.
Raphael
1
R., verpasst den Punkt. eine einzelne longkann 32 Elemente oder 1 byte, 8 Elemente speichern . 1M Einträge können also nur in ~ 125K RAM gespeichert werden! Der Speicher kann erheblich effizienter sein als andere Darstellungen, je nachdem, wie das Problem implementiert ist ...
vzn
Sie würden also über 12 MB für Sets benötigen, an denen das OP interessiert ist. Das bläst (derzeit) alle Caches und wird für spärliche Sets schrecklich sein. Insbesondere dominiert das Erstellen einer leeren Menge alle anderen Operationen (für dünn besetzte Mengen). Knuth spricht dieses Thema übrigens in TAoCP an.
Raphael
12 MB? huh? Plakat sagte, dass er nur 2 Sätze hat. Das Plakat gab nicht die Dichte seines Sets an. darauf wird in meiner Antwort hingewiesen. Nehmen Sie an, er hat spärliche Mengen? Es gibt keine One Correct Answer, der Ansatz wird als alternative Option aufgezeigt, die je nach den Umständen nützlich sein kann. es wird in diesem Zusammenhang nicht selten verwendet ...
vzn
Ich schlage vor, Sie lesen die Frage erneut: "Jeder Satz enthält ungefähr eine Million Einträge, und jeder Eintrag ist eine positive Ganzzahl, die höchstens 10 Stellen lang ist." Es gibt1010 verschiedene zahlen können vorkommen, und es gibt ungefähr 106diejenigen in der Liste. Das bedeutet, dass nur 0,01% aller Einträge in Ihrem Bitvektor 1 sind - das würde ich in der Tat als sehr spärlich bezeichnen. (Es stellte sich heraus, dass meine 12MB zu niedrig waren; du brauchst natürlich1010b1.15GB.)
Raphael