Große Dateien vergleichen

[uname]

Ich bin auf der Suche nach einer Möglichkeit zwei große Dateien effizient zu vergleichen. Die Dateien sind sehr ähnlich und enthalten jeweils nur eine Liste von sortierten MD5-Fingerprints (schon ohne Dateinamen). Insgesamt sind es jeweils etwas mehr als 1 GB an Daten und 40 Millionen Zeilen. Zur Verfügung habe ich einen Rechner mit 1 GB RAM und 2,5 GB Swap (32-Bit-Architektur).

Alle Versuche sind bis jetzt gescheitert. Perl mit Hashes oder auch der Befehl "diff". Entweder war die Laufzeit unannehmbar (selbst nach Stunden kein Ergebnis) oder die Speicherauslastung war zu hoch. Aktuell versuche ich die Kombination aus Perl mit BerkeleyDB. Ich denke aber auch das wird scheitern, da bereits die Erzeugung der BerkeleyDB viel zu lange dauert.

Kennt jemand eine Möglichkeit zwei Dateien mehr oder weniger parallel zu durchlaufen ohne die Daten der einen Datei vorher vollständig in einer Struktur speichern zu müssen? Bin aktuell ein wenig ratlos.

[hikaru]

Teile und Herrsche:
1. Ermittle von beiden Dateien die MD5-Summe.
2. Ist diese unterschiedlich, halbiere die Dateien und wiederhole 1. für jeweils einander entsprechende Teildateien.

[pferdefreund]

Da wird wohl ein eigenes Programm notwedig werden.
Falls es sich um Textdateien handelt, die ja, wie du sagst,
sortiert sind, kann man die sequentiell nebeneinander
herlesen und nicht beide komplett, wie bei PC-Programmen üblich
in den Speicher lutschen - das dürfte bei der Größe nämlich
Swapping ohne Ende geben.
Das ist dann die Programmlogik aus den 70.er Jahren, wie sie
auf Großrechnern ala S/370 verwendet wurde.
Eventuell findet man was bei Google unter
Sequentiell nebeneinander herlesen. Sowas hab ich mal Anfang
der 80er Jahre in PL/1 under DOS/VSE auf ner S/370 gemacht.

[gms]

Die Dateien sind sehr ähnlich und enthalten jeweils nur eine Liste von sortierten MD5-Fingerprints
..
Kennt jemand eine Möglichkeit zwei Dateien mehr oder weniger parallel zu durchlaufen ohne die Daten der einen Datei vorher vollständig in einer Struktur speichern zu müssen?

wie pferdefreund schon angemerkt hat, wenn die Dateien vorsortiert sind, genügt ein einfacher Durchlauf einer Merge-Sortierung:

Code: Alles auswählen

gms@gms2 ~/tmp $ md5sum /usr/bin/[ab]* 2>/dev/null | sort >x1.txt
gms@gms2 ~/tmp $ md5sum /usr/bin/[bc]* 2>/dev/null | sort >x2.txt
gms@gms2 ~/tmp $ cat x.pl
#!perl -w                        
use strict;                      
my ($DATEI1,$DATEI2);            
open($DATEI1,$ARGV[0]) or die "failed top open $ARGV[0]\n";
open($DATEI2,$ARGV[1]) or die "failed top open $ARGV[1]\n";


my ($md51,$file1,$md52,$file2) = ( split(/ /,<$DATEI1>,2),split(/ /,<$DATEI2>,2) );
while ( defined $md51 && defined $md52 ) {                                         
  my $cmp = $md51 cmp $md52;                                                       
  if ( $cmp == 0 ) {                                                               
    print "equal: ",$md51," ",$file1;                                              
    ($md51,$file1,$md52,$file2) = ( split(/ /,<$DATEI1>,2),split(/ /,<$DATEI2>,2) );
  } elsif ( $cmp < 0 ) {                                                            
    print "left : ",$md51," ",$file1;                                               
    ($md51,$file1) = ( split(/ /,<$DATEI1>,2) );                                    
  } else  {                                                                         
    print "right: ",$md52," ",$file2;                                               
    ($md52,$file2) = ( split(/ /,<$DATEI2>,2) );                                    
  }                                                                                 
}
gms@gms2 ~/tmp $perl x.pl x1.txt x2.txt 
right: 00727b87e3321dc449a3da083b7e5c1e  /usr/bin/complete-ant-cmd.pl
equal: 007a6ccb5abe57686fd073c556ffc3ba  /usr/bin/bmtoa              
right: 00ac6d6e7d7470f003ef49ba94fe5f87  /usr/bin/compress-dummy     
right: 01592e9445d5c3bdfc76f01c6630629f  /usr/bin/cupstestdsc        
right: 015fb4d04ae966211044614402b6ae7e  /usr/bin/compile-et.pl      
left : 024065e5277943f572f560a2e160c8cc  /usr/bin/aurecord
...

edit: habe das jetzt nur schnell reingetippt, daher fehlt nach der while Schleife noch die Ausgabe für den letzten Datensatz

Gruß
gms

http://de.wikipedia.org/wiki/Mergesort

[uname]

Danke. Ich habe es im Prinzip genau so übernommen.