2 Textdateien vergleichen

[TigerLilly]

TFile.Equals(<filename>) gibt es ja leider nicht. Was ist die eleganteste Möglichkeit, zu prüfen, ob zwei Dateien den gleichen Inhalt haben? Gibt es da in der Delphi RTL etwas?

tx

[Der schöne Günther]

Haben beide Dateien die gleiche Größe? Wenn nein, dann ist das Ergebnis schon vorzeitig

Delphi-Quellcode:

false

.

Dann: Beide in einem BufferedFileStream öffnen und Byte für Byte vergleichen - Sobald ungleich dann ist das Ergebnis

Delphi-Quellcode:

false

.

Dann: Ergebnis ist

Delphi-Quellcode:

true

, Dateien sind identisch.

[stahli]

StringList1.Text=StringList2.Text

Hängt natürlich von der Art der Dateien und Anzahl der Prüfungen ab, ob das so taugt...

[lxo]

Hash ermitteln und vergleichen MD5 oder sonstiges evtl. ?
System.Hash

[Der schöne Günther]

Zitat:

Zitat von stahli (Beitrag 1474125)

StringList1.Text=StringList2.Text

Sicher nicht die beste Wahl wenn die Dateien groß oder keine Textdateien sind.

[Dalai]

Zitat:

Zitat von Der schöne Günther (Beitrag 1474124)

Haben beide Dateien die gleiche Größe? Wenn nein, dann ist das Ergebnis schon vorzeitig

Delphi-Quellcode:

false

.

Das kommt darauf an, ob man Zeilenumbrüche mit vergleichen will oder nicht.

Grüße
Dalai

[himitsu]

Delphi-Quellcode:

if TFile.ReadAllText(FileA) = TFile.ReadAllText(FileB) then
  ...

Leider gibt es aus irgendeinem schwachsinnigem Grund in TFile oder sonstwo im Delphi kein GetFileSize, sonst könnte man es Binär auch mit einer einzen Zeile lösen.
Und leider gibt es auch keinen Comparer für TBytes. [add] Mal nachsehn, ob inzwischen, aber ich glaub nicht dran. [/add]

Delphi-Quellcode:

A := TFile.ReadAllBytes(FileA);
B := TFile.ReadAllBytes(FileB);
if (Length(A) = Length(B)) and ((A = nil) or CompareMemory(@A[0], @B[0], Length(A))) then
  ...

[edit] uhhhh, da gab's doch was Neues ... inline :duck:

Delphi-Quellcode:

var A := TFile.ReadAllBytes(FileA); var B := TFile.ReadAllBytes(FileB); if (Length(A) = Length(B)) and CompareMemory(Pointer(A), Pointer(B), Length(A))) then

und mit Speichergau, aber WindowsFileCache hilft etwas

Delphi-Quellcode:

if (Length(TFile.ReadAllBytes(FileA)) = Length(TFile.ReadAllBytes(FileB))) and CompareMemory(Pointer(TFile.ReadAllBytes(FileA)), Pointer(TFile.ReadAllBytes(FileB)), Length(TFile.ReadAllBytes(FileA)))) then

[/edit]

Und natürlich knallt das alles, wenn die Dateien nicht existieren oder nicht lesbar sind,
aber Speicherlecks sind dadurch nicht zu befürchten.

Zitat:

Delphi-Quellcode:

// und vorher noch LoadFromFile
StringList1.Text=StringList2.Text

Bei etwas größeren Dateien natürlich der Speichergau.

Beim Lesen als Stream, durch TEncoding gejagt als String, in String-Array zerlegt (Zeilen), dann über .Text wieder in "einen" String und nun erst verglichen.
Aber zumindestens würden unterschiedliche Zeilenumbrüche (#10, #13 oder #13#10) und BOMs ignoriert, vielleicht noch mit Trim drumrum. :stupid:

[Bernhard Geyer]

Zitat:

Zitat von Der schöne Günther (Beitrag 1474127)

Zitat:

Zitat von stahli (Beitrag 1474125)

StringList1.Text=StringList2.Text

Sicher nicht die beste Wahl wenn die Dateien groß oder keine Textdateien sind.

Soll aber Textdatei sein.
Und wenn man Textdateien vergleichen will, dann sollte die Codierung (UTF8, UTF-16) ja auch egal sein, so das das laden in einen String(List) vermutlich nötig ist.

[TigerLilly]

:- ) Danke für die Tipps!

