Какой самый быстрый способ проверить, идентичны ли файлы?

Question

Если у вас есть 1 000 000 исходных файлов, вы подозреваете, что они все одинаковы, и вы хотите сравнить их, каков текущий ускоренный метод для сравнения этих файлов? Предположим, что это файлы Java, и платформа, на которой выполняется сравнение, не важна. cksum заставляет меня плакать. Когда я имею в виду идентичные, я имею в виду ВСЕ идентичные.

Обновление: Я знаю о создании контрольных сумм. Дифф смехотворен ... Я хочу скорость.

Обновление: Не зацикливайтесь на том факте, что они являются исходными файлами. Представьте, например, что вы взяли миллион прогонов программы с очень регулируемым выходом. Вы хотите доказать, что все 1 000 000 версий вывода одинаковы.

Обновление: читать количество блоков, а не байтов? Сразу выкинуть? Это быстрее, чем найти количество байтов?

Обновление: Отличается ли это ЛЮБЫМ от самого быстрого способа сравнения двух файлов?

Answer 1

Я бы выбрал что-то вроде подхода, принятого программой cmp: откройте два файла (скажем, файл 1 и файл 2), прочитайте блок из каждого и сравните их побайтно. Если они совпадают, прочитайте следующий блок из каждого, сравните их побайтно и т. Д. Если вы дошли до конца обоих файлов, не обнаружив никаких различий, найдите начало файла 1, закройте файл 2 и откройте файл 3 на своем месте, и повторяйте, пока вы не проверили все файлы. Я не думаю, что есть какой-либо способ избежать чтения всех байтов всех файлов, если они на самом деле все идентичны, но я думаю, что этот подход является (или близок к) наиболее быстрым способом обнаружения любых различий, которые могут существовать.

Модификация OP : Поднят важный комментарий с Марк Бесси

"Еще одна очевидная оптимизация, если ожидается, что файлы будут в основном идентичными, и если они относительно малы, - это сохранение одного из файлов полностью в памяти. Это сокращает время перебора при попытке чтения двух файлов одновременно. «

Answer 2

Большинство людей в своих ответах игнорируют тот факт, что файлы должны сравниваться неоднократно. Таким образом, контрольные суммы быстрее, поскольку контрольная сумма рассчитывается один раз и сохраняется в памяти (вместо последовательного чтения файлов n раз).

Answer 3

Если предположить, что файлы будут одинаковыми (похоже, что это сценарий), то обработка контрольных сумм / хэшей - пустая трата времени - вероятно, они будут одинаковыми, и вы получите перечитать файлы, чтобы получить окончательное доказательство (я также предполагаю, что, поскольку вы хотите «доказать ... они одинаковы», то иметь хеш с одинаковым значением недостаточно).

Если это так, я думаю, что решение, предложенное Дэвидом , довольно близко к тому, что вам нужно сделать. Пара вещей, которые можно сделать, чтобы оптимизировать сравнение при повышении уровня сложности:

• перед сравнением проверьте, совпадают ли размеры файлов.
• используйте самую быструю функцию memcmp (), которую вы можете (сравнивая слова вместо байтов - большинство сред выполнения C должны это уже делать)
• использовать несколько потоков для сравнения блоков памяти (вплоть до числа процессоров, доступных в системе, при превышении которого ваш поток будет сражаться друг с другом)
• использование перекрывающихся / асинхронных операций ввода-вывода для обеспечения максимально возможной загруженности каналов ввода-вывода, а также тщательного профилирования, чтобы вы как можно меньше переключались между файлами (если файлы разделены между несколькими различными дисками и ввода-вывода порты, все к лучшему)

Answer 4

Обновление: не зацикливайтесь на том, что они являются исходными файлами. Представьте, например, что вы взяли миллион прогонов программы с очень регулируемым выходом. Вы хотите доказать, что все 1 000 000 версий выходных данных одинаковы.

если у вас есть контроль над выводом, программа, создающая файлы / вывод, создаст md5 на лету и вставит его в файл или выходной поток или даже направит вывод через программу, которая создает md5 по пути и сохраняет как-то по сторонам данных, главное - сделать вычисления, когда байты уже находятся в памяти.

если вы не можете выполнить это, то, как уже говорили другие, проверьте размеры файлов, затем проведите прямое байтовое сравнение для файлов одинакового размера, я не вижу, как какой-либо вид двоичного деления или вычисления md5 лучше чем прямое сравнение, вам придется прикасаться к каждому байту, чтобы доказать равенство при любом его разрезании, чтобы вы могли также сократить объем вычислений, необходимых для каждого байта, и получить возможность обрезать, как только вы обнаружите несоответствие.

