Быстрее ли? При чтении файла частями по 9.24МиБ и расчете MD4/SHA1 хешей загрузка процессора E6550 не превышает 10%, а скорость ограничивается 100МиБ/с. Тут ограничивающим фактором выступает не мощность процессора, а ограничение I/O системы.
С одной стороны механизм на обычных хешах очень сильно проседает при коллизии, с другой механизм прямых сравнений - на множестве файлов одинакового размера (попробуйте поискать дубликаты среди 100 образом виртуальных машин по 5Гиб
).
Впрочем проблема коллизий разрешается довольно просто: хеш нужно считать не от целого файла, а от блоков фиксированного размера. (Это не я придумал - в ed2k/AICH, BitTorrent клиентах это уже есть)
Согласен. Фактически скорость вычисления MD5(openssl) в 2-3 раза быстрее чтения с диска, соответственно для вычисления контрольной суммы не имеет смысла использовать xor или подобные быстрые алгоритмы с высоким уровнем коллизий.
Мы решаем задачу по поиску дубликатов файлов и соответственно должны учесть все проблемы с этим связанные. Если решать задачу универсально, то можно составить такой алгоритм:
0) Имеем(получаем) список файлов(путей)
1) Получаем канонические пути, сортируем и отсеиваем дубликаты
2) Получаем размеры, сортируем и разделяем на пачки с одинаковым размером, отсеиваем уникальные
3) Далее работаем с каждой пачкой в которой файлы имеют одинаковый размер
4) Определяем sparthash и sfullhash, sparthash <= sfullhash, где
sparthash - размер блока(куска большого файла) для вычисления частичного хеша(например от начала файла)
sfullhash - максимального размер файла для вычисления хеша на всем файле
5) Для пачек с размером файлов > sfullhash, вычисляем hash на размере sparthash, сортируем и отбрасываем уникальные, разбиваем на пачки с одинаковым hash
6) Далее с каждой пачкой с размером файлов <= sfullhash и пачек полученных на шаге 5 работаем одинаково
7) Вычисляем hash для каждого файла пачки, сортируем и отбрасываем уникальные, разбиваем на пачки с одинаковым hash
8.) Теперь имеем пачки с одинаковым hash, с очень очень высокой вероятностью они одинаковы, но мы не можем этого гарантировать! Далее работаем с каждой такой пачкой
9) Делаем побайтное сравнение файлов в пачке, но не каждого с каждым, а последовательно:
1-й со 2-м, 2-й с 3-м, 3-й с 4-м, ... N-1 c N
10) С очень очень высокой вероятность мы получим, что 1==2==3==4==...==N, и таким образом удостоверимся в идентичности файлов
11) В редких ситуациях будем иметь что то подобное: 1==2<3==4>...<N.
12) Для однознаковых последовательностей, по знакам "<" и ">", например:
1==2<3==4<...<N. или 1==2>3==4>...>N.
Все тривиально!
13) Для неоднознаковых, убираем дубликаты, и сортируем. Алгоритм сортировки выбираем с наименьшим кол-вом сравнений элементов, кол-во перемещений роли не играет. Во время сортировки(и до нее - для исходной последовательности) запоминаем отношения сравниваемых файлов между собой(<>=), чтобы не делать повторные сравнения во время сортировки и после нее.
14) Шаг 13 очень маловероятен, но возможен и должен оптимизироваться только по кол-ву попарных сравнений - как можно меньше.