- Codierung unterschiedlich --> Dateien sind unterschiedlich
- Zeilenumbrüche anders --> Dateien sind unterschiedlich

Also kann man wirkliche Byteweise vergleichen.

CompareMemory ist aber nicht Teil der RTL - sondern?

TBufferedFileStream optimiert bei wiederholtem Lesen, da für den Vergleich nur 1x gelesen werden muss, genügt doch TFileStream?

Da ich nach dem ersten Unterschied schon aufhören kann, ist es doch performanter, wenn ich die Dateien zeichenweise lese + vergleiche + nicht den ganzen Inhalt mit TFile.ReadAllBytes(FileA) einlese und dann erst vergleiche, oder?

[Der schöne Günther]

Zitat:

Zitat von TigerLilly (Beitrag 1474142)

TBufferedFileStream optimiert bei wiederholtem Lesen, da für den Vergleich nur 1x gelesen werden muss, genügt doch TFileStream?

Gemeint ist nicht die Datei mehrmals hintereinander zu lesen.
Wenn du zeichenweise liest, dann ist das doch wiederholtes Lesen.

Wenn du dir hingegen die gesamte Datei in den Speicher ziehst (wie z.B. auch mit TFile.ReadAllBytes(..)) dann macht mit oder ohne Puffer keinen Unterschied.

[KodeZwerg]

Ich schließe mich lxo da voll und ganz an.
Dateigröße prüfen, wenn gleich dann einen Hash/Crc Wert beider Dateien vergleichen.
Dabei ist es völlig egal ob es Text oder Binär Inhalt ist.

Delphi-Quellcode:

uses
  WinApi.Windows, System.Hash;


// um Dateigrößen >4GB zu ermitteln
function GetFileSize(const aFilename: String): Int64;
var
  info: TWin32FileAttributeData;
begin
  Result := -1;
  if NOT GetFileAttributesEx(PWideChar(aFileName), GetFileExInfoStandard, @info) then
    Exit;
  Result := Int64(info.nFileSizeLow) or Int64(info.nFileSizeHigh shl 32);
end;

// von lxo aus Delphi-Praxis
function GetHashMD5(const Datei: String): String;
begin
  Result := THashMD5.GetHashStringFromFile(Datei);
end;

//beispiel, nur hier per editor... ungetestet
function IsEqualFile(const Datei1, Datei2: String): Boolean;
begin
  Result := ( (GetFileSize(Datei1) = GetFileSize(Datei2)) and (GetHashMD5(Datei1) = GetHashMD5(Datei2)) );
end;

//edit
code beispiel angefügt

[Uwe Raabe]

Zitat:

Zitat von TigerLilly (Beitrag 1474142)

CompareMemory ist aber nicht Teil der RTL - sondern?

Stimmt, aber CompareMem in SysUtils ist es.

Zitat:

Zitat von TigerLilly (Beitrag 1474142)

TBufferedFileStream optimiert bei wiederholtem Lesen, da für den Vergleich nur 1x gelesen werden muss, genügt doch TFileStream?

Da ich nach dem ersten Unterschied schon aufhören kann, ist es doch performanter, wenn ich die Dateien zeichenweise lese + vergleiche + nicht den ganzen Inhalt mit TFile.ReadAllBytes(FileA) einlese und dann erst vergleiche, oder?

Das ist so ein bisschen Statistik. Eenn sich die Dateien häufig erst am Ende unterscheiden, ist es meist performanter die Datei komplett oder blockweise einzulesen. Blockweise Einlesen ist in der Regel ein guter Kompromiss.

[freimatz]

Zitat:

Zitat von TigerLilly (Beitrag 1474122)

TFile.Equals(<filename>) gibt es ja leider nicht. Was ist die eleganteste Möglichkeit, zu prüfen, ob zwei Dateien den gleichen Inhalt haben? Gibt es da in der Delphi RTL etwas?

Nein.
Definiere "elegant" :P
Mit unklaren Anforderungen bekommt man meist nicht das was man erwartet. :-)

[lxo]

Zitat:

Zitat von KodeZwerg (Beitrag 1474147)

Delphi-Quellcode:

