Vereinigung von Mengen - suche effizienten Algorithmus

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo zusammen,

ich benötige eure Hilfe bei folgendem Problem:

Ich habe ca 100.000 Elemente die verschiedenen Mengen zugeordnet sind. Ein Element kann dabei in mehreren Mengen (ca. 30.000) enthalten sein.

Jetzt möchte ich folgendes machen:

Mengen, die über mindestens ein Element miteinander verbunden sind, sollen zusammengefasst werden.

Beispiel 1: Element A ist nur in Menge 1 vorhanden. Element B ist in Menge 1 und 5 vorhanden. In Menge 5 ist sonst noch das Element C vorhanden. Ergebnis: Elemente A,B,C werden zu einer Menge vorhanden.

Beispiel 2: In Menge 1 sind die Elemente A und B vorhanden. In Menge 2 die Elemente B und C, in Menge 3 die Elemente C und D. Ergebnis: Elemente A,B,C,D werden zu einer Menge zusammengefasst.

Wie kann ich das möglichst effizient hinbekommen? Wer hat eine Idee für einen Algorithums?

Grüße und Danke

power_blue

#2

Hallo,
es gibt zwei Ansätze: Für Mengen ohne Halbordnung nimmt man üblicherweise Hash-Tables; man geht einfach durch alle Mengen und fügt jeweils alle Elemente in eine gemeinsame Hashtabelle ein. Am Ende geht man die Hashtabelle durch, also man schreibt die nicht-leeren Buckets raus. Für diesen Ansatz braucht man natürlich eine Hashfunktion, die ein Element auf eine natürliche Zahl abbilden kann.

Für Mengen mit Halbordnung bieten sich Suchbäume an, hier ist die Auswahl groß, z.B. BSTs, B-Trees, etc. Der eigentliche Algorithmus ist ebenso trivial wie im Hash-Fall: Gehe durch alle Mengen, füge jeweils alle Elemente in einen gemeinsamen Baum. Am Ende gehe In-Order durch den Baum, also in der Reihenfolge, die durch die Halbordnung induziert wird.

Auf dem Papier ist die Hash-Table-Variante am schnellsten (O(n+m)), in der Praxis lohnt es sich bei den paar Elementen gar nicht irgendwas spezielles zu programmieren oder zu benutzen. Wie schon erwähnt, ist der eigentliche Algorithmus bei passender Wahl der Datenstruktur eigentlich trivial. Es gibt sogar Datenstrukturen, die speziell zur Vereinigung von Mengen entworfen wurden, z.B. der Fibonacci-Heap. Hier wäre der „Algorithmus“ besonders einfach: Füge die Elemente einer Menge in jeweils einen F-Heap, am Schluß benutze die „Merge“ Operation.

Die Schwierigkeit in der Praxis ist oft, eine geeignete Hash-Funktion oder eine geeignete Halbordnung zu definieren. In der Allgemeinheit, wie Du die Frage formuliert hast, kann man hier keine weiteren Hinweise geben.

#3

Als alte Datenbankerin würde ich das alles in eine einfache Datenbank schreiben, die dann diese Arbeit erledigen soll. Dafür sind Datenbanken da und können das vermutlich deutlich besser als jeder selbstgestrickte oder aus einem Lehrbuch abgetippte Ansatz.

Es gibt in allen halbwegs modernen Programmiersprachen Schnittstellen zu einfachen Datenbanksystemen. Das einfachste ist zumeist SQLite, das löuft rein lokal - teils auch in Memory - und braucht keinen dedizierten Server.

In was für einer Sprache willst du das überhaupt machen?

#4

Danke für die Denkanstöße.

Ich habe meine Implementierung jetzt angepasst, ist zwar etwas komplexer aber auch deutlich performanter.

Danke und Grüße

powerblue

#5

Hi,

das mit den Datenbanken würde funktionieren, aber mir steht leider nur Access (ja, gruselig) zur Verfügung. Mein Admin gibt mir nichts anderes…

Trotzdem machen auch Datenbanken das nicht voll allein, auch da müsste ja irgendwo ein effizeienter Algorithums herkommen.

Habe die Daten in Access, rechne aber alles im Speicher und schreibe nur das Ergebnis zurück. MIt der Geschwindigkeit, die ich jetzt erreicht habe, kann ich gut leben.

Grüße

Michael

#6

