Ich muss ein Programm schreiben, das 10'000'000 + Entitäten miteinander vergleicht. Die Entitäten sind im Wesentlichen flache Zeilen in einer Datenbank / CSV-Datei.
Der Vergleichsalgorithmus muss sehr flexibel sein. Er basiert auf einer Regelengine, bei der der Endbenutzer Regeln eingibt und jede Entität mit jeder anderen Entität verglichen wird.
Ich denke darüber nach, wie ich diese Aufgabe in kleinere Arbeitslasten aufteilen könnte, aber ich habe noch nichts gefunden. Da die Regeln vom Endbenutzer eingegeben werden, scheint das Vorsortieren des DataSets unmöglich.
Ich versuche jetzt, das gesamte DataSet in den Speicher zu packen und jedes Element zu verarbeiten. Aber das ist nicht sehr effizient und benötigt ca. 20 GB Speicher (komprimiert).
Haben Sie eine Idee, wie ich die Arbeitsbelastung aufteilen oder reduzieren könnte?
Danke
Wenn sich Ihre Regeln auf der höchsten Abstraktionsebene befinden (z. B. eine unbekannte Vergleichsfunktion), können Sie Ihr Ziel nicht erreichen. 10 ^ 14 Vergleichsoperationen werden für Ewigkeiten laufen.
Wenn die Regeln nicht völlig allgemein sind, sehe ich 3 Lösungen, um verschiedene Fälle zu optimieren:
Wenn der Vergleich transitiv ist und Sie Hash berechnen können (jemand hat das bereits empfohlen), tun Sie es. Hashes kann auch kompliziert sein, nicht nur Ihre Regeln =). Finden Sie gute Hash-Funktion und es kann in vielen Fällen helfen.
Wenn Entitäten sortierbar sind , sortieren Sie sie. Zu diesem Zweck würde ich empfehlen, nicht direkt zu sortieren, sondern ein Array von Indizes (oder IDs) von Elementen zu erstellen. Wenn Ihr Vergleich in SQL umgewandelt werden kann (wie ich weiß, dass Ihre Daten in der Datenbank sind), können Sie dies auf der DBMS-Seite effizienter durchführen und die sortierten Indizes lesen (zum Beispiel 3,1,2, was den Artikel mit ID = 3 bedeutet ist die niedrigste, mit ID = 1 ist in der Mitte und mit ID = 2 ist die größte). Dann müssen Sie nur benachbarte Elemente vergleichen.
Wenn es sich lohnt , würde ich versuchen, eine heuristische Sortierung oder Hashing zu verwenden. Ich meine, ich würde einen Hash erstellen, der nicht unbedingt identische Elemente identifi- ziert, aber Ihren Datensatz in Gruppen aufteilen kann, zwischen denen es definitiv kein einziges Paar gleicher Elemente gibt. Dann sind alle gleichen Paare in den inneren Gruppen und Sie können Gruppen einzeln nacheinander lesen und manuelle komplexe Funktionsberechnung in der Gruppe von nicht 10 000 000, aber zum Beispiel 100 Elementen vornehmen. Der andere Teilansatz ist eine heuristische Sortierung mit demselben Zweck, um zu gewährleisten, dass gleiche Elemente nicht an den verschiedenen Enden eines Datensatzes liegen. Danach können Sie Elemente nacheinander lesen und mit 1000 vorherigen Elementen vergleichen (zum Beispiel gelesen und im Speicher gehalten). Ich würde zum Beispiel 1100 Elemente im Gedächtnis behalten und die ältesten 100 jedes Mal, wenn neue 100 kommen. Dies würde Ihre DB-Lesevorgänge optimieren. Die andere Implementierung davon ist möglicherweise auch möglich, falls Ihre Regeln Regeln wie (Attribut1 = Wert1) UND (...) oder Regel wie (Attribut1 & lt; Wert2) UND (...) oder irgendeine andere einfache Regel enthalten. Dann können Sie die Clusterisierung zuerst anhand dieser Kriterien vornehmen und dann Elemente in erstellten Clustern vergleichen.
Was ist übrigens, wenn Ihre Regel alle 10 000 000 Elemente als gleich betrachtet? Möchten Sie 10 ^ 14 Ergebnispaare erhalten? Dieser Fall beweist, dass Sie diese Aufgabe im Allgemeinen nicht lösen können. Versuchen Sie, einige Einschränkungen und Annahmen zu treffen.
Ich würde versuchen, über die Regelhierarchie nachzudenken. Sagen wir zum Beispiel, dass Regel A "Farbe" und Regel B "Form" ist.
Wenn Sie Objekte zuerst nach Farbe aufteilen, Dann brauchen Sie den roten Kreis nicht mit dem blauen Dreieck zu vergleichen.
Dies reduziert die Anzahl der benötigten Vergleiche.
Ich würde aus jeder Entität einen Hashcode erstellen. Sie müssen wahrscheinlich die ID von der Hash-Generierung ausschließen und dann auf Gleichheit testen. Wenn Sie die Hashs haben, können Sie alle Hashcodes alphabetisch bestellen. Wenn alle Entitäten in Ordnung sind, ist es ziemlich einfach, nach Doubles zu suchen.
Wenn Sie jede Entität mit allen Entities vergleichen wollen, als effektiv die Daten clustern müssen, gibt es sehr wenig Gründe, völlig unabhängige Dinge zu vergleichen (vergleichen Sie Clothes with Human macht keinen Sinn), ich denke, Ihre Regeln werden es versuchen Cluster die Daten.
Damit Sie die Daten clustern müssen, versuchen Sie einige Cluster-Algorithmen wie K-Means .
Siehe auch Apache Mahout
Suchen Sie nach dem am besten geeigneten Sortieralgorithmus, Art von a, dafür? Ich denke Divide and Concur scheint gut zu sein. Wenn der Algorithmus gut aussieht, können Sie viele andere Möglichkeiten für die Berechnung haben. Besonders parallele Verarbeitung mit MPICH oder etwas kann Ihnen ein endgültiges Ziel geben.
Aber bevor Sie entscheiden, wie Sie vorgehen sollen, müssen Sie überlegen, ob der Algorithmus zuerst passt.