расчет md5 был бы полезен, если вы планируете сравнить их позже с новыми выходами, но вы в основном вернулись к моей первой точке вычисления md5 как можно скорее

Answer 5

Ну, самый оптимальный алгоритм будет зависеть от количества дубликатов файлов.

Предполагается, что некоторые из них одинаковы, но большинство из них разные, а файлы большие.

Отфильтруйте те, которые явно не совпадают, используя простую проверку длины файла.

Выберите случайные байты из файла, вычислите хеш и сравните (сворачивая поиск диска)

Следуйте этому с полным файлом SHA1.

Answer 6

Существует ряд программ, которые сравнивают набор файлов в целом, чтобы найти идентичные. FDUPES хороший: Ссылка . Миллион файлов не должен быть проблемой, в зависимости от точного характера ввода. Я думаю, что FDUPES требует Linux, но есть и другие подобные программы для других платформ.

Я пытался написать более быструю программу, но за исключением особых случаев, FDUPES был быстрее.

В любом случае, общая идея - начать с проверки размеров файлов. Файлы разных размеров не могут быть одинаковыми, поэтому вам нужно только посмотреть на группы файлов одинакового размера. Тогда это становится более сложным, если вам нужна оптимальная производительность: если файлы могут отличаться, вы должны сравнивать небольшие части файлов в надежде на раннее обнаружение различий, чтобы вам не приходилось читать остальные. Однако если файлы, вероятно, будут идентичными, то будет проще прочитать каждый файл для вычисления контрольной суммы, потому что тогда вы можете читать последовательно с диска вместо того, чтобы перемещаться между двумя или более файлами. (Это предполагает нормальные диски, поэтому SSD: s могут отличаться.)

В моих тестах, когда я пытался сделать более быструю программу, оказалось, что (к моему удивлению) быстрее было сначала прочитать каждый файл для вычисления контрольной суммы, а затем, если контрольные суммы были равны, сравнить файлы напрямую, прочитав блоки поочередно из каждого файла, чем просто читать блоки поочередно без предыдущих вычислений контрольной суммы! Оказалось, что при вычислении контрольных сумм Linux кэшировал оба файла в оперативной памяти, последовательно читая каждый файл, и второе чтение было тогда очень быстрым. При запуске с чередующимися чтениями файлы (физически) не читались последовательно.

EDIT:

Некоторые люди выражали удивление и даже сомнение, что чтение файлов может быть быстрее, чем чтение только один раз. Возможно, мне не удалось объяснить очень четко, что я делал. Я имею в виду предварительную загрузку кеша, чтобы файлы были в кеше диска при последующем доступе к ним так, как это было бы медленно на физическом диске. Здесь - это веб-страница, на которой я пытался объяснить более подробно, с изображениями, кодом C и измерениями.

Однако это имеет (в лучшем случае) незначительное отношение к первоначальному вопросу.

Answer 7

Я не думаю, что хеширование будет быстрее, чем байтовое сравнение. Побайтовое сравнение может быть немного оптимизировано путем конвейерного чтения и сравнения байтов, а также можно сравнивать несколько разделов файла в параллельных потоках. Было бы пойти что-то вроде этого:

• Проверьте, отличаются ли размеры файлов
• Асинхронное чтение блоков файлов в память
• Передайте их рабочим потокам для сравнения

Или просто запустите cmp (или эквивалент для вашей ОС) параллельно. Это может быть легко написано, и вы все равно получите преимущество параллелизма.

Answer 8

Я бы запустил что-то вроде этого

find -name \*.java -print0 | xargs -0 md5sum | sort

затем посмотрите, какие файлы имеют разные суммы MD5. Это сгруппирует файлы по контрольной сумме.

Вы можете заменить md5sum на sha1sum или даже rmd160, если хотите.

Answer 9

Использование cksum не так надежно, как использование чего-то вроде md5sum. Но я бы выбрал максимальную надежность, что означает побайтовое сравнение с использованием cmp.

Вы должны прочитать каждый байт в обоих файлах для всех методов проверки, поэтому вы также можете выбрать наиболее надежный.

В качестве первого прохода вы можете проверить список каталогов, чтобы увидеть, отличаются ли размеры. Это быстрый способ получить более быструю обратную связь для разных файлов.

Answer 10

Если вы хотите сравнить файлы один за другим, используйте ExamDiff.