uses
  WinApi.Windows, IdHashMessageDigest, IdHash;

 //returns MD5 hash for a file, von Zarko Gajic
 function MD5(const fileName : string) : string;
 var
   idmd5 : TIdHashMessageDigest5;
   fs : TFileStream;
   hash : T4x4LongWordRecord;
 begin
   idmd5 := TIdHashMessageDigest5.Create;
   fs := TFileStream.Create(fileName, fmOpenRead OR fmShareDenyWrite) ;
   try
     result := idmd5.AsHex(idmd5.HashValue(fs)) ;
   finally
     fs.Free;
     idmd5.Free;
   end;
 end;

Statt TIdHashMessageDigest5 würde ich dann aber aber System.Hash.THashMD5 nutzen.
Ist angenehmer zu verwenden und gerade kurz getestet auch schneller.

Code:

uses
 System.Hash;

begin
 THashMD5.GetHashStringFromFile( 'C:\Test.txt');
end;

[TigerLilly]

Zitat:

Zitat von lxo (Beitrag 1474151)

Code:

uses
 System.Hash;

begin
 THashMD5.GetHashStringFromFile( 'C:\Test.txt');
end;

Ah! Das ist gut!

Zitat:

Zitat von freimatz (Beitrag 1474150)

Mit unklaren Anforderungen bekommt man meist nicht das was man erwartet. :-)

q.e.d.

[KodeZwerg]

Hab den Schnippsel überarbeitet, Danke @lxo

[lxo]

Kleiner Tipp noch für alle die DevExpress nutzen.
Da gibt es auch die Unit dxHash.pas

Die kriegen das nochmal schneller hin als System.Hash

[freimatz]

Zitat:

Zitat von TigerLilly (Beitrag 1474160)

Zitat:

Zitat von freimatz (Beitrag 1474150)

Mit unklaren Anforderungen bekommt man meist nicht das was man erwartet. :-)

q.e.d.

:-)

Wenn Du mit elegant möglichs kurzen Code meinst, dass ist das mit dem Hash m.E. am Besten.
Wenn es dagegen z.B. um die Laufzeit geht gibt es sicher noch schnellere Methoden, einiges wurde ja hier auch schon andiskutiert.

Zudem: Beyond Compare hat zig. Optionen mit denen man einstellen kann was man mit "gleich" meint ;-)

[einbeliebigername]

Hallo,

Zitat:

Zitat von Der schöne Günther (Beitrag 1474127)

Zitat:

Zitat von stahli (Beitrag 1474125)

StringList1.Text=StringList2.Text

Sicher nicht die beste Wahl wenn die Dateien groß oder keine Textdateien sind.

Sicherlich nicht die beste Lösung des Problems, welche aber unter schon genannten Bedingungen noch akzeptabel ist. Aber auf alle Fälle unendlich mal besser als dieser Blödsinn:

Zitat:

Zitat von lxo (Beitrag 1474126)

Hash ermitteln und vergleichen MD5 oder sonstiges evtl. ?
System.Hash

Und folgender Algorithmus ist fehlerhaft.

Zitat:

Zitat von KodeZwerg (Beitrag 1474147)

Delphi-Quellcode:

uses
  WinApi.Windows, System.Hash;


// um Dateigrößen >4GB zu ermitteln
function GetFileSize(const aFilename: String): Int64;
var
  info: TWin32FileAttributeData;
begin
  Result := -1;
  if NOT GetFileAttributesEx(PWideChar(aFileName), GetFileExInfoStandard, @info) then
    Exit;
  Result := Int64(info.nFileSizeLow) or Int64(info.nFileSizeHigh shl 32);
end;

// von lxo aus Delphi-Praxis
function GetHashMD5(const Datei: String): String;
begin
  Result := THashMD5.GetHashStringFromFile(Datei);
end;

//beispiel, nur hier per editor... ungetestet
function IsEqualFile(const Datei1, Datei2: String): Boolean;
begin
  Result := ( (GetFileSize(Datei1) = GetFileSize(Datei2)) and (GetHashMD5(Datei1) = GetHashMD5(Datei2)) );
end;

Genauer gesagt liefert dieser nur beim Rückgabewert

Delphi-Quellcode:

False

ein korrektes Ergebnis. Der Rückgabewert

Delphi-Quellcode:

True

ist unbrauchbar, denn es fehlt noch der Byteweise Vergleich.

[KodeZwerg]

Zitat:

Zitat von einbeliebigername (Beitrag 1474182)

