AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

2 Textdateien vergleichen

Ein Thema von TigerLilly · begonnen am 23. Sep 2020 · letzter Beitrag vom 27. Sep 2020
Antwort Antwort
Seite 4 von 5   « Erste     234 5   
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
1.172 Beiträge
 
Delphi 11 Alexandria
 
#31

AW: 2 Textdateien vergleichen

  Alt 24. Sep 2020, 16:54
Vergleich ist via File/Stream und CompareMem, Blockgröße 4096.
  Mit Zitat antworten Zitat
Michael II

Registriert seit: 1. Dez 2012
Ort: CH BE Eriswil
703 Beiträge
 
Delphi 11 Alexandria
 
#32

AW: 2 Textdateien vergleichen

  Alt 24. Sep 2020, 16:54
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...
Michael Gasser

Geändert von Michael II (24. Sep 2020 um 17:04 Uhr)
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
1.172 Beiträge
 
Delphi 11 Alexandria
 
#33

AW: 2 Textdateien vergleichen

  Alt 24. Sep 2020, 17:02
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.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
43.017 Beiträge
 
Delphi 12 Athens
 
#34

AW: 2 Textdateien vergleichen

  Alt 24. Sep 2020, 17:06
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).
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list : BugReports/FeatureRequests

Geändert von himitsu (24. Sep 2020 um 17:29 Uhr)
  Mit Zitat antworten Zitat
Michael II

Registriert seit: 1. Dez 2012
Ort: CH BE Eriswil
703 Beiträge
 
Delphi 11 Alexandria
 
#35

AW: 2 Textdateien vergleichen

  Alt 24. Sep 2020, 17:16
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... .
Michael Gasser
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
10.934 Beiträge
 
Delphi 12 Athens
 
#36

AW: 2 Textdateien vergleichen

  Alt 24. Sep 2020, 17:23
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!
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming

Geändert von Uwe Raabe (24. Sep 2020 um 17:25 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von KodeZwerg
KodeZwerg

Registriert seit: 1. Feb 2018
3.685 Beiträge
 
Delphi 11 Alexandria
 
#37

AW: 2 Textdateien vergleichen

  Alt 25. Sep 2020, 10:58
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!
Gruß vom KodeZwerg
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
1.172 Beiträge
 
Delphi 11 Alexandria
 
#38

AW: 2 Textdateien vergleichen

  Alt 25. Sep 2020, 11:19
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.
  Mit Zitat antworten Zitat
Benutzerbild von KodeZwerg
KodeZwerg

Registriert seit: 1. Feb 2018
3.685 Beiträge
 
Delphi 11 Alexandria
 
#39

AW: 2 Textdateien vergleichen

  Alt 25. Sep 2020, 11:22
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.
Gruß vom KodeZwerg
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
10.934 Beiträge
 
Delphi 12 Athens
 
#40

AW: 2 Textdateien vergleichen

  Alt 25. Sep 2020, 11:49
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.
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 10:14 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz