Strategie-Frage zum Umgang mit großen Datenmengen

[mzurhorst]

Hallo zusammen, und frohes neues Jahr.

Ich habe mal eine Frage zum Umgang mit großen Datenmengen.
Nun ist groß ja relativ. Ich spreche über zwei Stapel aus ASCII-Dateien, welche in Summe jeweils ca. 75-80 Millionen Zeilen haben. Diese beiden Stapel möchte ich vergleichen.
Ich bin hier unentschlossen, ob ich das ganze unbedingt mit einer Datenbank machen müsste, oder ob das evtl. auch im RAM laufen könnte. Benötigt wird der Vergleich nur 1x für eine Auswertung.


Inhalt der Dateien aus Haufen 1:

• Kosolenausgabe von du auf einem Enterprise Storage
• Die Zeilen beinhalten Dateigröße in kB und die Pfadangabe zur Datei.
• Der Dateiname ist einzigartig über einen unique alphanumerischen String. (z.B. something_a1b2c3d4e5f6g7.pdf)
• Für mich interessant ist hier nur die Dateigröße (Integer) und dieser alphanum. String (blau markiert).
• Für Haufen 1 hatte ich bereits im letzten Sommer einen Python Parser geschrieben, der mir diese Sachen in eine MariaDB importiert. Dieser läuft ~3-4 Stunden und befüllt eine Tabelle der Datenbank.

Inhalt der Dateien von Haufen 2:

• Das ist ein Report aus einer Enterprise PLM Applikation. (Teamcenter).
• Die Zeilen beinhalten drei relevante Informationen:
• ------> interner Datenbank Identifier
• ------> externer Identifier (das ist der alphanum. String von oben!)
• ------> Information ob diese Datei noch referenziert wird aus der Datenbank oder nicht.
• Haufen 2 habe ich noch nicht komplett, sondern nur ca. 200k Zeilen Sample.

Warum das Ganze?
Ich möchte nun im Grunde die Haufen übereinander legen und wissen, wie viel Speicherplatz auf dem Storage alloziert wird durch Dateien, welche nicht mehr in der Datenbank referenziert sind.

Ich überlege nun ob hier an dieser Stelle MySQL überhaupt nötig und effizient ist und wie ich am besten vorgehe.
Mit Python würde ich nun Haufen 1 importieren in Datenbank-Tabelle 1, und dann den Parser nochmal modifizieren für Haufen 2. Diesen Haufen dann in eine zweite Tabelle rein, und dann mittels Join die Treffer suchen.
Wie kann ich bei so etwas vorhersagen, wie effizient das läuft?


Und wäre es z.B. auch vorstellbar, dass ich dies mit Lazarus / FPC mache und statt einer Datenbank diese ganzen 75 Millionen Records direkt im Arbeitsspeicher vorhalte?
In dem Fall würde ich Haufen 1 Zeile für Zeile in ein Objekt rein laden (UID, Größe), und beim Import von Haufen 2 würde ich immer nach dem passenden Objekt im RAM suchen und ein Bool Flag setzen für referenziert/nicht referenziert).
Am Ende wäre das Aufsummieren aller nicht referenzierten Objekte dann sehr einfach.

Was meint ihr dazu? - Wie geht man am geschicktesten an so eine Aufgabe ran?


Danke und viele Grüße,
Marcus

[Socke]

Wie kann ich bei so etwas vorhersagen, wie effizient das läuft?

Die Datenbank und die Clientprogramme müssen korrekt eingestellt bzw. programmiert sein. D.h. auf der Datenbank hilft ein entsprechend großer Data-Cache, sodass alle Daten und Indizes in den Arbeitsspeicher passen. Die Clientprogramme sollten gerade beim Laden eine passende Transaktionskontrolle haben. Da du nur eine einmalige Abfrage durchführtst, könnten auch MEMORY-Tabellen sinnvoll sein.
Mit passenden Indizes wird die Datenbankversion nur marginal langsamer sein, als eine optimale Eigenimplementierung.

Die direkte Verarbeitung in einem (Pascal-)Programm halte ich hingegen eher für eine Spielerei. Damit wirst du auch dein Ziel erreichen, das Suche und Summieren deiner Daten musst du aber selbst implementieren. Der Programmieraufwand ist m.E. ein Vielfaches höher als bei einer SQL-Datenbank. Immerhin stehen die passende Datenstrukturen (z.B Hash-Maps oder AVL-Bäume) sind stehen in Free Pascal bereits zur Verfügung.

