Ein Prüfsummenvergleich ist höchstwahrscheinlich langsamer als ein byteweiser Vergleich.
Um eine Prüfsumme zu generieren, müssen Sie jedes Byte der Datei laden und die Verarbeitung durchführen. Sie müssen dies dann für die zweite Datei tun. Die Verarbeitung wird mit ziemlicher Sicherheit langsamer sein als die Vergleichsprüfung.
Eine Prüfsumme kann jedoch schneller und sinnvoller sein, wenn Sie die Prüfsumme des Falls "Test" oder "Basis" vorberechnen können. Wenn Sie über eine vorhandene Datei verfügen und prüfen, ob eine neue Datei mit der vorhandenen identisch ist, bedeutet die Vorberechnung der Prüfsumme für Ihre "vorhandene" Datei, dass Sie das DiskIO nur einmal ausführen müssen neue Datei. Dies wäre wahrscheinlich schneller als ein Byte-für-Byte-Vergleich.
Stellen Sie sicher, dass Sie berücksichtigen, wo sich Ihre Dateien befinden. Wenn Sie lokale Dateien mit einem Backup auf halbem Weg der Welt (oder über ein Netzwerk mit schrecklicher Bandbreite) vergleichen, ist es möglicherweise besser, zuerst einen Hash zu erstellen und eine Prüfsumme über das Netzwerk zu senden, anstatt einen Bytestrom an zu senden vergleichen Sie.
Kim
@ReedCopsey: Ich habe ein ähnliches Problem, da ich Eingabe- / Ausgabedateien speichern muss, die von mehreren Ausarbeitungen erstellt wurden, die viele Duplikate enthalten sollen. Ich dachte, vorberechneten Hash zu verwenden, aber kann ich davon ausgehen, dass wenn 2 (z. B. MD5) Hash gleich sind, die 2 Dateien gleich sind und ein weiterer Byte-2-Byte-Vergleich vermieden wird? Soweit ich weiß, sind Kollisionen mit MD5 / SHA1 usw. wirklich unwahrscheinlich ...
digEmAll
1
@digEmAll Die Kollisionswahrscheinlichkeit ist gering - Sie können jedoch immer einen stärkeren Hash ausführen - dh: Verwenden Sie SHA256 anstelle von SHA1, wodurch die Wahrscheinlichkeit von Kollisionen weiter verringert wird.
Reed Copsey
Vielen Dank für Ihre Antwort - ich komme gerade in .net. Ich gehe davon aus, dass, wenn man die Hashcode / Prüfsummen-Technik verwendet, die Hashes des Hauptordners irgendwo dauerhaft gespeichert werden. Aus Neugier würden Sie es für eine WPF-Anwendung speichern - was würden Sie tun? (Ich habe derzeit XML, Textdateien oder Datenbanken).
BKSpurgeon
139
Die langsamste Methode besteht darin, zwei Dateien byteweise zu vergleichen. Das schnellste, das ich finden konnte, ist ein ähnlicher Vergleich, aber anstelle von jeweils einem Byte würden Sie ein Array von Bytes mit der Größe Int64 verwenden und dann die resultierenden Zahlen vergleichen.
Folgendes habe ich mir ausgedacht:
constint BYTES_TO_READ =sizeof(Int64);staticboolFilesAreEqual(FileInfo first,FileInfo second){if(first.Length!= second.Length)returnfalse;if(string.Equals(first.FullName, second.FullName,StringComparison.OrdinalIgnoreCase))returntrue;int iterations =(int)Math.Ceiling((double)first.Length/ BYTES_TO_READ);
using (FileStream fs1 = first.OpenRead())
using (FileStream fs2 = second.OpenRead()){byte[] one =newbyte[BYTES_TO_READ];byte[] two =newbyte[BYTES_TO_READ];for(int i =0; i < iterations; i++){
fs1.Read(one,0, BYTES_TO_READ);
fs2.Read(two,0, BYTES_TO_READ);if(BitConverter.ToInt64(one,0)!=BitConverter.ToInt64(two,0))returnfalse;}}returntrue;}
Bei meinen Tests konnte ich feststellen, dass dies ein einfaches ReadByte () -Szenario um fast 3: 1 übertrifft. Im Durchschnitt über 1000 Läufe erhielt ich diese Methode bei 1063 ms und die folgende Methode (einfacher Byte-für-Byte-Vergleich) bei 3031 ms. Hashing kam mit durchschnittlich 865 ms immer im Sekundentakt zurück. Dieser Test wurde mit einer ~ 100 MB Videodatei durchgeführt.
Hier sind die ReadByte- und Hashing-Methoden, die ich zu Vergleichszwecken verwendet habe:
staticboolFilesAreEqual_OneByte(FileInfo first,FileInfo second){if(first.Length!= second.Length)returnfalse;if(string.Equals(first.FullName, second.FullName,StringComparison.OrdinalIgnoreCase))returntrue;
using (FileStream fs1 = first.OpenRead())
using (FileStream fs2 = second.OpenRead()){for(int i =0; i < first.Length; i++){if(fs1.ReadByte()!= fs2.ReadByte())returnfalse;}}returntrue;}staticboolFilesAreEqual_Hash(FileInfo first,FileInfo second){byte[] firstHash = MD5.Create().ComputeHash(first.OpenRead());byte[] secondHash = MD5.Create().ComputeHash(second.OpenRead());for(int i=0; i<firstHash.Length; i++){if(firstHash[i]!= secondHash[i])returnfalse;}returntrue;}
Du hast mir das Leben leichter gemacht. Vielen Dank
anindis
2
@anindis: Für Vollständigkeit, können Sie beide lesen Antwort @ Lars und @ RandomInsano Antwort . Ich bin froh, dass es so viele Jahre später geholfen hat! :)
chsh
1
Die FilesAreEqual_HashMethode sollte auch usingin beiden Dateistreams eine haben, wie die ReadByteMethode, sonst bleibt sie an beiden Dateien hängen.
Ian Mercer
2
Beachten Sie, dass FileStream.Read()möglicherweise weniger Bytes als die angeforderte Nummer gelesen werden. Sie sollten StreamReader.ReadBlock()stattdessen verwenden.
Palec
2
Wenn in der Int64-Version die Stream-Länge kein Vielfaches von Int64 ist, vergleicht die letzte Iteration die nicht gefüllten Bytes mit der Füllung der vorherigen Iteration (die ebenfalls gleich sein sollte, damit sie in Ordnung ist). Auch wenn die Stream-Länge kleiner als sizeof (Int64) ist, sind die nicht gefüllten Bytes 0, da C # Arrays initialisiert. IMO, der Code sollte diese Kuriositäten wahrscheinlich kommentieren.
Crokusek
46
Wenn Sie nicht entscheiden, dass Sie wirklich einen vollständigen Byte-für-Byte-Vergleich benötigen (siehe andere Antworten zur Diskussion des Hashings), ist die einfachste Lösung:
Im Gegensatz zu einigen anderen veröffentlichten Antworten ist dies für jede Art von Datei eindeutig korrekt : Binär, Text, Medien, ausführbare Datei usw., aber als vollständiger binärer Vergleich Dateien, die sich nur in "unwichtigen" Arten unterscheiden (wie Stückliste , Zeile) -end , Zeichenkodierung , Medienmetadaten, Leerzeichen, Auffüllen, Quellcodekommentare usw.) werden immer als ungleich betrachtet .
Dieser Code lädt beide Dateien vollständig in den Speicher, daher sollte er nicht zum Vergleichen wirklich gigantischer Dateien verwendet werden . Abgesehen von dieser wichtigen Einschränkung ist das vollständige Laden angesichts des Designs des .NET GC (da es grundlegend optimiert ist, um kleine, kurzlebige Zuordnungen extrem billig zu halten) keine wirkliche Strafe und könnte sogar optimal sein, wenn Dateigrößen erwartet werden auf weniger als 85K , da ein Minimum an Benutzercode verwenden (wie hier gezeigt) Datei Performance - Probleme auf die Delegation von maximal impliziert CLR, BCLund JITdie neueste Design - Technologie, System - Code und adaptive Laufzeit Optimierungen profitieren von (zB).
Darüber hinaus sind in solchen Workaday-Szenarien Bedenken hinsichtlich der Leistung des Byte-für-Byte-Vergleichs über LINQEnumeratoren (wie hier gezeigt) umstritten, da das Schlagen der Festplatte a filet / a̲l̲l̲ für Datei-E / A die Vorteile um mehrere Größenordnungen in den Schatten stellt der verschiedenen Speichervergleichsalternativen. Zum Beispiel, obwohl SequenceEquales uns tatsächlich die "Optimierung" gibt , bei der ersten Nichtübereinstimmung abzubrechen , spielt dies kaum eine Rolle, nachdem wir bereits den Inhalt der Dateien abgerufen haben, die jeweils vollständig erforderlich sind, um die Übereinstimmung zu bestätigen.
Dieser sieht für große Dateien nicht gut aus. Nicht gut für die Speichernutzung, da beide Dateien bis zum Ende gelesen werden, bevor mit dem Vergleich des Byte-Arrays begonnen wird. Deshalb würde ich mich lieber für einen Streamreader mit Puffer entscheiden.
Krypto_47
3
@ Krypto_47 Ich habe diese Faktoren und die angemessene Verwendung im Text meiner Antwort besprochen.
Glenn Slayden
33
Zusätzlich zu Reed Copseys Antwort:
Der schlimmste Fall ist, wenn die beiden Dateien identisch sind. In diesem Fall ist es am besten, die Dateien Byte für Byte zu vergleichen.
Wenn die beiden Dateien nicht identisch sind, können Sie die Dinge etwas beschleunigen, indem Sie früher erkennen, dass sie nicht identisch sind.
Wenn die beiden Dateien beispielsweise unterschiedlich lang sind, wissen Sie, dass sie nicht identisch sein können, und Sie müssen nicht einmal ihren tatsächlichen Inhalt vergleichen.
Um vollständig zu sein: Der andere große Gewinn stoppt, sobald die Bytes an 1 Position unterschiedlich sind.
Henk Holterman
6
@Henk: Ich fand das zu offensichtlich :-)
dtb
1
Guter Punkt, um dies hinzuzufügen. Es war für mich offensichtlich, also habe ich es nicht aufgenommen, aber es ist gut zu erwähnen.
Reed Copsey
16
Es wird noch schneller, wenn Sie nicht in kleinen 8-Byte-Blöcken lesen, sondern eine Schleife herumlegen und einen größeren Block lesen. Ich habe die durchschnittliche Vergleichszeit auf 1/4 reduziert.
publicstaticboolFilesContentsAreEqual(FileInfo fileInfo1,FileInfo fileInfo2){bool result;if(fileInfo1.Length!= fileInfo2.Length){
result =false;}else{
using (var file1 = fileInfo1.OpenRead()){
using (var file2 = fileInfo2.OpenRead()){
result =StreamsContentsAreEqual(file1, file2);}}}return result;}privatestaticboolStreamsContentsAreEqual(Stream stream1,Stream stream2){constint bufferSize =1024*sizeof(Int64);var buffer1 =newbyte[bufferSize];var buffer2 =newbyte[bufferSize];while(true){int count1 = stream1.Read(buffer1,0, bufferSize);int count2 = stream2.Read(buffer2,0, bufferSize);if(count1 != count2){returnfalse;}if(count1 ==0){returntrue;}int iterations =(int)Math.Ceiling((double)count1 /sizeof(Int64));for(int i =0; i < iterations; i++){if(BitConverter.ToInt64(buffer1, i *sizeof(Int64))!=BitConverter.ToInt64(buffer2, i *sizeof(Int64))){returnfalse;}}}}}
Im Allgemeinen ist die Prüfung count1 != count2nicht korrekt. Stream.Read()kann aus verschiedenen Gründen weniger als die von Ihnen angegebene Anzahl zurückgeben.
porges
1
Um sicherzustellen, dass der Puffer eine gerade Anzahl von Int64Blöcken enthält, können Sie die Größe wie folgt berechnen : const int bufferSize = 1024 * sizeof(Int64).
Jack A.
14
Das einzige, was einen Prüfsummenvergleich etwas schneller machen kann als einen byteweisen Vergleich, ist die Tatsache, dass Sie jeweils eine Datei lesen, was die Suchzeit für den Plattenkopf etwas verkürzt. Dieser leichte Gewinn kann jedoch sehr gut durch die zusätzliche Zeit der Berechnung des Hashs aufgefressen werden.
Außerdem kann ein Prüfsummenvergleich natürlich nur dann schneller sein, wenn die Dateien identisch sind. Wenn dies nicht der Fall ist, würde ein Byte-für-Byte-Vergleich beim ersten Unterschied enden und ihn viel schneller machen.
Sie sollten auch berücksichtigen, dass ein Hash-Code-Vergleich nur besagt, dass dies sehr wahrscheinlich ist dass die Dateien identisch sind. Um 100% sicher zu sein, müssen Sie einen byteweisen Vergleich durchführen.
Wenn der Hash-Code beispielsweise 32 Bit beträgt, sind Sie zu 99,99999998% sicher, dass die Dateien identisch sind, wenn die Hash-Codes übereinstimmen. Das ist fast 100%, aber wenn Sie wirklich 100% Sicherheit brauchen, ist es das nicht.
Wenn Sie einen größeren Hash verwenden, können Sie die Wahrscheinlichkeit eines falschen Positivs deutlich unter die Wahrscheinlichkeit bringen, dass der Computer während des Tests einen Fehler gemacht hat.
Loren Pechtel
Ich bin nicht einverstanden mit der Hash-Zeit und der Suchzeit. Sie können viele Berechnungen während einer einzelnen Kopfsuche durchführen. Wenn die Wahrscheinlichkeit hoch ist, dass die Dateien übereinstimmen, würde ich einen Hash mit vielen Bits verwenden. Wenn es eine vernünftige Chance auf eine Übereinstimmung gibt, würde ich sie Block für Block vergleichen, zum Beispiel 1-MB-Blöcke. (Wählen Sie eine Blockgröße, die 4k gleichmäßig teilt, um sicherzustellen, dass Sie niemals Sektoren teilen.)
Loren Pechtel
1
Um @ Guffas Zahl 99,99999998% zu erklären, stammt sie aus der Datenverarbeitung. Dies 1 - (1 / (2^32))ist die Wahrscheinlichkeit, dass eine einzelne Datei einen bestimmten 32-Bit-Hash hat. Die Wahrscheinlichkeit, dass zwei verschiedene Dateien denselben Hash haben, ist gleich, da die erste Datei den "angegebenen" Hashwert liefert und wir nur prüfen müssen, ob die andere Datei mit diesem Wert übereinstimmt oder nicht. Die Chancen mit 64- und 128-Bit-Hashing sinken auf 99,99999999999999999994% bzw. 99,99999999999999999999999999999999997%, als ob dies bei solch unergründlichen Zahlen von Bedeutung wäre.
Glenn Slayden
... In der Tat kann die Tatsache, dass diese Zahlen für die meisten Menschen schwerer zu verstehen sind als die mutmaßlich einfache, wenn auch zutreffende Vorstellung von "unendlich vielen Dateien, die in demselben Hash-Code kollidieren", erklären, warum Menschen unangemessen misstrauisch sind , Hash-as- zu akzeptieren Gleichberechtigung.
Glenn Slayden
13
Bearbeiten: Diese Methode würde nicht zum Vergleichen von Binärdateien funktionieren!
In .NET 4.0 verfügt die FileKlasse über die folgenden zwei neuen Methoden:
@dtb: Es funktioniert nicht für Binärdateien. Sie haben den Kommentar wahrscheinlich bereits eingegeben, als ich das erkannte und die Bearbeitung oben in meinem Beitrag hinzufügte. : o
Sam Harwell
@ 280Z28: Ich habe nichts gesagt
;-)
Müssen Sie nicht auch beide Dateien im Speicher speichern?
RandomInsano
Beachten Sie, dass File auch die Funktion ReadAllBytes hat, die auch SequenceEquals verwenden kann. Verwenden Sie diese Funktion stattdessen, da sie für alle Dateien funktionieren würde. Und wie @RandomInsano sagte, wird dies im Speicher gespeichert. Obwohl es für kleine Dateien absolut in Ordnung ist, würde ich es bei großen Dateien vorsichtig verwenden.
DaedalusAlpha
1
@DaedalusAlpha Es wird eine Aufzählung zurückgegeben, sodass die Zeilen bei Bedarf geladen und nicht die ganze Zeit im Speicher gespeichert werden. ReadAllBytes gibt dagegen die gesamte Datei als Array zurück.
IllidanS4 will Monica am
7
Ehrlich gesagt denke ich, dass Sie Ihren Suchbaum so weit wie möglich kürzen müssen.
Dinge zu überprüfen, bevor Sie Byte für Byte gehen:
Sind die Größen gleich?
Unterscheidet sich das letzte Byte in Datei A von Datei B.
Außerdem ist das gleichzeitige Lesen großer Blöcke effizienter, da Laufwerke sequentielle Bytes schneller lesen. Byteweise gehen führt nicht nur zu weitaus mehr Systemaufrufen, sondern auch dazu, dass der Lesekopf einer herkömmlichen Festplatte häufiger hin und her sucht, wenn sich beide Dateien auf derselben Festplatte befinden.
Lesen Sie Block A und Block B in einen Bytepuffer und vergleichen Sie sie (verwenden Sie NICHT Array.Equals, siehe Kommentare). Passen Sie die Größe der Blöcke an, bis Sie das erreichen, was Sie für einen guten Kompromiss zwischen Speicher und Leistung halten. Sie können den Vergleich auch mit mehreren Threads durchführen, die Festplattenlesevorgänge jedoch nicht mit mehreren Threads.
Die Verwendung von Array.Equals ist eine schlechte Idee, da das gesamte Array verglichen wird. Es ist wahrscheinlich, dass mindestens ein gelesener Block nicht das gesamte Array ausfüllt.
Doug Clutter
Warum ist es eine schlechte Idee, das gesamte Array zu vergleichen? Warum füllt ein Blocklesevorgang das Array nicht aus? Es gibt definitiv einen guten Abstimmungspunkt, aber deshalb spielt man mit den Größen. Zusätzliche Punkte für den Vergleich in einem separaten Thread.
RandomInsano
Wenn Sie ein Byte-Array definieren, hat es eine feste Länge. (zB - var buffer = new byte [4096]) Wenn Sie einen Block aus der Datei lesen, kann er die vollen 4096 Bytes zurückgeben oder nicht. Zum Beispiel, wenn die Datei nur 3000 Bytes lang ist.
Doug Clutter
Ah, jetzt verstehe ich! Eine gute Nachricht ist, dass der Lesevorgang die Anzahl der in das Array geladenen Bytes zurückgibt. Wenn das Array also nicht gefüllt werden kann, sind Daten vorhanden. Da wir auf Gleichheit testen, spielen alte Pufferdaten keine Rolle. Docs: msdn.microsoft.com/en-us/library/9kstw824(v=vs.110).aspx
RandomInsano
Wichtig ist auch, dass meine Empfehlung, die Equals () -Methode zu verwenden, eine schlechte Idee ist. In Mono führen sie einen Speichervergleich durch, da die Elemente im Speicher zusammenhängend sind. Microsoft überschreibt es jedoch nicht, sondern führt nur einen Referenzvergleich durch, der hier immer falsch wäre.
RandomInsano
4
Meine Antwort ist eine Ableitung von @lars, behebt aber den Fehler im Aufruf von Stream.Read. Ich füge auch einige schnelle Pfadüberprüfungen hinzu, die andere Antworten hatten, und eine Eingabevalidierung. Kurz gesagt, dies sollte die Antwort sein:
using System;
using System.IO;
namespace ConsoleApp4{classProgram{staticvoidMain(string[] args){var fi1 =newFileInfo(args[0]);var fi2 =newFileInfo(args[1]);Console.WriteLine(FilesContentsAreEqual(fi1, fi2));}publicstaticboolFilesContentsAreEqual(FileInfo fileInfo1,FileInfo fileInfo2){if(fileInfo1 ==null){thrownewArgumentNullException(nameof(fileInfo1));}if(fileInfo2 ==null){thrownewArgumentNullException(nameof(fileInfo2));}if(string.Equals(fileInfo1.FullName, fileInfo2.FullName,StringComparison.OrdinalIgnoreCase)){returntrue;}if(fileInfo1.Length!= fileInfo2.Length){returnfalse;}else{
using (var file1 = fileInfo1.OpenRead()){
using (var file2 = fileInfo2.OpenRead()){returnStreamsContentsAreEqual(file1, file2);}}}}privatestaticintReadFullBuffer(Stream stream,byte[] buffer){int bytesRead =0;while(bytesRead < buffer.Length){int read = stream.Read(buffer, bytesRead, buffer.Length- bytesRead);if(read ==0){// Reached end of stream.return bytesRead;}
bytesRead += read;}return bytesRead;}privatestaticboolStreamsContentsAreEqual(Stream stream1,Stream stream2){constint bufferSize =1024*sizeof(Int64);var buffer1 =newbyte[bufferSize];var buffer2 =newbyte[bufferSize];while(true){int count1 =ReadFullBuffer(stream1, buffer1);int count2 =ReadFullBuffer(stream2, buffer2);if(count1 != count2){returnfalse;}if(count1 ==0){returntrue;}int iterations =(int)Math.Ceiling((double)count1 /sizeof(Int64));for(int i =0; i < iterations; i++){if(BitConverter.ToInt64(buffer1, i *sizeof(Int64))!=BitConverter.ToInt64(buffer2, i *sizeof(Int64))){returnfalse;}}}}}}
Oder wenn Sie super-fantastisch sein möchten, können Sie die asynchrone Variante verwenden:
using System;
using System.IO;
using System.Threading.Tasks;
namespace ConsoleApp4{classProgram{staticvoidMain(string[] args){var fi1 =newFileInfo(args[0]);var fi2 =newFileInfo(args[1]);Console.WriteLine(FilesContentsAreEqualAsync(fi1, fi2).GetAwaiter().GetResult());}publicstaticasyncTask<bool>FilesContentsAreEqualAsync(FileInfo fileInfo1,FileInfo fileInfo2){if(fileInfo1 ==null){thrownewArgumentNullException(nameof(fileInfo1));}if(fileInfo2 ==null){thrownewArgumentNullException(nameof(fileInfo2));}if(string.Equals(fileInfo1.FullName, fileInfo2.FullName,StringComparison.OrdinalIgnoreCase)){returntrue;}if(fileInfo1.Length!= fileInfo2.Length){returnfalse;}else{
using (var file1 = fileInfo1.OpenRead()){
using (var file2 = fileInfo2.OpenRead()){returnawaitStreamsContentsAreEqualAsync(file1, file2).ConfigureAwait(false);}}}}privatestaticasyncTask<int>ReadFullBufferAsync(Stream stream,byte[] buffer){int bytesRead =0;while(bytesRead < buffer.Length){int read =await stream.ReadAsync(buffer, bytesRead, buffer.Length- bytesRead).ConfigureAwait(false);if(read ==0){// Reached end of stream.return bytesRead;}
bytesRead += read;}return bytesRead;}privatestaticasyncTask<bool>StreamsContentsAreEqualAsync(Stream stream1,Stream stream2){constint bufferSize =1024*sizeof(Int64);var buffer1 =newbyte[bufferSize];var buffer2 =newbyte[bufferSize];while(true){int count1 =awaitReadFullBufferAsync(stream1, buffer1).ConfigureAwait(false);int count2 =awaitReadFullBufferAsync(stream2, buffer2).ConfigureAwait(false);if(count1 != count2){returnfalse;}if(count1 ==0){returntrue;}int iterations =(int)Math.Ceiling((double)count1 /sizeof(Int64));for(int i =0; i < iterations; i++){if(BitConverter.ToInt64(buffer1, i *sizeof(Int64))!=BitConverter.ToInt64(buffer2, i *sizeof(Int64))){returnfalse;}}}}}}
wäre das Bitkonverter-Bit nicht besser als `` `für (var i = 0; i <count; i + = sizeof (long)) {if (BitConverter.ToInt64 (buffer1, i)! = BitConverter.ToInt64 (buffer2, i)) { falsch zurückgeben; }} `` `
Simon
2
Meine Experimente zeigen, dass es definitiv hilfreich ist, Stream.ReadByte () weniger oft aufzurufen, aber die Verwendung von BitConverter zum Packen von Bytes macht keinen großen Unterschied zum Vergleich von Bytes in einem Byte-Array.
Es ist also möglich, diese "Math.Ceiling and Iterations" -Schleife im obigen Kommentar durch die einfachste zu ersetzen:
for(int i =0; i < count1; i++){if(buffer1[i]!= buffer2[i])returnfalse;}
Ich denke, es hat damit zu tun, dass BitConverter.ToInt64 vor dem Vergleich ein wenig Arbeit erledigen muss (Argumente überprüfen und dann die Bitverschiebung durchführen), und dies entspricht dem Arbeitsaufwand für den Vergleich von 8 Bytes in zwei Arrays .
Array.Equals geht tiefer in das System hinein, daher ist es wahrscheinlich viel schneller als Byte für Byte in C #. Ich kann nicht für Microsoft sprechen, aber tief im Inneren verwendet Mono den Befehl memcpy () von C für die Array-Gleichheit. Schneller geht es nicht.
RandomInsano
2
@ RandomInsano denke, Sie meinen memcmp (), nicht memcpy ()
SQL Police
1
Wenn die Dateien nicht zu groß sind, können Sie Folgendes verwenden:
publicstaticbyte[]ComputeFileHash(string fileName){
using (var stream =File.OpenRead(fileName))returnSystem.Security.Cryptography.MD5.Create().ComputeHash(stream);}
Es ist nur möglich, Hashes zu vergleichen, wenn die Hashes zum Speichern nützlich sind.
Eine weitere Verbesserung bei großen Dateien mit identischer Länge könnte darin bestehen, die Dateien nicht nacheinander zu lesen, sondern mehr oder weniger zufällige Blöcke zu vergleichen.
Sie können mehrere Threads verwenden, die an verschiedenen Positionen in der Datei beginnen und entweder vorwärts oder rückwärts vergleichen.
Auf diese Weise können Sie Änderungen in der Mitte / am Ende der Datei schneller erkennen, als Sie es mit einem sequentiellen Ansatz erreichen würden.
Würde das Festplatten-Thrashing hier Probleme verursachen?
RandomInsano
Physische Festplatten ja, SSDs würden das erledigen.
TheLegendaryCopyCoder
1
Wenn Sie nur zwei Dateien vergleichen müssen, ist der schnellste Weg (in C weiß ich nicht, ob er auf .NET anwendbar ist).
öffne beide Dateien f1, f2
Holen Sie sich die jeweilige Dateilänge l1, l2
wenn l1! = l2 sind die Dateien unterschiedlich; halt
mmap () beide Dateien
Verwenden Sie memcmp () für die mmap () ed-Dateien
OTOH, wenn Sie herausfinden müssen, ob in einem Satz von N Dateien doppelte Dateien vorhanden sind, ist der schnellste Weg zweifellos die Verwendung eines Hashs, um N-Wege-Bit-für-Bit-Vergleiche zu vermeiden.
Im Folgenden finden Sie einige Dienstprogrammfunktionen, mit denen Sie feststellen können, ob zwei Dateien (oder zwei Streams) identische Daten enthalten.
Ich habe eine "schnelle" Version bereitgestellt, die Multithread-fähig ist, da sie Byte-Arrays (jeder Puffer wird aus den in jeder Datei gelesenen Daten gefüllt) in verschiedenen Threads mithilfe von Aufgaben vergleicht.
Wie erwartet ist es viel schneller (ungefähr 3x schneller), verbraucht aber mehr CPU (weil es Multithread-fähig ist) und mehr Speicher (weil es zwei Byte-Array-Puffer pro Vergleichsthread benötigt).
publicstaticboolAreFilesIdenticalFast(string path1,string path2){returnAreFilesIdentical(path1, path2,AreStreamsIdenticalFast);}publicstaticboolAreFilesIdentical(string path1,string path2){returnAreFilesIdentical(path1, path2,AreStreamsIdentical);}publicstaticboolAreFilesIdentical(string path1,string path2,Func<Stream,Stream,bool> areStreamsIdentical){if(path1 ==null)thrownewArgumentNullException(nameof(path1));if(path2 ==null)thrownewArgumentNullException(nameof(path2));if(areStreamsIdentical ==null)thrownewArgumentNullException(nameof(path2));if(!File.Exists(path1)||!File.Exists(path2))returnfalse;
using (var thisFile =newFileStream(path1,FileMode.Open,FileAccess.Read,FileShare.ReadWrite)){
using (var valueFile =newFileStream(path2,FileMode.Open,FileAccess.Read,FileShare.ReadWrite)){if(valueFile.Length!= thisFile.Length)returnfalse;if(!areStreamsIdentical(thisFile, valueFile))returnfalse;}}returntrue;}publicstaticboolAreStreamsIdenticalFast(Stream stream1,Stream stream2){if(stream1 ==null)thrownewArgumentNullException(nameof(stream1));if(stream2 ==null)thrownewArgumentNullException(nameof(stream2));constint bufsize =80000;// 80000 is below LOH (85000)var tasks =newList<Task<bool>>();do{// consumes more memory (two buffers for each tasks)var buffer1 =newbyte[bufsize];var buffer2 =newbyte[bufsize];int read1 = stream1.Read(buffer1,0, buffer1.Length);if(read1 ==0){int read3 = stream2.Read(buffer2,0,1);if(read3 !=0)// not eofreturnfalse;break;}// both stream read could return different countsint read2 =0;do{int read3 = stream2.Read(buffer2, read2, read1 - read2);if(read3 ==0)returnfalse;
read2 += read3;}while(read2 < read1);// consumes more cpuvar task =Task.Run(()=>{returnIsSame(buffer1, buffer2);});
tasks.Add(task);}while(true);Task.WaitAll(tasks.ToArray());return!tasks.Any(t =>!t.Result);}publicstaticboolAreStreamsIdentical(Stream stream1,Stream stream2){if(stream1 ==null)thrownewArgumentNullException(nameof(stream1));if(stream2 ==null)thrownewArgumentNullException(nameof(stream2));constint bufsize =80000;// 80000 is below LOH (85000)var buffer1 =newbyte[bufsize];var buffer2 =newbyte[bufsize];var tasks =newList<Task<bool>>();do{int read1 = stream1.Read(buffer1,0, buffer1.Length);if(read1 ==0)return stream2.Read(buffer2,0,1)==0;// check not eof// both stream read could return different countsint read2 =0;do{int read3 = stream2.Read(buffer2, read2, read1 - read2);if(read3 ==0)returnfalse;
read2 += read3;}while(read2 < read1);if(!IsSame(buffer1, buffer2))returnfalse;}while(true);}publicstaticboolIsSame(byte[] bytes1,byte[] bytes2){if(bytes1 ==null)thrownewArgumentNullException(nameof(bytes1));if(bytes2 ==null)thrownewArgumentNullException(nameof(bytes2));if(bytes1.Length!= bytes2.Length)returnfalse;for(int i =0; i < bytes1.Length; i++){if(bytes1[i]!= bytes2[i])returnfalse;}returntrue;}
Ich denke, es gibt Anwendungen, bei denen "Hash" schneller ist als der Vergleich von Byte für Byte. Wenn Sie eine Datei mit anderen vergleichen müssen oder eine Miniaturansicht eines Fotos haben, die sich ändern kann. Es hängt davon ab, wo und wie es verwendet wird.
Noch eine Antwort, abgeleitet von @chsh. MD5 mit Verwendungen und Verknüpfungen für Datei gleich, Datei existiert nicht und unterschiedliche Längen:
/// <summary>/// Performs an md5 on the content of both files and returns true if/// they match/// </summary>/// <param name="file1">first file</param>/// <param name="file2">second file</param>/// <returns>true if the contents of the two files is the same, false otherwise</returns>publicstaticboolIsSameContent(string file1,string file2){if(file1 == file2)returntrue;FileInfo file1Info =newFileInfo(file1);FileInfo file2Info =newFileInfo(file2);if(!file1Info.Exists&&!file2Info.Exists)returntrue;if(!file1Info.Exists&& file2Info.Exists)returnfalse;if(file1Info.Exists&&!file2Info.Exists)returnfalse;if(file1Info.Length!= file2Info.Length)returnfalse;
using (FileStream file1Stream = file1Info.OpenRead())
using (FileStream file2Stream = file2Info.OpenRead()){byte[] firstHash = MD5.Create().ComputeHash(file1Stream);byte[] secondHash = MD5.Create().ComputeHash(file2Stream);for(int i =0; i < firstHash.Length; i++){if(i>=secondHash.Length||firstHash[i]!= secondHash[i])returnfalse;}returntrue;}}
Antworten:
Ein Prüfsummenvergleich ist höchstwahrscheinlich langsamer als ein byteweiser Vergleich.
Um eine Prüfsumme zu generieren, müssen Sie jedes Byte der Datei laden und die Verarbeitung durchführen. Sie müssen dies dann für die zweite Datei tun. Die Verarbeitung wird mit ziemlicher Sicherheit langsamer sein als die Vergleichsprüfung.
So generieren Sie eine Prüfsumme: Mit den Kryptografieklassen können Sie dies problemlos tun. Hier ist ein kurzes Beispiel für das Generieren einer MD5-Prüfsumme mit C #.
Eine Prüfsumme kann jedoch schneller und sinnvoller sein, wenn Sie die Prüfsumme des Falls "Test" oder "Basis" vorberechnen können. Wenn Sie über eine vorhandene Datei verfügen und prüfen, ob eine neue Datei mit der vorhandenen identisch ist, bedeutet die Vorberechnung der Prüfsumme für Ihre "vorhandene" Datei, dass Sie das DiskIO nur einmal ausführen müssen neue Datei. Dies wäre wahrscheinlich schneller als ein Byte-für-Byte-Vergleich.
quelle
Die langsamste Methode besteht darin, zwei Dateien byteweise zu vergleichen. Das schnellste, das ich finden konnte, ist ein ähnlicher Vergleich, aber anstelle von jeweils einem Byte würden Sie ein Array von Bytes mit der Größe Int64 verwenden und dann die resultierenden Zahlen vergleichen.
Folgendes habe ich mir ausgedacht:
Bei meinen Tests konnte ich feststellen, dass dies ein einfaches ReadByte () -Szenario um fast 3: 1 übertrifft. Im Durchschnitt über 1000 Läufe erhielt ich diese Methode bei 1063 ms und die folgende Methode (einfacher Byte-für-Byte-Vergleich) bei 3031 ms. Hashing kam mit durchschnittlich 865 ms immer im Sekundentakt zurück. Dieser Test wurde mit einer ~ 100 MB Videodatei durchgeführt.
Hier sind die ReadByte- und Hashing-Methoden, die ich zu Vergleichszwecken verwendet habe:
quelle
FilesAreEqual_Hash
Methode sollte auchusing
in beiden Dateistreams eine haben, wie dieReadByte
Methode, sonst bleibt sie an beiden Dateien hängen.FileStream.Read()
möglicherweise weniger Bytes als die angeforderte Nummer gelesen werden. Sie solltenStreamReader.ReadBlock()
stattdessen verwenden.Wenn Sie nicht entscheiden, dass Sie wirklich einen vollständigen Byte-für-Byte-Vergleich benötigen (siehe andere Antworten zur Diskussion des Hashings), ist die einfachste Lösung:
• für
System.IO.FileInfo
Beispiele:• für
System.String
Pfadnamen:Im Gegensatz zu einigen anderen veröffentlichten Antworten ist dies für jede Art von Datei eindeutig korrekt : Binär, Text, Medien, ausführbare Datei usw., aber als vollständiger binärer Vergleich Dateien, die sich nur in "unwichtigen" Arten unterscheiden (wie Stückliste , Zeile) -end , Zeichenkodierung , Medienmetadaten, Leerzeichen, Auffüllen, Quellcodekommentare usw.) werden immer als ungleich betrachtet .
Dieser Code lädt beide Dateien vollständig in den Speicher, daher sollte er nicht zum Vergleichen wirklich gigantischer Dateien verwendet werden . Abgesehen von dieser wichtigen Einschränkung ist das vollständige Laden angesichts des Designs des .NET GC (da es grundlegend optimiert ist, um kleine, kurzlebige Zuordnungen extrem billig zu halten) keine wirkliche Strafe und könnte sogar optimal sein, wenn Dateigrößen erwartet werden auf weniger als 85K , da ein Minimum an Benutzercode verwenden (wie hier gezeigt) Datei Performance - Probleme auf die Delegation von maximal impliziert
CLR
,BCL
undJIT
die neueste Design - Technologie, System - Code und adaptive Laufzeit Optimierungen profitieren von (zB).Darüber hinaus sind in solchen Workaday-Szenarien Bedenken hinsichtlich der Leistung des Byte-für-Byte-Vergleichs über
LINQ
Enumeratoren (wie hier gezeigt) umstritten, da das Schlagen der Festplatte a filet / a̲l̲l̲ für Datei-E / A die Vorteile um mehrere Größenordnungen in den Schatten stellt der verschiedenen Speichervergleichsalternativen. Zum Beispiel, obwohlSequenceEqual
es uns tatsächlich die "Optimierung" gibt , bei der ersten Nichtübereinstimmung abzubrechen , spielt dies kaum eine Rolle, nachdem wir bereits den Inhalt der Dateien abgerufen haben, die jeweils vollständig erforderlich sind, um die Übereinstimmung zu bestätigen.quelle
Zusätzlich zu Reed Copseys Antwort:
Der schlimmste Fall ist, wenn die beiden Dateien identisch sind. In diesem Fall ist es am besten, die Dateien Byte für Byte zu vergleichen.
Wenn die beiden Dateien nicht identisch sind, können Sie die Dinge etwas beschleunigen, indem Sie früher erkennen, dass sie nicht identisch sind.
Wenn die beiden Dateien beispielsweise unterschiedlich lang sind, wissen Sie, dass sie nicht identisch sein können, und Sie müssen nicht einmal ihren tatsächlichen Inhalt vergleichen.
quelle
Es wird noch schneller, wenn Sie nicht in kleinen 8-Byte-Blöcken lesen, sondern eine Schleife herumlegen und einen größeren Block lesen. Ich habe die durchschnittliche Vergleichszeit auf 1/4 reduziert.
quelle
count1 != count2
nicht korrekt.Stream.Read()
kann aus verschiedenen Gründen weniger als die von Ihnen angegebene Anzahl zurückgeben.Int64
Blöcken enthält, können Sie die Größe wie folgt berechnen :const int bufferSize = 1024 * sizeof(Int64)
.Das einzige, was einen Prüfsummenvergleich etwas schneller machen kann als einen byteweisen Vergleich, ist die Tatsache, dass Sie jeweils eine Datei lesen, was die Suchzeit für den Plattenkopf etwas verkürzt. Dieser leichte Gewinn kann jedoch sehr gut durch die zusätzliche Zeit der Berechnung des Hashs aufgefressen werden.
Außerdem kann ein Prüfsummenvergleich natürlich nur dann schneller sein, wenn die Dateien identisch sind. Wenn dies nicht der Fall ist, würde ein Byte-für-Byte-Vergleich beim ersten Unterschied enden und ihn viel schneller machen.
Sie sollten auch berücksichtigen, dass ein Hash-Code-Vergleich nur besagt, dass dies sehr wahrscheinlich ist dass die Dateien identisch sind. Um 100% sicher zu sein, müssen Sie einen byteweisen Vergleich durchführen.
Wenn der Hash-Code beispielsweise 32 Bit beträgt, sind Sie zu 99,99999998% sicher, dass die Dateien identisch sind, wenn die Hash-Codes übereinstimmen. Das ist fast 100%, aber wenn Sie wirklich 100% Sicherheit brauchen, ist es das nicht.
quelle
1 - (1 / (2^32))
ist die Wahrscheinlichkeit, dass eine einzelne Datei einen bestimmten 32-Bit-Hash hat. Die Wahrscheinlichkeit, dass zwei verschiedene Dateien denselben Hash haben, ist gleich, da die erste Datei den "angegebenen" Hashwert liefert und wir nur prüfen müssen, ob die andere Datei mit diesem Wert übereinstimmt oder nicht. Die Chancen mit 64- und 128-Bit-Hashing sinken auf 99,99999999999999999994% bzw. 99,99999999999999999999999999999999997%, als ob dies bei solch unergründlichen Zahlen von Bedeutung wäre.Bearbeiten: Diese Methode würde nicht zum Vergleichen von Binärdateien funktionieren!
In .NET 4.0 verfügt die
File
Klasse über die folgenden zwei neuen Methoden:Was bedeutet, dass Sie verwenden könnten:
quelle
Ehrlich gesagt denke ich, dass Sie Ihren Suchbaum so weit wie möglich kürzen müssen.
Dinge zu überprüfen, bevor Sie Byte für Byte gehen:
Außerdem ist das gleichzeitige Lesen großer Blöcke effizienter, da Laufwerke sequentielle Bytes schneller lesen. Byteweise gehen führt nicht nur zu weitaus mehr Systemaufrufen, sondern auch dazu, dass der Lesekopf einer herkömmlichen Festplatte häufiger hin und her sucht, wenn sich beide Dateien auf derselben Festplatte befinden.
Lesen Sie Block A und Block B in einen Bytepuffer und vergleichen Sie sie (verwenden Sie NICHT Array.Equals, siehe Kommentare). Passen Sie die Größe der Blöcke an, bis Sie das erreichen, was Sie für einen guten Kompromiss zwischen Speicher und Leistung halten. Sie können den Vergleich auch mit mehreren Threads durchführen, die Festplattenlesevorgänge jedoch nicht mit mehreren Threads.
quelle
Meine Antwort ist eine Ableitung von @lars, behebt aber den Fehler im Aufruf von
Stream.Read
. Ich füge auch einige schnelle Pfadüberprüfungen hinzu, die andere Antworten hatten, und eine Eingabevalidierung. Kurz gesagt, dies sollte die Antwort sein:Oder wenn Sie super-fantastisch sein möchten, können Sie die asynchrone Variante verwenden:
quelle
Meine Experimente zeigen, dass es definitiv hilfreich ist, Stream.ReadByte () weniger oft aufzurufen, aber die Verwendung von BitConverter zum Packen von Bytes macht keinen großen Unterschied zum Vergleich von Bytes in einem Byte-Array.
Es ist also möglich, diese "Math.Ceiling and Iterations" -Schleife im obigen Kommentar durch die einfachste zu ersetzen:
Ich denke, es hat damit zu tun, dass BitConverter.ToInt64 vor dem Vergleich ein wenig Arbeit erledigen muss (Argumente überprüfen und dann die Bitverschiebung durchführen), und dies entspricht dem Arbeitsaufwand für den Vergleich von 8 Bytes in zwei Arrays .
quelle
Wenn die Dateien nicht zu groß sind, können Sie Folgendes verwenden:
Es ist nur möglich, Hashes zu vergleichen, wenn die Hashes zum Speichern nützlich sind.
(Der Code wurde etwas sauberer bearbeitet.)
quelle
Eine weitere Verbesserung bei großen Dateien mit identischer Länge könnte darin bestehen, die Dateien nicht nacheinander zu lesen, sondern mehr oder weniger zufällige Blöcke zu vergleichen.
Sie können mehrere Threads verwenden, die an verschiedenen Positionen in der Datei beginnen und entweder vorwärts oder rückwärts vergleichen.
Auf diese Weise können Sie Änderungen in der Mitte / am Ende der Datei schneller erkennen, als Sie es mit einem sequentiellen Ansatz erreichen würden.
quelle
Wenn Sie nur zwei Dateien vergleichen müssen, ist der schnellste Weg (in C weiß ich nicht, ob er auf .NET anwendbar ist).
OTOH, wenn Sie herausfinden müssen, ob in einem Satz von N Dateien doppelte Dateien vorhanden sind, ist der schnellste Weg zweifellos die Verwendung eines Hashs, um N-Wege-Bit-für-Bit-Vergleiche zu vermeiden.
quelle
Etwas (hoffentlich) einigermaßen Effizientes:
quelle
Im Folgenden finden Sie einige Dienstprogrammfunktionen, mit denen Sie feststellen können, ob zwei Dateien (oder zwei Streams) identische Daten enthalten.
Ich habe eine "schnelle" Version bereitgestellt, die Multithread-fähig ist, da sie Byte-Arrays (jeder Puffer wird aus den in jeder Datei gelesenen Daten gefüllt) in verschiedenen Threads mithilfe von Aufgaben vergleicht.
Wie erwartet ist es viel schneller (ungefähr 3x schneller), verbraucht aber mehr CPU (weil es Multithread-fähig ist) und mehr Speicher (weil es zwei Byte-Array-Puffer pro Vergleichsthread benötigt).
quelle
Ich denke, es gibt Anwendungen, bei denen "Hash" schneller ist als der Vergleich von Byte für Byte. Wenn Sie eine Datei mit anderen vergleichen müssen oder eine Miniaturansicht eines Fotos haben, die sich ändern kann. Es hängt davon ab, wo und wie es verwendet wird.
Hier können Sie das bekommen, was am schnellsten ist.
Optional können wir den Hash in einer Datenbank speichern.
Hoffe das kann helfen
quelle
Noch eine Antwort, abgeleitet von @chsh. MD5 mit Verwendungen und Verknüpfungen für Datei gleich, Datei existiert nicht und unterschiedliche Längen:
quelle
if (i>=secondHash.Length ...
unter welchen Umständen wären zwei MD5-Hashes unterschiedlich lang?Dies funktioniert gut, wenn man zuerst die Länge vergleicht, ohne Daten zu lesen, und dann die Lese-Byte-Sequenz vergleicht
quelle