Union / Kreuzung der 2 Sätze, wobei jeder Satz durch seine Untergruppen definiert sind

Question

Wir wissen, dass jeder Satz der Definition aus der Vereinigung von anderen Sätzen.

Zum Beispiel

A = B union {1,2}

B = C Union D

C = {5,6}

D = {5,7}

E = {4}

dann A = {1,2,5,6,7}

Eine Vereinigung E = {1,2,4,5,6,7}

Sind die alle effiziente Algorithmen zu tun. Angenommen, die Hierarchie der Gewerkschaften kann wirklich tief sein, und die Teilmengen können ziemlich oft ändern (nicht viel). Ich denke, es sollte Möglichkeiten zur Minimierung reduziert die Menge der Gewerkschaften sein, eine machen.

Answer 1

So haben Sie eine unveränderliche Hierarchie der Gewerkschaften haben Sätze zu ändern? Und Sie sind, wie in Ihrem Beispiel nur daran interessiert, den Wert eines Satzes?

Dann die Hierarchie flach. Das heißt, in Ihrem Beispiel würden Sie einmal zu Fuß durch die Hierarchie der Satz von wechselnden Sets Ihr Set die Vereinigung, und diesen Satz zu finden ist.

mit Neuberechnen Gewerkschaften zu verzichten, wenn sich ein Blattsatz ändert, können Sie für jedes Element verfolgen könnte, wie viele Sätze es derzeit enthalten. Dies kann schnell aktualisiert werden, wenn ein Blatt Änderungen eingestellt, und diejenigen, die an irgendwelchen unverändert Blattsätzen nicht erforderlich. Dann zählen die Elemente mit der Frequenz> 0 sind zur Zeit in der Union.

Answer 2

Vielleicht sind Sie auf der Suche nach einer Art von disjoint Satz Datenstruktur

Answer 3

Einige Fragen zu diesem Fall.

Erste Frage: Wie lange geht diese „Skript“ / „Programm“ hat zu laufen? Im Fall ist es nicht zu lang ist, könnte es auch eine gute Option, einfach vorherige Gewerkschaften und Überprüfung Cache zu speichern, bevor eine Gewerkschaft Aktion ausführen. Das Gedächtnis ist nicht so teuer heutzutage.)

Zweite Frage, die Sie stellen sollten: Elemente in einer bestimmten Reihenfolge vor Vereinigung? Wenn sie nicht, und eine Liste sind mehr als einmal zugegriffen wird, kann es sehr hilfreich sein, zunächst eine Liste zu sortieren (als Sie eine Entscheidung treffen können, wenn man nur auf halbe Strecke eine Liste ist, zum Beispiel). Mergesort ist eine leistungsfähige Technik der effizienten Join von zwei Listen bestellt.