Dublettenabgleich

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
brasil66
User
Beiträge: 27
Registriert: Mittwoch 20. Juli 2005, 19:01
Wohnort: Braunschweig

Donnerstag 18. August 2005, 09:46

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
Benutzeravatar
jens
Moderator
Beiträge: 8482
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Donnerstag 18. August 2005, 09:54

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 :)

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Donnerstag 18. August 2005, 10:03

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
User
Beiträge: 27
Registriert: Mittwoch 20. Juli 2005, 19:01
Wohnort: Braunschweig

Donnerstag 18. August 2005, 10:03

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 :lol:
Benutzeravatar
jens
Moderator
Beiträge: 8482
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Donnerstag 18. August 2005, 10:18

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?

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Donnerstag 18. August 2005, 10:29

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 :D
XT@ngel
User
Beiträge: 256
Registriert: Dienstag 6. August 2002, 14:36
Kontaktdaten:

Mittwoch 7. September 2005, 16:02

mawe hat geschrieben:Naja, Datei B auch blockweise
Hi, vielleicht hab ich jetzt einen Denkfehler, aber beide Files blockweise einlesen funktioniert doch nicht oder?


MfG
Andreas
Benutzeravatar
jens
Moderator
Beiträge: 8482
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Mittwoch 7. September 2005, 16:07

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 ;)

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
XT@ngel
User
Beiträge: 256
Registriert: Dienstag 6. August 2002, 14:36
Kontaktdaten:

Mittwoch 7. September 2005, 16:13

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
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Mittwoch 7. September 2005, 16:19

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
Benutzeravatar
jens
Moderator
Beiträge: 8482
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Mittwoch 7. September 2005, 19:32

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

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
BlackJack

Mittwoch 7. September 2005, 21:54

jens hat geschrieben: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.
Antworten