Und folgender Algorithmus ist fehlerhaft.
...mein schnippsel von oben...
Genauer gesagt liefert dieser nur beim Rückgabewert

Delphi-Quellcode:

False

ein korrektes Ergebnis. Der Rückgabewert

Delphi-Quellcode:

True

ist unbrauchbar, denn es fehlt noch der Byteweise Vergleich.

Ein Hash wird über die Bytes generiert.
Hättest Du die Güte ein Beispiel zu posten damit das was Du sagst nachvollziehbar ist?
Das 2 unterschiedliche Dateien den gleichen MD5 Hash liefern... möglich ja aber eher die Ausnahme als die Regel.

Ich hatte halt Geschwindigkeit im Vordergrund.

so etwas hier wollte ich verhindern...
gefunden auf Stackoverflow, code von David

Delphi-Quellcode:

// Usage example

var lError: Integer;
...
 if FilesAreIdentical(lError, 'file1.ext', 'file2.ext')
    then Memo1.Lines.Append('Files are identical.')
    else case lError of
           0: Memo1.Lines.Append('Files are NOT identical!');
           1: Memo1.Lines.Append('Files opened, stream read exception raised!');
           2: Memo1.Lines.Append('File does not exist!');
           3: Memo1.Lines.Append('File open exception raised!');
         end; // case
...

// StreamAreIdentical

function StreamsAreIdentical(var aError: Integer;
                             const aStream1, aStream2: TStream;
                             const aBlockSize: Integer = 4096): Boolean;

var
  lBuffer1: array of byte;
  lBuffer2: array of byte;
  lBuffer1Readed,
  lBuffer2Readed,
  lBlockSize: integer;

begin
  Result:=False;
  aError:=0;
  try
    if aStream1.Size <> aStream2.Size
       then Exit;

    aStream1.Position:=0;
    aStream2.Position:=0;

    if aBlockSize>0
       then lBlockSize:=aBlockSize
       else lBlockSize:=4096;

    SetLength(lBuffer1, lBlockSize);
    SetLength(lBuffer2, lBlockSize);

    lBuffer1Readed:=1; // just for entering while

    while (lBuffer1Readed > 0) and (aStream1.Position < aStream1.Size) do
    begin
      lBuffer1Readed := aStream1.Read(lBuffer1[0], lBlockSize);
      lBuffer2Readed := aStream2.Read(lBuffer2[0], lBlockSize);

      if (lBuffer1Readed <> lBuffer2Readed) or ((lBuffer1Readed <> lBlockSize) and (aStream1.Position < aStream1.Size))
         then Exit;

      if not CompareMem(@lBuffer1[0], @lBuffer2[0], lBuffer1Readed)
         then Exit;
    end; // while

    Result:=True;
  except
    aError:=1; // stream read exception
  end;
end;


// FilesAreIdentical using function StreamsAreIdentical

function FilesAreIdentical(var aError: Integer;
                           const aFileName1, aFileName2: String;
                           const aBlockSize: Integer = 4096): Boolean;

var lFileStream1,
    lFilestream2: TFileStream;

begin
 Result:=False;
 try
   if not (FileExists(aFileName1) and FileExists(aFileName2))
      then begin
        aError:=2; // file not found
        Exit;
      end;

   lFileStream1:=nil;
   lFileStream2:=nil;
   try
     lFileStream1:=TfileStream.Create(aFileName1, fmOpenRead or fmShareDenyNone);
     lFileStream2:=TFileStream.Create(aFileName2, fmOpenRead or fmShareDenyNone);
     result:=StreamsAreIdentical(aError, lFileStream1, lFileStream2, aBlockSize);
   finally
     if lFileStream2<>nil
        then lFileStream2.Free;

     if lFileStream1<>nil
        then lFileStream1.Free;
   end; // finally
 except
   aError:=3; // file open exception
 end; // except
end;

[Gausi]

Warum bei zwei Dateien überhaupt die Hashwerte bilden, wenn man nur wissen will, ob die beiden Files gleich sind? Den Aufwand, den Hash zu berechnen (gut, der hält sich in aller Regel in Grenzen), kann man sich doch sparen, und einfach den Dateiinhalt vergleichen. Oder sind Dinge wie CompareMem so CPU-lastig? :gruebel:

