Typowe podejścia zalecają czytanie pliku binarnego za pośrednictwem FileStream i porównywanie go bajt po bajcie.
- Czy porównanie sum kontrolnych, takich jak CRC, byłoby szybsze?
- Czy istnieją biblioteki .NET, które mogą generować sumę kontrolną dla pliku?
Odpowiedzi:
Porównanie sum kontrolnych najprawdopodobniej będzie wolniejsze niż porównanie bajt po bajcie.
Aby wygenerować sumę kontrolną, musisz załadować każdy bajt pliku i wykonać na nim przetwarzanie. Będziesz musiał to zrobić na drugim pliku. Przetwarzanie będzie prawie na pewno wolniejsze niż kontrola porównawcza.
Jeśli chodzi o generowanie sumy kontrolnej: Możesz to łatwo zrobić za pomocą klas kryptografii. Oto krótki przykład generowania sumy kontrolnej MD5 w języku C #.
Jednak suma kontrolna może być szybsza i mieć więcej sensu, jeśli można wstępnie obliczyć sumę kontrolną przypadku „testowego” lub „podstawowego”. Jeśli masz istniejący plik i sprawdzasz, czy nowy plik jest taki sam jak istniejący, wstępne obliczenie sumy kontrolnej na „istniejącym” pliku oznaczałoby konieczność wykonania DiskIO tylko raz, na nowy plik. Prawdopodobnie byłoby to szybsze niż porównanie bajt po bajcie.
źródło
Najwolniejszą możliwą metodą jest porównywanie dwóch plików bajt po bajcie. Najszybsze, jakie udało mi się wymyślić, to podobne porównanie, ale zamiast jednego bajtu na raz, użyjesz tablicy bajtów o rozmiarze Int64, a następnie porównasz wynikowe liczby.
Oto, co wymyśliłem:
W moich testach mogłem zobaczyć, że to przewyższa prosty scenariusz ReadByte () o prawie 3: 1. Uśredniony ponad 1000 uruchomień, otrzymałem tę metodę przy 1063 ms, a metodę poniżej (proste porównanie bajt po bajcie) przy 3031 ms. Haszowanie zawsze wracało poniżej sekundy, średnio około 865 ms. Ten test dotyczył pliku wideo ~ 100 MB.
Oto metody ReadByte i haszujące, których użyłem do celów porównawczych:
źródło
FilesAreEqual_Hash
Metoda powinna miećusing
zarówno pliku strumieni zbyt podobnie jakReadByte
metody inaczej będzie powiesić na obu plików.FileStream.Read()
może faktycznie odczytać mniej bajtów niż żądana liczba. Zamiast tego powinieneś użyćStreamReader.ReadBlock()
.Jeśli nie zdecydujesz, że naprawdę potrzebujesz pełnego porównania bajt po bajcie (zobacz inne odpowiedzi w celu omówienia haszowania), najłatwiejszym rozwiązaniem jest:
• na
System.IO.FileInfo
przykład:• dla
System.String
nazw ścieżek:W przeciwieństwie do innych opublikowanych odpowiedzi, jest to bezsprzecznie poprawne dla każdego rodzaju plików: binarnych, tekstowych, multimedialnych, wykonywalnych itp., Ale jako pełne porównanie binarne pliki, które różnią się tylko w „nieistotny” sposób (np. BOM , wiersz -ending , kodowanie znaków , metadane multimediów, spacje, dopełnienie, komentarze w kodzie źródłowym itp.) zawsze będą uważane za nierówne .
Ten kod ładuje oba pliki w całości do pamięci, więc nie powinien być używany do porównywania naprawdę gigantycznych plików . Poza tym ważnym zastrzeżeniem, pełne ładowanie nie jest tak naprawdę karą, biorąc pod uwagę projekt .NET GC (ponieważ jest zasadniczo zoptymalizowany, aby utrzymywać bardzo niskie , krótkotrwałe alokacje niezwykle tanie ), a w rzeczywistości może być nawet optymalne, gdy oczekuje się rozmiaru pliku powinna być mniejsza niż 85k , ponieważ przy użyciu minimum kodu użytkownika (patrz tutaj) implikuje maksymalnie delegowanie problemów z wydajnością do pliku
CLR
,BCL
orazJIT
do korzystania z (na przykład) najnowszej technologii projektowania, kod systemu i adaptacyjnych optymalizacje uruchomieniowych.Ponadto w takich scenariuszach dnia roboczego obawy dotyczące wydajności porównywania bajt po bajcie za pomocą modułów
LINQ
wyliczających (jak pokazano tutaj) są dyskusyjne, ponieważ uderzenie w dysk a̲t̲ a̲l̲l̲ dla wejścia / wyjścia pliku przyćmiewa o kilka rzędów wielkości korzyści różnych alternatyw porównujących pamięć. Na przykład, choćSequenceEqual
nie w rzeczywistości daje nam „Optymalizacja” z porzucenie na pierwszym niedopasowania , to nie ma znaczenia po już pobrana zawartość pliki, każdy w pełni należy potwierdzić meczu ..źródło
Oprócz odpowiedzi Reeda Copseya :
W najgorszym przypadku oba pliki są identyczne. W takim przypadku najlepiej porównać pliki bajt po bajcie.
Jeśli dwa pliki nie są identyczne, możesz nieco przyspieszyć działanie, wykrywając wcześniej, że nie są identyczne.
Na przykład, jeśli dwa pliki mają różną długość, wiesz, że nie mogą być identyczne i nie musisz nawet porównywać ich rzeczywistej zawartości.
źródło
Robi się jeszcze szybciej, jeśli nie czytasz małych 8-bajtowych fragmentów, ale umieszczasz pętlę, odczytując większy fragment. Skróciłem średni czas porównania do 1/4.
źródło
count1 != count2
nie jest poprawna.Stream.Read()
może zwrócić mniej niż podana liczba z różnych powodów.Int64
bloków, można obliczyć wielkość takiego:const int bufferSize = 1024 * sizeof(Int64)
.Jedyną rzeczą, która może sprawić, że porównanie sum kontrolnych będzie nieco szybsze niż porównanie bajt po bajcie, to fakt, że czytasz jeden plik na raz, co nieco skraca czas wyszukiwania głowicy dysku. Ten niewielki zysk może jednak zostać zjedzony przez dodatkowy czas obliczania hasha.
Oczywiście porównanie sum kontrolnych ma szansę być szybsze tylko wtedy, gdy pliki są identyczne. Jeśli tak nie jest, porównanie bajt po bajcie zakończyłoby się przy pierwszej różnicy, co znacznie przyspieszyło.
Należy również wziąć pod uwagę, że porównanie kodu skrótu mówi tylko, że jest to bardzo prawdopodobne że pliki są identyczne. Aby mieć 100% pewności, musisz porównać bajt po bajcie.
Jeśli na przykład kod skrótu ma 32 bity, masz około 99,999999998% pewności, że pliki są identyczne, jeśli kody skrótu są zgodne. To prawie 100%, ale jeśli naprawdę potrzebujesz 100% pewności, to nie wszystko.
źródło
1 - (1 / (2^32))
, co jest prawdopodobieństwem, że dowolny plik będzie miał 32-bitowy hash. Prawdopodobieństwo, że dwa różne pliki będą miały tę samą wartość skrótu jest takie samo, ponieważ pierwszy plik zawiera „podaną” wartość skrótu i musimy tylko rozważyć, czy drugi plik pasuje do tej wartości. Szanse z 64- i 128-bitowym haszowaniem spadają do 99.999999999999999994% i 99.9999999999999999999999999999999999997% (odpowiednio), jakby to miało znaczenie przy tak niewyobrażalnych liczbach.Edycja: ta metoda nie zadziała przy porównywaniu plików binarnych!
W .NET 4.0
File
klasa ma następujące dwie nowe metody:Co oznacza, że możesz użyć:
źródło
Szczerze mówiąc, myślę, że musisz przyciąć swoje drzewo wyszukiwania tak bardzo, jak to możliwe.
Rzeczy do sprawdzenia przed przejściem bajt po bajcie:
Również jednoczesne odczytywanie dużych bloków będzie bardziej wydajne, ponieważ dyski szybciej odczytują kolejne bajty. Przechodzenie bajt po bajcie powoduje nie tylko znacznie więcej wywołań systemowych, ale także powoduje, że głowica czytająca tradycyjnego dysku twardego częściej szuka tam i z powrotem, jeśli oba pliki znajdują się na tym samym dysku.
Odczytaj fragment A i fragment B do bufora bajtowego i porównaj je (NIE używaj Array.Equals, patrz komentarze). Dostosuj rozmiar bloków, aż osiągniesz to, co uważasz za dobrą kompromis między pamięcią a wydajnością. Możesz również wielowątkowość porównania, ale nie wielowątkowość odczytów dysku.
źródło
Moja odpowiedź jest pochodną @lars, ale naprawia błąd w wywołaniu
Stream.Read
. Dodam również szybkie sprawdzanie ścieżki, które miały inne odpowiedzi, i walidację danych wejściowych. W skrócie, to powinno być odpowiedź:A jeśli chcesz być super-niesamowity, możesz użyć wariantu asynchronicznego:
źródło
Moje eksperymenty pokazują, że zdecydowanie pomaga wywołać Stream.ReadByte () mniej razy, ale użycie BitConverter do pakowania bajtów nie robi dużej różnicy w porównaniu z porównywaniem bajtów w tablicy bajtów.
Można więc zastąpić pętlę „Math.Ceiling and iterations” w powyższym komentarzu na najprostszą:
Wydaje mi się, że ma to związek z faktem, że BitConverter.ToInt64 musi wykonać trochę pracy (sprawdzić argumenty, a następnie wykonać przesunięcie bitowe) przed porównaniem, a to kończy się taką samą ilością pracy, jak porównanie 8 bajtów w dwóch tablicach .
źródło
Jeśli pliki nie są zbyt duże, możesz użyć:
Porównywanie skrótów będzie możliwe tylko wtedy, gdy będą one przydatne do przechowywania.
(Zmodyfikowałem kod na coś znacznie bardziej przejrzystego).
źródło
Innym ulepszeniem w przypadku dużych plików o identycznej długości może być nie odczytywanie plików po kolei, a raczej porównywanie mniej lub bardziej losowych bloków.
Możesz używać wielu wątków, zaczynając od różnych pozycji w pliku i porównując do przodu lub do tyłu.
W ten sposób możesz wykryć zmiany w środku / na końcu pliku, szybciej niż w przypadku podejścia sekwencyjnego.
źródło
Jeśli potrzebujesz tylko porównać dwa pliki, myślę, że najszybszym sposobem byłoby (w C nie wiem, czy ma to zastosowanie do .NET)
OTOH, jeśli chcesz sprawdzić, czy w zestawie N plików znajdują się zduplikowane pliki, najszybszym sposobem jest niewątpliwie użycie skrótu, aby uniknąć N-stronnych porównań bit po bicie.
źródło
Coś (miejmy nadzieję) w miarę wydajnego:
źródło
Oto kilka funkcji narzędziowych, które pozwalają określić, czy dwa pliki (lub dwa strumienie) zawierają identyczne dane.
Udostępniłem „szybką” wersję, która jest wielowątkowa, ponieważ porównuje tablice bajtów (każdy bufor wypełniony z tego, co zostało odczytane w każdym pliku) w różnych wątkach przy użyciu zadań.
Zgodnie z oczekiwaniami jest znacznie szybszy (około 3x szybszy), ale zużywa więcej procesora (ponieważ jest wielowątkowy) i więcej pamięci (ponieważ potrzebuje dwóch bajtowych buforów tablicy na wątek porównania).
źródło
Myślę, że są aplikacje, w których „mieszanie” jest szybsze niż porównywanie bajt po bajcie. Jeśli chcesz porównać plik z innymi lub mieć miniaturę zdjęcia, które można zmienić. To zależy od tego, gdzie i jak jest używany.
Tutaj możesz uzyskać to, co jest najszybsze.
Opcjonalnie możemy zapisać hash w bazie danych.
Mam nadzieję, że to pomoże
źródło
Jeszcze inna odpowiedź, pochodząca z @chsh. MD5 z zastosowaniami i skrótami do pliku to samo, plik nie istnieje i różne długości:
źródło
if (i>=secondHash.Length ...
jakich okolicznościach dwa skróty MD5 miałyby różne długości?To, jak odkryłem, działa dobrze, porównując najpierw długość bez czytania danych, a następnie porównując odczytaną sekwencję bajtów
źródło