Natürlich. Aber echte Datenbanksysteme haben Optimizer, die den jeweils sinvollsten Algorithmus zur Abarbeitung deiner Joins selbst wählen. Wir müssen uns keine Illusion machen, dass wir als jeweils einzelne Programmierer da auch nur im Ansatz so gut sein können wie die Tausenden Entwickler bei Oracle und vormals Sun oder auch Microsoft mit ihrer Jet-Engine in Access. Für jede Mannstunde, die du da in deinen eigenen Ansatz investierst, hat Oracle/Sun schon längst 10.000 Mannstunden in MySQL investiert. Deren Code ist auch nicht neu (=risikobehaftet), sondern seit Jahren millionenfach im Einsatz. Ernsthafte Performanceschwächen fallen bei so vielen Nutzern schnell auf und werden korrigiert.

Was hast du denn konkret gemacht? Und mit Komplexität steigt immer auch das Fehlerrisiko. Eventuell kaufst du dir die höhere Performance irgendwann mit Datenverlusten ein, weil du nicht alle Grenzfälle bedacht hast.

#7

Guten Morgen,

im Grunde hast du natürlich recht. Aber Access ist für DB-Operationen nun wirklich nicht der Bringer. Habe vorher versucht das dort nur mit DB-Funktionen zu rechnen. Das hat aber ewig gedauert. Insbesondere wurden die durchzuführenden Abfragen mit fortschreitener Bearbeitung immer langsamer in der Ausführung. Das scheint wohl ein Access-Problem (mit den Meta-Daten?) zu sein.

Ich habe mir jetzt ein Dictionary (ist m. W. ja nur ein Hash-Table) mit den Elementen gefüllt, zu den Elementen speichere ich dort, in welchen Mengen sie vorhanden sind. Als zweites habe ich ein Dictionary mit den Mengen gefüllt, dort speichere ich, welche Elemente zur jeweiligen Menge gehörten.

Mit diesen beiden Dictionarys kann ich zusammengehörige Mengen um ein vielfaches schneller finden, als es vorher rein in der DB möglich war.

Mein ursprüngliches Problem war auch nicht irgendeine Form von Indexierung aufzubauen, das kann Access natürlich gut. Vielmehr ging (geht) es mir darum, möglichst schnell die jeweils zusammengehörigen Mengen zu finden und dann zusammenzufassen (wobei das Zusammenfassen natürlich das kleinste Problem ist).

Grüße

powerblue

#8

Das scheint eher ein Problem mit deinen Indizes zu sein. Oder deine Abfragen benutzen die Indizes nicht. 100.000 Zeilen ist für eine Datenbank nicht mal der Nennung wert.

Das glaube ich dir auch. Aber das bezahlst du mit Speicher und CPU-Cycles (=Strom). Bei Access ist bei 3GB RAM Schluss. Kann gut sein, dass du das mit deinen paar Zeilen recht schnell erreichst.

Naja, ich wollte nur deinen Blick auf alternative Lösungen lenken, die vermutlich besser mit der Datenmenge skaliert. Aber ob die Datenmenge zukünftig wächst, das weißt nur du. Viel Erfolg mit deiner Lösung.

#9

Hallo,

nach meinen Recherchen ist das tatsächlich ein Problem von Access, das andere Datenbanken (z. B. SQL-Srever) nicht haben.

Die Indizes sind in Ordnung, da lässt sich in Access nicht so viel falsch machen. Und meine Abfragen nutzen natürlich die Indizes, dafür habe ich die ja überhaupt erst gesetzt.

Das Ganze startet in Access ja auch wirklich recht schnell, wird mit der Zeit aber immer langssamer. Die einzige Möglichkeit, die ich gefunden habe, das zu beheben, wäre die Bearbeitung zwischenzeitlich zu stoppen, die Datebank zu „komprimieren und reparieren“ und dann die Bearbeitung fortzusetzen. Aber das ist mir dann wirklich zu blöd.

Hier über die Vor-/Nachteile von Datenbanken zu philosofpheren war aber auch nicht mein Ziel. Ich bin nach wie vor offen für konkrete Vorschläge, wie ich das zuerst genannte Problem lösen kann. Letztendlich ist mir völlig egal, ob ich das mit Access umsetze oder nicht, solange es schnell läuft. Und meine bisherige Umsetzung ist das schnellste, was ich finden konnte. Insbesondere muss das Rechenen im Speicher schon deshalb schneller sein, weil das Schreiben/Lesen der Daten in einer DB (=>Aktion auf dem Speichermedium der Datenbank) länger dauert, als im RAM.

Bei 3 GB kann das Datenvolumen noch um das ca. 8 fache steigen, dass das passiert, kann ich ausschließen.

Wie erkenne ich insbesondere im Beispiel 2 möglicht effizient (bezogen auf die Zeit), dass diese 3 Mengen zusammenzufassen sind?