Mit Hashwerten würde ich nur arbeiten, wenn ich mehr als nur eine Datei habe, und z.B. in einem Dokumenten-Verwaltungssystem checken möchte, ob eine Datei bereits im System vorhanden ist oder nicht (zumindest mit einer i.A. ausreichend hohen Wahrscheinlichkeit).

[freimatz]

Zitat:

Zitat von Gausi (Beitrag 1474187)

Warum bei zwei Dateien überhaupt die Hashwerte bilden, wenn man nur wissen will, ob die beiden Files gleich sind?

Weil es nichts existierendes gibt und ein

Delphi-Quellcode:

THashMD5.GetHashStringFromFile(file1)=THashMD5.GetHashStringFromFile(file2)

schnell hingeschrieben ist, Geschwindigkeit keine Rolle spielt und man noch mehr zu tun hat. ;-)

[Delphi.Narium]

Zwei Hashwerte getrennt von zwei 4 GB großen (oder auch größeren) Dateien zu berechnen, dürfte deutlich einfacher sein, als beide Dateien ins Ram zu laden und sie dann dort zu vergleichen.

Zum Dublettensuchen nehme ich seit Jahr und Tag MD5. Ist sau schnell und treffsicher. Und Du musst nicht beide Dateien gleichzeitig im Speicher halten und Du muss nicht mal was Programmieren, um den Vergleich durchzuführen.

Einfacher, als mit dem Beispiel von KodeZwerg, kriegst Du das nicht hin und alles mit bereits vorhanden Hausmitteln, mit hinlänglich bekannten und verbreiteten Algorithmen.

In meiner Musikdateienverwaltung steht zu jeder Datei auch der entsprechende MD5-Hash. Kommt 'ne neue Datei, wird deren MD5 berechnet und der eindeutige Index haut mir das beim Speichern direkt um die Ohren.

Wie willst Du sowas denn einfacher machen?

So kannst Du sogar zwei Dateien vergleichen, von denen Du bis dahin nichtmal wusstest, dass ein Vergleich zur Dublettenerkennung erforderlich sein könnte.

OK: Der Vorschlag von freimatz ist noch kürzer, den kann man klar verständlich irgendwo im Quelltext in 'nem If then else stehen haben und fertig.

[einbeliebigername]

Hallo,

Zitat:

Zitat von KodeZwerg (Beitrag 1474183)

Ein Hash wird über die Bytes generiert.

Ja, richtig. Genauer gesagt über die gesamten Bytes. Sonst macht das garkeinen Sinn. Aber dazu später mehr.

Zitat:

Zitat von KodeZwerg (Beitrag 1474183)

Hättest Du die Güte ein Beispiel zu posten damit das was Du sagst nachvollziehbar ist?

Nein. Das ist mir zu aufwendig, bzw. der Strom ist mir zu teuer, zwei Dateien zu suchen wo dein Algorithmus falsche Ergebnisse liefert. Mir reicht es das es diese zwei Dateien theoretisch geben kann.

Zitat:

Zitat von KodeZwerg (Beitrag 1474183)

Das 2 unterschiedliche Dateien den gleichen MD5 Hash liefern... möglich ja aber eher die Ausnahme als die Regel.

Es reicht, dass es möglich ist. Denn wir wollen Programme scheiben die 100,0% richtig funktionieren.

Zitat:

Zitat von KodeZwerg (Beitrag 1474183)

so etwas hier wollte ich verhindern...

Beim überfliegen scheint das aber erst mal mit jedem Pärchen 100,0% richtig zu funktionieren.

Zitat:

Zitat von KodeZwerg (Beitrag 1474183)

Ich hatte halt Geschwindigkeit im Vordergrund.

Da verliert deinen Lösung mit Hash aber haushoch. Was ist denn langsam? Über den byteweisen vergleich gähnt die CPU heutzutage nur müde. Es ist doch das lesen der Dateien von der Festplatte, was langsam ist. Selbst bei einer sehr guten SSD hat die CPU neben bei noch genügend Zeit. Und das Problem an deiner Lösung mit Hash ist, neben dem Problem mit der mangelnden Aussagekraft bei gleichen Hashwerten, dass bei beiden Dateien immer der gesamte Inhalt gelesen werden muss, selbst wenn das erste Byte schon unterschiedlich ist. Und selbst wenn die heutigen CPU's die Berechnung eines Hash spielend erledigen, ist der Aufwand für die Hash-Berechnungen deutlich höher als für den byteweisen Vergleich.

