Dublettenabgleich

[brasil66]

Hallo!

Ich habe einen großen Dublettenabgleich vor mir, der bewältigt werden muss. Es verhält sich folgendermaßen:
Es gibt zwei große Dateien, reine Textdateien in deren Zeilen jeweils nur eine Nummer steht.

Bsp.
Datei1:
123235346346
234346346456345234
23453462341253
3534634123
34534645523686345
3464745
usw.

Datei2:
34645746545
3643453
464564674
346456
usw.

Jede einzelene Nummer in einer Zeile stellt einen Datensatz dar und die Reihenfolge der Nummern unterliegt keiner Ordnung.
Jetzt soll verglich werden ob jede Nummer aus Datei1 in Datei2 überhaupt vorhanden ist, und wenn ja, dann soll diese Nummer in eine dritte Datei geschrieben werden, d.h. Datei2 nach erster Nummer aus Datei1 komplett durchforsten, dann nach zweiter Nummer usw.

Ich weiß, das dies wahrscheinlich recht einfach und unkompliziert mit zwei Schleifen zu bewältigen ist, hat jemand dafür einen passenden Tipp zum Anfang parat? Ich tue mich mit den Vergleichen ein wenig schwer ...

Danke schonmal im voraus & Gruß aus Braunschweig

[jens]

Wie groß sind die Daten? Wenn sie nicht all zu groß sind, kannst du einfach alle Nummern einer Datei in eine Liste packen. Dann die andere Datei Zeile für Zeile druchgehen. Wenn eine Nummer auch in der Liste vorkommt, wird sie in die dritte Datei gespeichert...

Wenn die Liste allerdings sehr groß ist und nicht mehr wirklich in deinem Haupspeicher passen, dann hast du ein Problem

[mawe]

Hi!

Wie schon jens gesagt hat, kommts auf die Grösse an
Bei "zumutbarer" Dateilänge kann man mit sets arbeiten:

Code: Alles auswählen

f1 = file("d1.txt","r")
f2 = file("d2.txt","r")
f3 = file("out.txt","w")
lst1 = set(f1.readlines())
lst2 = set(f2.readlines())
for i in (lst1 & lst2):
    f3.write(i)

Gruß, mawe

[brasil66]

Der Hauptspeicher an dem Rechner ist 1GB und die Dateien sind mit ca. 100.000 Zeilen als reine .txt-Dateien klein genug, sollte also nicht das Problem sein ...... und wenn´s dann doch nicht passen sollte, könnte ich temporär auch noch aufrüsten, gemäß dem alten Trucker-Spruch: Hubraum statt Leistung

[jens]

Eine andere Lösung, wenn RAM knapp wird, wäre eine Blockweise abarbeitung... Also man liest einen Zahlen-Block aus Datei A ein und nudelt dann zeile für zeile Datei B durch und schreibt die gleichen Nummern in Datei C rein.
Danach den nächsten Block aus Datei A lesen und wieder Datei B durchnudeln...

Das ganze würde natürlich länger dauern, aber es ist Speicherschonender...

Aus wenn es das Problem nicht gibt, hat jemand ein besseres Prinzip dafür?

[mawe]

Naja, Datei B auch blockweise einlesen. Also

Code: Alles auswählen

100: Block von A einlesen
   200: Block von B einlesen
   ABlock und BBlock vergleichen
   goto 200
goto 100

goto ist schon cool

[XT@ngel]

Naja, Datei B auch blockweise

Hi, vielleicht hab ich jetzt einen Denkfehler, aber beide Files blockweise einlesen funktioniert doch nicht oder?


MfG
Andreas

[jens]

Warum sollte es nicht gehen???
Wäre halt nur eine Sache, wenn man wirklich große Dateien bearbeiten müßte, die halt nicht mehr in's RAM passen... Wobei ja das Betriebssystem auch toll swappen kann

[XT@ngel]

die Reihenfolge der Nummern unterliegt keiner Ordnung.

Beispiel:
File 1:

Code: Alles auswählen

100
200
300
400
500
600

File 2:

Code: Alles auswählen

600
500
400
300
200
100

Wenn man jetzt von file1 und 2 jeweils die ersten 3 Zahlen im Speicher hat, ist doch der Vergleich gar nicht möglich?

Code: Alles auswählen

600  100
500  200
400  300

?

[mawe]

Hi!

Ist meiner Meinung nach ein Denkfehler. Ich weiss, ich hätts nicht mit goto zeigen sollen Prinzipiell sinds ja 2 Schleifen.
Ich lese einen Block von A ein, und vergleiche den mit jedem Block aus B. Dann lese ich den nächsten Block von A ein, und vergleiche ihn mit jedem Block aus B ...
Es wird also alles mit allem verglichen.
Also:

Code: Alles auswählen

100, 200, 300 <-> 600, 500, 400
100, 200, 300 <-> 300, 200, 100
# erster Block von A mit jedem Block von B verglichen
400, 500, 600 <-> 600, 500, 400
400, 500, 600 <-> 300, 300, 100
# zweiter Block von A mit jedem Block von B verglichen

Gruß, mawe

[jens]

Genau so hatte ich mir das auch gedacht... Ist zwar ineffektiv, aber was anders machen, wenn es 50GB zu vergleichen gibt

[BlackJack]

Genau so hatte ich mir das auch gedacht... Ist zwar ineffektiv, aber was anders machen, wenn es 50GB zu vergleichen gibt

Da gibt's aus dem Datenbankbereich Algorithmen, zum Beispiel einen Hash-Join bei dem mit Hilfe einer Partitionierungsfunktion die Eingabe so aufbereitet wird, das eine Hashtabelle entsteht, die noch in den Hauptspeicher passt.

Das blockweise einlesen von B ist eine nette Idee wenn man in C programmiert, in Python wird das zeilenweise iterieren über ein Dateiobjekt intern mit einem Puffer gemacht. Das sollte eigentlich genügen.