Optimierst du deine Programme/Datenbanken tatsächlich bzgl. des Stromverbrauchs? Mir ist da der Zeitfraktor deutlich wichtiger.

Grüße

powerblue

#10

Woher weißt du das? Hast du das mal gemessen und analysiert?

Klingt für mich nach fehlenden Indizes. Aber ich kenne Access zu wenig, um das mit Sicherheit sagen zu können.

Nicht direkt. Ich optimiere bezüglich CPU-Cycles. Je schneller die CPU wieder frei ist, desto mehr Anfragen bekomme ich pro Zeiteinheit bearbeitet. Optimierung ist immer ein iterativer und kontextabhängiger Prozess, manchmal kann eine Temporäre Tabelle wunder wirken, manchmal ist es zusätzlicher Overhead. Manchmal kann das Drehen von Spalten in der WHERE-Klausel dem Query-Optimizer helfen, machnmal nicht.

Aber letztlich ist es ja gut, wenn du eine Lösung hast.

Du darfst nicht das blanke Datenvolumen deiner 100.000 Datensätze betrachten, sondern den Speicher, den deine Applikation zur Laufzeit im Peak benötigt. Da musst du nur an einer Stelle eine Kopie der Daten machen und schon verdoppelst du deinen Speicherbedarf. Aber auch solche Optimierungen sind ein iterativer, kontextbezogener Prozess. Mehr Performance kriegt man nur selten mit mehr Speicher oder schnellere CPUs, sondern nur durch solides Handwerk.

#11

Hallo,

vielen Dank für deine Hilfe.

Ganz deppert bin ich auch nicht…

Grüße

powerblue

#12

Das habe ich auch nie behauptet. Du bist halt mega unkonkret. Wie oft habe ich mir in meinem Leben schon anhören müssen: „bei mir ist alles Knorke“ und dann sieht man sich die DB-Struktur an und außer dem Primärschlüssel ist kein Index da.

Anhand welcher Aussage von dir sollte ich denn erkennen, dass das bei dir anders ist? Du nennst nichtmal die Programmiersprache. Offensichtlich VBA aber das erhöht nicht unbedingt das Vertrauen in deine Professionalität. Du lieferst keinerlei Beispieldaten, nicht mal ungefähre Beschreibungen. Du sagst nicht, woran du erkennst, dass deine Indizes für deine Joins greifen. Nix.

Aber dann beleidigt sein, weil ich Zweifel anmelde? Lies dir deine Beiträge nochmal mit meiner Brille durch und dann sage mir, was du an meiner Stelle von dir denken würdest.

#14

