2 Textdateien vergleichen

[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.

[Michael II]

Zitat von TigerLilly:

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 von 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!

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!