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

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

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

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

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

EDIT:

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

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

Ответ 7

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

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

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

Ответ 8

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

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

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

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

Ответ 9

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

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

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

Ответ 10

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

Ответ 11

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

Ответ 12

Зачем изобретать колесо? Как насчет стороннего приложения? Конечно, у него нет API-интерфейсов, но я не думаю, что вы часто помещаете себя в эту ситуацию. Мне нравится это приложение doublekiller просто создайте резервную копию перед запуском.:) Это быстро и бесплатно!

Ответ 13

Сначала сравните длины файлов всех миллионов. Если у вас есть дешевый способ сделать это, начните с самых больших файлов. Если все они пройдут, то сравните каждый файл, используя двоичный паттерн разделения; это приведет к сбою быстрее в файлах, похожих друг на друга, но не одинаковых. Для получения информации об этом методе сравнения см. метод Кнут-Моррис-Пратт.

Ответ 14

Я только что написал приложение С#, которое делает что-то похожее на то, что вы хотите. Что мой код делает это.

Прочитайте все размеры каждого файла в списке или массиве.

Используйте цикл for, чтобы проверить, одинаковы ли эти размеры. если они имеют одинаковый размер, сравните байт одного файла с байтом другого файла. Если два байта одинаковы, переходите к следующему байту. Если разница найдена, верните, что файлы разные.

Если конец обоих файлов достигнут, а последние два байта одинаковы, файлы должны быть идентичными.

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

Ответ 15

Используйте концепцию Bloom Filter. Простое объяснение здесь: http://crzyjcky.com/2013/01/03/the-magical-bloom-filter/

Это дает вам постоянное время сравнения. Однако этот метод нельзя использовать в одиночку. Apache Cassandra и HBase используют этот метод внутри.

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

Ответ 16

По-моему, это операция файловой системы. Итак, сначала выберите свою файловую систему с осторожностью. Затем дедуплицируем. Затем сравните inodes. Как:

% find / -inum "$(ls -di "./test.file" | grep -E '^[0-9]*')"
<list of identical files provided in a few seconds to a minute>

Ответ 17

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