Hash’s kann man einsetzten um den kreuzweisen Vergleich vieler Dateien zu optimieren. Dabei muss man dann aber auf die Eigenheiten der Hash-Algorithmen eingehen. Und läuft Gefahr, dass die Optimierung bei manchen Situationen nach hinten los geht.

[Rollo62]

Ich denke eigentlich auch, dass das direkte Vergleichen mit frühem Abbruch am am schnellsten sein wird.
Zumindest wenn es statistisch verteilt ist, und sich die Files nicht nur am Ende unterscheiden.

Es sei denn, der Hash wird für spätere Vergleiche "aufgehoben",
dann könnte der Hash auch Sinn machen.

Ich bin aber gar nicht sicher ob MD5 überhaupt noch zeitgemäß ist,
das kommt doch aus der Hash-Urzeit.
Gibt es da nicht mittlerweile viel effizientere Hashes für große Text- und Binärdateien ?

[freimatz]

Falls das interessiert würde ich bei git nachschauen.

[Rollo62]

Ja, gute Idee.
So einfach ist das bei GIT aber anscheinend auch nicht:
https://www.golem.de/news/hashfunkti...02-139145.html

[TigerLilly]

Hat mich jetzt interessiert.

Bei identen Dateien, egal welche Größe, ist Hash schneller, weil der Vergleich ja bis zum letzten Byte laufen muss.
Wenn es Unterschiede gibt, und auch wenn die erst im letzten Viertel sind, ist der Vergleich schneller, auch hier unabhängig von der Größe.

Die Dateien waren Textdateien, Zeilen zwischne 1000 und 100.000. Wobei die Unterschiede nicht groß sind:

Zeilen: 100000 Änderung bei 0 Dauer 341 296
Zeilen: 100000 Änderung bei 25 Dauer 257 305
Zeilen: 100000 Änderung bei 75 Dauer 302 350

Zeiten sind Millisekunden, Vergleich und dann Hash. Die "Änderung bei" gibt an, in welchem Teil der Datei der erste Unterschied ist, in %.
Um den Einfluß des Windows Cache zu elimieren, erfolgt der Vergleich mehrfach und die Zeit wird gemittelt.

[Gausi]

Zitat:

Zitat von TigerLilly (Beitrag 1474208)

Bei identen Dateien, egal welche Größe, ist Hash schneller, weil der Vergleich ja bis zum letzten Byte laufen muss.

Und beim Hashen muss nicht die gesamte Datei gelesen und verarbeitet werden? Mir leuchtet immer noch nicht ein, wieso hashen schneller sein soll bzw. kann. Wie hast du denn die Textdateien verglichen? Mit StringList1.Text = StingList2.Text, von dem weiter vorne schon geklärt wurde, dass das alles andere als optimal ist? (Egal ob die Ressource "Zeit" oder "Speicher" betrachtet wird).
Der Weg über CompareMem (deutlich mehr "eigener Code", was ja auch ein Maß für Effizienz sein kann) sollte eigentlich deutlich schneller sein als hashen ...

[Rollo62]

Zitat:

Zitat von TigerLilly (Beitrag 1474208)

Bei identen Dateien, egal welche Größe, ist Hash schneller, weil der Vergleich ja bis zum letzten Byte laufen muss.

Wundert mich aber,
Byte-Vergleich ist doch optimal schnell, wohingegen der der Hash jedes Byte Berechnen, verschieben und sonstwie vermuscheln muss.
https://de.wikipedia.org/wiki/Messag...st_Algorithm_5

[TigerLilly]

Vergleich ist via File/Stream und CompareMem, Blockgröße 4096.

[Michael II]

Hashes - zum Beispiel MD5 sind v.a. gut um zu checken, ob zwei Bitfolgen (hier Files) voneinander verschieden sind. Wenn man aber wie hier gefordert sicher auf Gleichheit von zwei Files checken will und allein zum Beispiel MD5 verwendet, dann fliegt einem das sogar bei reinen Textfiles sowas von rasch um die Ohren.

