2 Textdateien vergleichen

[einbeliebigername]

Hallo,

Zitat von KodeZwerg:

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 von KodeZwerg:

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 von KodeZwerg:

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 von KodeZwerg:

so etwas hier wollte ich verhindern...

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

Zitat von KodeZwerg:

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 von TigerLilly:

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 von TigerLilly:

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.