Datenstruktur für Schnittmenge festlegen?

19

Gibt es eine Datenstruktur, die eine Sammlung von Mengen (von endlichen Mengen) verwaltet, die die folgenden Operationen unterstützt? Jede sublineare Laufzeit wird geschätzt?

  1. Initiere ein leeres Set.
  2. Fügen Sie einem Set ein Element hinzu.
  3. Geben Sie bei zwei Sätzen an, ob sie sich überschneiden.
Dawei Huang
quelle
1
Dies ist eine sehr allgemeine Frage, da jede Datenstruktur diese Operationen mit endlicher Domäne unterstützen kann. Könnten Sie etwas genauer sein? Z.B. Welche Komplexität benötigen Sie, was sind Sie bereit zu opfern, um Set-Operationen usw. zu bekommen
Bartosz Przybylski

Antworten:

12

Wenn in jeder Gruppe eine Aufzeichnung darüber geführt wird, welche anderen Gruppen vorhanden sind, und Sie insgesamt Gruppen haben, können Sie jede Datenstruktur für eine Sammlung ( z. B. binäre Suchbäume usw. ) auf einfache Weise in eine Datenstruktur umwandeln, auf die Sie zugreifen können ein Element der Schnittmenge zweier Mengen in der Zeit O ( log s ) .s>0O(logs)

  • Jeder Satz sollte eine eindeutige Kennung von einem vollständig bestellten Satz haben. Wenn Sie Ihre Mengen explizit benennen , könnte der Bezeichner nur der Index sein.S1,S2,

  • Sie sollten eine "Registrierung" der Sätze implementieren; eine Datenstruktur, die eine Sammlung aller von Ihnen definierten Mengen verwaltet. Die Registrierung sollte als Suchbaum-Datenstruktur implementiert werden, um ein einfaches Abrufen ( z. B.  wenn Sie die Menge löschen möchten) und ein lineares Durchlaufen der Mengen zu ermöglichen.

  • Jede Menge auch einen "Index" jeder der anderen Mengen - keine Kopie davon, sondern eine Datenstruktur, die durch die Bezeichnungen der anderen Mengen indiziert wird. Dieser Index wird verwendet, um für jede Menge S k einen binären Suchbaum aller Elemente von S jS k zu führen . (Die beiden Mengen S j und S k teilen sich eine Kopie dieses Suchbaums.)SjSkSjSkSjSk

Initialisierung

Initialisierung eines Satzes besteht aus O ( 1 ) Operationen des Tree seiner Elemente zu initialisieren, O ( s ) Operationen wie Sie initialisieren ( das Kopieren aus der Registrierung) der Index für den Satz T und O ( s log s ) Operationen, während Sie die Registrierung durchlaufen, um T zu den Indizes jeder der anderen Mengen S j hinzuzufügen . Im Index von T erstellen wir Suchbäume, die T S j = ∅ darstellenT=O(1)O(s)TO(slogs)TSjTTSj=für die anderen Mengen ; Wir kopieren den gleichen Zeiger für den Index von S j .SjSj

Hinzufügen eines Elements zu einer Menge T

Das Addieren von zu der Menge T benötigt wie üblich die Zeit O ( log n T ) , wobei n T = | T | . Wir testen auch die Zugehörigkeit von x in jeder der anderen Mengen S 1 , S 2 , ... , die Zeit O ( log n S 1 + log n S 2 + ) O ( s log n) benötigtxVTO(lognT)nT=|T|xS1,S2, wobei n = | V | ist die Größe des Universums (oder der größten Menge S j ) und s ist die Anzahl der Mengen in der Registrierung. Fügen Sie für jede Menge S j, so dass x S j ist , auch x in den Index für die Menge S jT ein . Für jeden solchen Satz S j , nimmt diese O ( log s + log n T ) Zeit, zu sehen S j

O(lognS1+lognS2+)O(slogn),
n=|V|SjsSjxSjxSjTSjO(logs+lognT)Sjim Index von und x in S jT einzufügen ; über alle Mengen S 1 , S 2 , ... hinweg dauert dies Zeit O ( s log s + s log n T ) . Wenn wir annehmen, dass die Anzahl der Mengen S j viel kleiner ist als die Größe des Universums V (dh wenn wir annehmen, dass s n ist ), beträgt die Gesamtzeit für das Einfügen des Elements O ( s log n ).TxSjTS1,S2,O(slogs+slognT)SjVsnO(slogn).

Wenn Sie keine Duplikate in Sets ermöglichen, können wir die Zeit in dem Fall , dass speichern bereits durch den Verzicht auf die Mitgliedschaft Tests und Einfügungen für die anderen Sätze T . "Einfügen" in dem Fall, dass x bereits vorhanden ist, dauert dann nur noch O ( log n T ) .xSTxO(lognT)

Schnittpunktprüfung

Der Index jedes Satzes wird genau beibehalten, um eine schnelle Beurteilung zu ermöglichen, ob sich zwei Sätze und S k schneiden oder nicht . Für eine Menge S j können wir , indem wir einfach ihren Index für die Menge S k prüfen , nicht nur in der Zeit O ( log s ) bestimmen, ob S j S k schneidet oder nicht , sondern wir können auch einen Binärbaum abrufen, der die gesamte Menge enthält S jS k .SjSkSjSkO(logs)SjSkSjSk

Elemententfernung

Um ein Element aus einer Menge T zu löschen , entfernen wir es nicht nur aus dem Suchbaum für T selbst, sondern aus jedem der Schnittpunkte S jT für die Mengen S j in seinem Index. Dies dauert Zeit O ( s log n T ) , wobei n T = | T | .xTTSjTSjO(slognT)nT=|T|

Löschung einstellen

Aufgrund des mit dem Durchsuchen der Registrierung verbundenen Aufwands ist es möglicherweise wünschenswert, Sätze zu löschen, sobald sie nicht mehr benötigt werden. Durch die gesamte Registrierung durchlaufen, können wir löschen aus dem Index aller anderen Sätze S j in der Zeit O ( s n T ) , dominiert von den Kosten für das Löschen der Suchbaum darstellt S jT für jedes der anderen Sätze S j mit n T = | T | .SSjO(snT)SjTSjnT=|T|

Bemerkungen

Wenn Sie nur mit einer konstanten Anzahl von Sätzen rechnen, reduzieren sich die oben genannten Laufzeiten auf:

  • Initialisierung: O(1)

  • Elementeinfügung: O(logn)

  • Kreuzungstest (und Abruf der Kreuzung): O(1)

  • Elemententfernung: O(lognT)

  • Löschung festlegen: O(nS)

Dabei ist die Größe der größten Menge in der Registrierung und n T = | T | für den Satz T, an dem Sie arbeiten.nnT=|T|T

O(|V|)VSTS

Niel de Beaudrap
quelle
5

Es gibt Datenstrukturen, mit denen Sie dies auch bei Eingaben im ungünstigsten Fall in weniger als linearer Zeit tun können. Siehe http://research.microsoft.com/pubs/173795/vldb11intersection.pdf (und die dort angegebenen Artikel).

Wenn Ihre beiden Mengen S und T einen großen Schnittpunkt haben und Sie ein Wörterbuch für S haben, sollten Sie schnell ein gemeinsames Element finden, indem Sie die Elemente von T in zufälliger Reihenfolge nachschlagen. Der schwierigste Fall ist, wenn die Schnittmenge 0 oder 1 ist.

Rasmus Pagh
quelle
3

Normalerweise unterstützt Ihre Programmiersprache eine Datenstruktur mit eindeutigen Elementen. Im Allgemeinen gibt es drei gängige Ansätze: Bäume, Hashes und Bitmasken. Tree-Elemente müssen vergleichbar sein, Hash-Elemente müssen hashbar sein und Bitmask-Elemente müssen eine Art Umwandlung in Ganzzahlen aufweisen.

Ein Tree-Set unterstützt das Einfügen in O (log n) und das Testen von Schnittpunkten in Worst Case O (n log n).

Ein Hash-Set unterstützt das Einfügen in Amortized O (1 * h), wobei 'h' die Laufzeit des Hash-Algorithmus ist, und den Schnittpunkttest in Worst Case O (n).

Bitmaskensätze werden im Allgemeinen nicht wie Baum- und Hash-Sätze verwendet.

Karl Damgaard Asmussen
quelle
2
Dies wäre eine anständige Stack Overflow- Antwort, aber hier möchten wir einige Details darüber, wie und warum es funktioniert.
Raphael
3

Wenn Ihr Fall falsch positive Antworten zulässt, würde ich Bloom Filter mit einer einzelnen Hash-Funktion verwenden.

Sie können es wie folgt implementieren:

Initiere ein leeres Set

  • Bnn

Fügen Sie einem Set ein Element hinzu.

  • B[hash(element)]=1

Geben Sie bei zwei Sätzen (B1, B2) an, ob sie sich überschneiden.

  • B1 AND B2 = 0

Komplexität

  • nO(1)
Grisha Weintraub
quelle