Zwei Beispiele: MD5 Files enthalten irgendwelche Bitfolgen. MD5 bildet jede Bitfolge eindeutig auf einen 128Bit Wert ab. Bei allen Files mit genauer Länge 128Bit = 16 Bytes könnten also all diese Mini-Files effektiv einen voneinander verschiedenen Hash aufweisen. Nehmen wir nur eine einzige weitere Bitfolge zum Beispiel 0 oder 10 oder was auch immer dazu hat man bereits sicher Kollisionen. - Bei einer Bitfolge mit genauer Länge 32 Bytes wird es im Schnitt 2^16-1 weitere Bitfolgen der Länge 32 Bytes geben, welche denselben Hash aufweisen.

Gesuchtes Beispiel? - Das kann doch bei Textfiles nicht passieren...!
MD5 bildet alle Bitfolgen dieser Welt auf jeweils einen 128Bit Wert ab. Das sind 2^128 = 3*10^38 voneinander verschiedene Werte. Wenn wir alle Textfiles mit zum Beispiel genau 39 Ziffern betrachten (und solche Files gibt es in der Praxis in Massen), dann benötigten wir eine Hashfunktion mit 10^39 möglichen Werten um all diese Files voneinander unterscheiden zu können; MD5 liefert aber nur 3*10^38.

Hashes sollten in diesem Thread zwar vom Tisch sein: Dennoch zum Speedvergleich Hash vs. CompareMem. Da muss CompareMem sowas von gewinnen. Die Gründe liegen auf der Hand. Wenn dem in Tests nicht so sein sollte, dann will ich je den Code sehen...

[TigerLilly]

Alles gut. Tatsächliches Vergleichen ist besser, Hashes können Kollisionen haben + damit wären unterschiedliche Dateien als gleich beurteilt. Ich wollte nur mehr wissen, was die Laufzeiten anbelangt.

Eine Alternative zum Hash wäre gewesen, die Buchstaben in jeder Datei zu zählen und diese Summen dann zu vergleichen, aber auch da ist der Vergleich schneller +hat den Vorteil, uU vorzeitig abbrechen zu können.

[himitsu]

CompareMem bricht beim ersten Unterschied ab,
während er Hash immer alles durchgehen muß.

Allerdings wird beim Hash immer nur auf einen Speicherbereich gleichzeitig zugegriffen werden,
während beim Direktvergleich eventuell öfters im Cache die Speicherbereiche umgeschaltet/neugeladen werden müssen.
Dagegen wird bei einem Hash aber auch bissl was "berechnet", was wieder bissl Zeit braucht.



Und ja, auch unterschiedliche Dateien können den selben Hash besitzen.
OK, ein guter Hash-Algorithmuß sollte kleinere Änderuungen gut abfangen, aber dennoch ist es möglich.

Ein MD5 ist 128 Bit (4 Integer bzw. 16 Byte) groß und kann somit 2^128 verschiedne Werte speichern.
also bei 17 Byte Dateigröße gibt es durchschnittlich 256 Datei-Versionen mit dem selben Hash, und je größer um so "schlimmer",
auch wenn es "statistisch" relativ unwahrscheinlich ist, dass im "realen" Umfeld zwei Dateien den gleichen Hash haben werden,
da es immerhin 340.282.366.920.938.463.463.374.607.431.768.211.456 unterschiedliche Hashs gibt und bei den Dateien auch nie "alle" Bit-Versionen existieren, aber unmöglich ist es nicht.



Der Hash ist für einen ersten Schnellen vergleich gut, z.b. um mehrere Dateien in einer Liste abzugleichen, aber will man wirklich auf "Gleichheit" prüfen, dann ist nur der Direktvergleich 100%ig sicher.
Ist der Hash aber schon unterschiedlich, dann kann der Direktvergleich auch nichts Anderes mehr aussagen. (je nach Komplexität der Daten kann man bei schnellem Kleinkram wie CRC32 anfangen, bis hin zu größeren/komplexeren Hashs)


Im Delphi findet man mehrere Hashs, wie z.B. CRC32, MD5, SHA1, SHA2, SHA512 oder BobJenkins und bis runter zu Word / 16 Bit (TIdHash16).

[Michael II]

Zitat:

Zitat von TigerLilly (Beitrag 1474216)

Eine Alternative zum Hash wäre gewesen, die Buchstaben in jeder Datei zu zählen und diese Summen dann zu vergleichen,

Was dann auch wieder eine sehr, sehr einfache Hashfunktion mit noch mehr Kollisionen wäre.... - ich mach jetzt kein Beispiel... ;-).

[Uwe Raabe]