[braunbär]

Ich bin nicht sicher, ob ich die Aufgabenstellung richtig verstanden habe, aber ich habe das Gefühl, dass da eine SQL Datenbank ein kompletter Overkill ist.

Vorgangsweise:
Erst einmal Haufen2 lesen - wenn ich dich richtig verstanden habe interessieren dich nur die Dateinamen, die nicht referenziert werden. Die legst du in eine sortierte Stringlist, die anderen ignorierst du.
Dann Haufen1 durchgehen, und für alle Dateien, die du in der Stringlist findest (das sind die nicht mehr referenzierten Dateien), die Größe aufaddieren.
Haufen1 brauchst du dafür gar nicht speichern, und von Haufen 2 nur die nicht referenzierten Dateien.

Wenn du zum Parsen der Zeilen die Regex Unit verwendest, dann hat das ganze Delphi Programm wahrscheinlich auf einer Bildschirmseite Platz. Mit Autohotkey wäre es noch viel einfacher, aber wenn du AHK nicht kennst, hilft dir das natürlich nicht weiter.


Oder hab ich irgend etwas von der Aufgabenstellung falsch verstanden?

[Warf]

Du kannst es so machen wie braunbär geschrieben hat, das laden der daten aus haufen 2 der länge M ist in O(M*log(M)) (für jedes element musst du via binärsuche die korrekte position ermitteln) und das suchen der Elemente aus haufen 1 mit Länge N brauchst du O(N*log(M)) (also für jedes der N elemente in Haufen 2 musst du binärsuche auf den M elementen von Haufen 1 machen). Die gesamt laufzeit ist damit in O(M*Log(M) + N*Log(M)) = O((M + N)*Log(M))

Noch ein alternativvorschlag von mir, du lädst beide haufen in den Speicher, das hat ein laufzeitverhalten von O(M*log(M) + N*log(N)) und dann machst du das folgende:

Code: Alles auswählen

var i1, i2: Integer;
i2 := 0;
for i1 := 0 to haufen1.length -1 do
  if haufen1[i1] = haufen2[i2] then
  begin
    // Kollision gefunden, was auch immer du mit den daten machen willst, machs hier
    Inc(i2);
  end;

Somit ist die Suche in O(N), und die gesammtlaufzeit damit in O(N*log(N) + M*log(M) + N) = O(N*(log(N) + 1) + M*log(M)). Wenn N deutlich größer M, lohnt sich die variante von braunbär mehr, wenn sie beide ungefähr gleich groß sind, macht das asymptotisch nicht viel aus:

Code: Alles auswählen

O(N*(log(N) + 1) + M*log(M)) ~ O(N*(log(N) + 1) + N*log(N)) ~* O(N*log(N) + N*log(N)) = (2*N*log(N)) ~ O((N+M)* Log(M))

(~ ist die annahme das N ungefähr M ist und ~* ist die annahme das N sehr groß ist und damit log(N) ungefähr log(N)+1)

Aber ich kann mir vorstellen das wenn du beide in den speicher lädst, und dann über beide iterierst, du eventuell vom intelligenten caching auf modernen CPU's profitieren kannst. Kann aber natürlich auch nicht der fall sein. Kannst ja beides mal ausprobieren und timen

Eine alternative wäre die version von braunbär mit einer Hashmap, da ist der Average case für einfügen und auslesen in O(1), also ist die gesammtkomplexität in O(N+M), und damit deutlich besser. Aber eine Hashmap hat einen hohen konstanten overhead (hash funktion berechnen) und muss um dynamisch wachsen zu können häufiger mal gerehashed werden, was in O(N) abläuft. Die damit resultierende laufzeit wär also in O(N*M), und damit schlechter als der sortierte ansatz. Aber, was man nicht vergessen darf, bei den einfüge operationen auf einer sortierten liste, muss im average case auch 1/2*N objekte verschoben werden, womit wir asymptotisch auch nicht besser sind. Außerdem, da weiß ich nicht ob vorhandene Hashmap implementationen das erlauben, wenn man eine gute hash funktion hat, und die anzahl der zeilen im vorhinein weiß, kann man das rehashen vermeiden indem man die bucket size und anzahl vorher approximiert (Das ist aber nur ne vermutung von mir, kenn mich in dem bereich nicht so sehr gut aus)
Hash maps haben einen recht hohen konstanten zeitaufwand, und die verschiebe aktion in sortierten listen (die 1/2*N braucht) kann sehr gut gecached werden (effektiv ist das ja nur pointer auf einem array zu verschieben), was bei einer hashmap nicht unbedingt der fall sein kann und ansonsten kann man auch einen balancierten Baum nehmen (AVL, RB oder B-Baum), wobei das cache verhalten einer array liste wie der StringList verloren geht, dafür die verschiebung wegfällt. Es kann also sehr gut sein das die sortierte Liste tatsächlich schneller ist, obwohl theoretisch die Hashmap besser sein sollte.