Hallo,

  • Du kennst dich zweifelsfrei viel besser mit Datenbanken aus als ich. Du hilft mir aber nicht, wenn du mir Infos gibts, nach denen ich nicht gefragt habe und meine eigentliche Frage nicht beantwortest.

  • Ok, ob der Index korrekt in Access erstellt werden oder nicht, kann ich nicht prüfen, da habe ich mich einfach mal auf die Microsoft-Programmierer verlassen. Dass es mehr als nur den Primärschlüssel gibt, ist weiß ich und nutze es auch.

  • In bin der Arbeitsumgebung hier nun mal limitiert. Mir stehen nur Access, Ecxel und VBA zur Verfügung. Das sagt mal gar nichts über meine Professionalität aus. Hatte Informatik aber auch nur als Nebenfach im Studium und arbeite auch nicht als Informatiker, falls du das meinst… Mir wäre ne richtige Programmiersprache und dein echter DB-Server auch lieber, habe ich aber halt hier nicht.

  • Ich habe den echten Ram-Speicherbedarf beobachtet.

  • Es gibt ein paar mehr als 130.00 Datensätze. Für jede Element-Mengen-Beziehung ein Datensatz. Ein Element kann dabei in bis zu 120 Mengen enthalten sein. In den meisten Föllen ist ein Element nur in 2-3 Mengen enthalten.

  • Du sagst selbst, dass du dich nicht so super mit Access auskennst. Ignorierst aber gleichzeitig, dass Access druchaus verschiedene Probleme hat, die echte DB-Server eben nicht haben. Nach meinen Recherchen ist eins dieser Probleme, dass Access langsamer wird, wenn (schnell nacheinander) viele Abfragen durchgefürht werden.

  • Die Aufgabenstellung habe ich im ersten Posting beschrieben. Mir würde jetzt helfen, wenn du mir sagst, wie du das umsetzen würdest (egal welche Programmiersprache, egal welches DB-System). Ausgangdaten sind in einer Tabelle mit zwei Feldern gespeichert. Feld1 Element, Feld2 Menge. Ein Datensatz für jede Element-Menge-Beziehung.

  • Ich gebe bisher so vor:

    1. Ich erstelle mir ein Elemente-Dictioary und speichere dort für jedes Element in welcher Meng es gespeichert ist. Zusätzlich erstelle ich ein Mengen-Dictioary und speichere dort, welche Elemente in der jeweiligen Menge enthalten sind.
    1. Ich wähle initial eine menge als aktuelle Menge
    1. Die Elemente der aktuellen Menge schreibe ich in einen Zwischenspeicher (in dem Zwischenspeicher ist jedes Elemente immer nur ein mal vorhanden; Dictionary). Im Mengen-Dictionary lösche ich diese Menge, Im Elemente-Dictionary lösche ich für jedes Element im Zischenspeicher, dass es in der aktuellen Menge vorhanden ist. Gibt es danach für das geprüfe Element keine Verbindungen zu einer Menge, lösche ich das Elemente aus dem Elemente-Dictionary.
    1. Ich prüfe für die Elemente im Zwischenspeicher, ob sie noch in anderen Mengen enthalten sind
      3a) Das aktuell zu prüfende Element ist noch in anderen Mengen vorhanden. Ich wähle eine dieser Mengen als aktuelle Menge.
      3b) Es gibt kein Element im Zwischenspeicher, das noch in einer anderen Menge vorhanden ist, Die Elemente im Zischenspeicher fasse ich zusammen (schreibe sie in die Zieltabelle in Access, der Zwischenspeicher wird geleert). Als aktuelle Menge wähle ich eine Menge aus dem Mengen-Array, die noch nicht bearbeitet wurde.

  • _4. ich wiederhole die Schritte ab 2. bis das Mengen-Dictionary (und damit gleichzeitig auch das Elemente-Dictionary) leer sind.

  • 5 Im Ergebnis erhalte ich in der Zieltabelle die zusammengefassten Mengen/Elemente.

Grüße

powerblue

#15

Das Problem ist aber vielleicht auch, dass ich dir schon deine Frage beantworte, du das aber nicht erkennen kannst oder willst. Kann sein, oder auch nicht. Aber nochmal: Wenn du ne fertige Lösung hast, dann nimm die und gut. Es sei denn, du willst ohne Ärger noch mal von einer anderen Seite draufschauen, dann können wir das machen. Will hier keinen Streit, sondern nur helfen. In meiner Erfahrung sind Datenbanken für Daten besser geeignet als Schleifen in einer Programmiersprache.

In SQL.

Also so?

+---------+-------+
| Element | Menge |
+---------+-------+
|       1 | A     |
|       1 | B     |
|       2 | B     |
|       2 | D     |
|       3 | C     |
|       4 | A     |
|       5 | C     |
|       6 | D     |
+---------+-------+

Wie lauten die Indizes?

Wie soll denn dein Ergebnis strukturell aussehen? Nimm mal das hier: https://ozh.github.io/ascii-tables/ und füge deinen Wunsch als vorformatierten Text ein.

Also eigentlich willst du eine gesamte Tabelle mit allen Daten, nur dass die Mengen zusammenstehen?

Dann sowas?

SELECT * FROM table ORDER BY Menge, Element;

Mag sein. Aber dafür sehe ich überhaupt keinen Bedarf. Eine Abfrage reicht, soweit ich das gerade erkenne.

#16

Hallo,

schön, dass wir wieder beim eigentlichen Thema sind. Danke für deine Zeit und Hilfe.

Meine Ausgangsdaten sehen so aus:

+---------+-------+
| Element | Menge |
+---------+-------+
| 1       | A     |
| 10      | A     |
| 11      | A     |
| 8       | B     |
| 9       | B     |
| 7       | C     |
| 6       | C     |
| 5       | C     |
| 4       | C     |
| 2       | D     |
| 1       | D     |
| 3       | D     |
| 8       | F     |
| 12      | F     |
| 13      | F     |
| 14      | F     |
| 15      | F     |
| 16      | G     |
| 2       | G     |
+---------+-------+

Ziel wäre:

+---------+-------+-----------------+
| Element | Menge | Zusammenfassung |
+---------+-------+-----------------+
| 1       | A     | I               |
| 10      | A     | I               |
| 11      | A     | I               |
| 8       | B     | II              |
| 9       | B     | II              |
| 7       | C     | IV              |
| 6       | C     | IV              |
| 5       | C     | IV              |
| 4       | C     | IV              |
| 2       | D     | I               |
| 1       | D     | I               |
| 3       | D     | I               |
| 8       | F     | II              |
| 12      | F     | II              |
| 13      | F     | II              |
| 14      | F     | II              |
| 15      | F     | II              |
| 16      | G     | I               |
| 2       | G     | I               |
+---------+-------+-----------------+