Bei meinen Versuchen braucht THashMD5 ca. 9x soviel Zeit wie ein CompareMem auf 4k Blöcke bei identischen Dateien von ca. 600kB

Vergrößere ich die Blöcke auf 32k, steigt der Faktor auf ca. 30!

[KodeZwerg]

Zitat:

Zitat von Uwe Raabe (Beitrag 1474220)

Bei meinen Versuchen braucht THashMD5 ca. 9x soviel Zeit wie ein CompareMem auf 4k Blöcke bei identischen Dateien von ca. 600kB

Vergrößere ich die Blöcke auf 32k, steigt der Faktor auf ca. 30!

Hallo Uwe!

Wir hatten ja das Thema Benchmark schon einmal, wo ich eher synthetisch vorgegangen war weil mir das hier schwer fällt:
"eine methode so zu gestalten das sie nicht den Cache benutzt"

Von daher meine Frage, könntest Du Deinen Bench-Code bitte posten, daran bin ich sehr interessiert!

[TigerLilly]

Zitat:

Zitat von Michael II (Beitrag 1474218)

Zitat:

Zitat von TigerLilly (Beitrag 1474216)

Eine Alternative zum Hash wäre gewesen, die Buchstaben in jeder Datei zu zählen und diese Summen dann zu vergleichen,

Was dann auch wieder eine sehr, sehr einfache Hashfunktion mit noch mehr Kollisionen wäre.... - ich mach jetzt kein Beispiel... ;-).

Jein. Ja, weil du recht hast, es kann Dateien geben, die sich nur durch Vertauschungen unterscheiden. Nein, weil es in diesem Fall auf Grund der daten nicht sein kann, dass es nur Vertauschungen gibt.

[KodeZwerg]

naja, "abc" ist beim zählen das selbe wie "xyz", also das würde ich generell ausschliessen aber kommt, wie du gerade geschrieben hast, auf die vor-ort situation an.

[Uwe Raabe]

Zitat:

Zitat von KodeZwerg (Beitrag 1474271)

Von daher meine Frage, könntest Du Deinen Bench-Code bitte posten, daran bin ich sehr interessiert!

Klar, kein Problem. Das Caching des Betriebssystems kann ich natürlich so nicht umgehen, aber ich kann adäquate Voraussetzungen für ein qualifiziertes Ergebnis schaffen. Da ich hier auf einer NVMe SSD arbeite, spielt das eh keine große Rolle.

Delphi-Quellcode:

program CompareFileBench;

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.Classes,
  System.Hash,
  System.Diagnostics;

function AreFilesEqual(const FileNameA, FileNameB: string; BlockSize: Integer = 4096): Boolean;
var
  a: TBytes;
  b: TBytes;
  cntA: Integer;
  cntB: Integer;
  readerA: TStream;
  readerB: TStream;
begin
  Result := False;
  readerA := TFileStream.Create(FileNameA, fmOpenRead);
  try
    readerB := TFileStream.Create(FileNameB, fmOpenRead);
    try
      SetLength(a, BlockSize);
      SetLength(b, BlockSize);
      repeat
        cntA := readerA.Read(a, BlockSize);
        cntB := readerB.Read(b, BlockSize);
        if cntA <> cntB then Exit;
        if cntA = 0 then Break;
        if not CompareMem(@a[0], @b[0], cntA) then Exit;
      until cntA < BlockSize;
      Result := True;
    finally
      readerB.Free;
    end;
  finally
    readerA.Free;
  end;
end;

procedure Test;
var
  c1: string;
  c2: string;
  I: Integer;
  sw: TStopwatch;
begin
  c1 := '<some file>';
  c2 := '<some other file with the same content>';

  { Dummy call to fill the cache }
  AreFilesEqual(c1, c2, 16*1024);
  sw := TStopwatch.StartNew;
  for I := 1 to 1000 do
    AreFilesEqual(c1, c2, 16*1024);
  Writeln(sw.ElapsedMilliseconds);

  { Dummy call to fill the cache }
  THashMD5.GetHashBytesFromFile(c1);
  THashMD5.GetHashBytesFromFile(c2);
  sw := TStopwatch.StartNew;
  for I := 1 to 1000 do begin
    THashMD5.GetHashBytesFromFile(c1);
    THashMD5.GetHashBytesFromFile(c2);
  end;
  Writeln(sw.ElapsedMilliseconds);
end;

begin
  try
    Test;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.