Ich kenn mich mit diversen SQL implementierungen nicht gut aus, ich denke aber SQL arbeitet mit Hashmaps oder Sortierten listen (bzw. AVL oder RB oder B bäumen), ist damit effektiv auch nix anderes als der vorschlag von braunbär oder der von mir. Asymptotisch wird das also nicht besser sein. Ist aber natürlich um einiges weniger aufwand. Wenn ein sortierter balancierter Baum benutzt wird (wovon ich mal ausgehe) ist das was die SQL datenbank im hintergrund macht also effektiv das was in meinem vorschlag gemacht wird. Was natürlich gemacht werden muss ist das beide datensätze geladen werden müssen vor den Operationen. d.h. wenn N viel größer als M ist, ist das auf jeden fall ineffizienter als der vorschlag von braunbär (ob mit String Liste oder mit Hashmap egal)

[martin_frb]

Einen Hash nutzen ist der erste Gedanke....

Alternativ:
Beide listen sortieren. Danach muss man beide listen nur einmal durchgehen.

1 Element in Liste 1 nehmen.
In Liste 2 suchen solange E1 < L2
Gefunden?
Danach 2 Element aus Liste 1 nehmen.
Die suche kann in Liste 2 an der Stelle fortgesetzt werden, an der E1 gefunden wurde (oder E1 > L2 war). E2 kann ja nicht vor E1 in L2 sein. (Da beide listen sortiert.

Wenn nicht alles in den Speiche passt, kann man die Sortierten listen auf Disk speichern, und in kleinen Stücken laden.

------------
Wenn alles ins Memory passt (ohne swapfile), ist der Hash schneller

[braunbär]

Nachdem er geschrieben hat, dass er das Programm nur einmal (oder zumindest sehr selten) brauchen wird, würde ich meinen, dass der Arbeitsaufwand insgesamt schon auch minimiert werden sollte, natürlich unter der Voraussetzung, dass das Zeitverhalten erträgilch bleibt. Ich denke, das der Overhead einer Datenbank für eine einmalige Verwendung der Daten gar nicht so gering ist - Die Daten müssen ja erst in die Datenbank gefüttert werden, das ist wohl nicht weniger Programieraufwand als das Lesen und Parsen der Dateien in einem Pascal Programm, und für die Verarbeitung müssen die Daten dann erst wieder aus der Datenbank gelesen werden.

Ein hash Tabelle wäre natürlich schneller als eine Stringlist. Ich habe vor Jahren in Delphi für ein paar Aufgaben mit hash Tabellen gearbeitet, das war die Programmierung doch etwas aufwändig, deshalb habe ich eine Stringlist vorgeschlagen. Aber mittlerweile gibt es ja, glaube ich, die entsprechenden Klassen in Lazarus/Free Pascal fix und fertig. Bei derartigen Aufgabenstellungen sollte man nicht unterschätzen, wieviel Aufwand es braucht, ein Programm zu testen, deshalb würde ich eher einem möglichst einfachen Agorithmus den Vorzug geben. Wenn der Computer dann einmal die ganze Nacht beschäftigt ist, sollte das ja auch egal sein, oder?

[mschnell]

Ich bin hier unentschlossen, ob ich das ganze unbedingt mit einer Datenbank machen müsste, oder ob das evtl. auch im RAM laufen könnte.

Das ist kein Widerspruch. Ach eine Datenbank kann im RAM gespeichert sein. z.B. SQLite hat eine Option dafür.

Python Listen scheinen auch gut geeignet zu sein. Die hashen automatisch. Aber eben nicht Lazarus .

-Michael