Mir geht es um die Spalte Zusammenfassung. Dort kann ich sehen, weche Elemente über die verschiedenen Mengen miteinander Verbunden sind.

Das Ergebnis kann von mir aus auch so aussehen:

+---------+-----------------+
| Element | Zusammenfassung |
+---------+-----------------+
| 1       | I               |
| 10      | I               |
| 11      | I               |
| 8       | II              |
| 9       | II              |
| 7       | IV              |
| 6       | IV              |
| 5       | IV              |
| 4       | IV              |
| 2       | I               |
| 3       | I               |
| 12      | II              |
| 13      | II              |
| 14      | II              |
| 15      | II              |
| 16      | I               |
+---------+-----------------+

Mir ist schleierhaft, wie man das mit einem einzigen SQL-Statement bewerkstelligen soll. Wenn du das hinbekommst, gebe ich einen aus.

In meiner ursprünglichen Version gab es in der Quell-Tabelle jeweils einen Index (Dublikate möglich) auf der Spalte Element und Menge und einen Index (ohne Duplikate) auf den beiden Spalten Element und Menge zusammen.

Auch in der ursprünglichen Version habe ich mit einem Zwischenspeicher (als Tabelle) gearbeitet. Dort habe ich sowohl ohne Indexierung als auch mit (anlaog Quell-Tabelle) Indexierung gearbeitet. Das machte bzgl. Geschwindigkeit keinen wesentlichen Unterschied. Die Zieltabelle hat keine Indizes.

Grüße

powerblue

#17

Mir ist noch nicht ganz klar, nach welchen Regeln du diese Zusammenfassung erzeugst.

In deinen Daten ist

  • 1 in A und D
  • 2 in D und G

Und weil 2 und 1 sich eine Menge teilen, ist auch A und G dann zusammengehörig?

Schick mal deinen VBA-Algorithmus.

Jetzt wo ich Details kenne, glaube ich auch nicht mehr an die 1-Statement-Lösung. Aber mit wenigen Anfragen kommen wir bestimmt aus.

Der Unique-Index würde reichen. Lösch den anderen, das spart Speicher und bläst die Datenbank nicht so auf.

Du meinst eine temporäre Tabelle?

Dann haben deine Indizes nicht auf deine Anfragen gepasst.

#18

Guten Morgen,

du bist ja früh am Start hier…

Sorry, den VBA-Code kann ich nicht schicken. Aber du hast das Problem erfasst. Ich habe einen Haufen Mengen, die (teileweise) über ihre Elemente verbunden sind. Alle Mengen mit Schnittmengen <> leere Menge möchte ich zusammenfassen, sodass ich im Ergebnis nur noch disjunkte Mengen erhalte.

Mir ist noch nicht ganz klar, nach welchen Regeln du diese Zusammenfassung erzeugst.
In deinen Daten ist

1 in A und D2 in D und G

Und weil 2 und 1 sich eine Menge teilen, ist auch A und G dann zusammengehörig?

Ja, genau das ist es. Und genau diese Konstellationen machen die Probleme. Es kann noch eine 4, 5, 6… Menge geben, die über ein Element mit z. B. G oder A verbunden ist, und dann auch noch dazu gehört. Genau das ist mein Problem. Vor allem, weil ich einen Algo benötige, der nicht auf einer statischen Datengrundlage arbeitet, sondern auch mit einem anderen Datenset klar kommt, bei dem die Mengen und deren Verbindungen anders sind.

Bisher ist mir dazu nichts anderes eingefallen als wie oben beschrieben (mal unabhängig davon, ob ich das mit dictionarys oder Tabellen mache) vorzugehen.

Mein Zwichenspeicher hatte ich in Access wie jede andere Tabelle angelegt. Ich hatte auch mal eine Prgrammversion getestet, bei der ich nur den Zwischenspeicher als Dictionary angelegt hatte, auch das hat nicht wirklich was gebracht. Bei Ausführung der vielen Abfragen auf meine Quell-Tabelle ist Access immer langsamer geworden - fast bis zum Stillstand.

Den Tipp, dass der Unique-Index reicht, werde ich mir aber schon mal merken.

Grüße

powerblue

#19

Ist echt eine interessante Knobelarbeit. Lass mich mal ein bisschen darüber nachdenken.