Поиск дубликатов файлов - C# предпочтительно

Question

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

1. Получить хэш-код уникального файла.
2. Сравните хэш-код уникального файла с хэш-кодом каждого файла на файловом сервере. Если равно, добавьте в список дубликатов.

Это делает работу, но принимает навсегда (я имею 200к файлы на файловом сервере), так что я должен был думать о чем-то еще, и это то, что я сделал:

1. Получить хэш-код уникального файла ,
2. Получите размер уникального файла в байтах.
3. Получить список всех файлов, имеющих одинаковый размер файла (это очень быстро, так как мне не нужно читать файлы)
4. Сравните хэш-код уникального файла с каждым файлом из файлов с кратким списком.

Это сократило время, требуемое для выполнения задачи, от нескольких часов до 10 минут, но это все еще не очень хорошо, особенно при попытке найти дубликаты для кучи файлов. Каждый поиск файлов в течение 10 минут означает, что 100 файлов займут 16 часов!

Есть ли уникальный идентификатор файла лучше, чем хеш-код? получение хеш-кода - это трудоемкая вещь в этом процессе.

Спасибо,

Answer 1

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

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

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

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

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

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

Answer 2

Поиск дубликатов по hashcode определенно является самым медленным способом; много дисковых операций ввода-вывода и процессора.

У меня есть некоторый опыт в этой области, и мы нашли fastert подход устранить файлы как можно скорее:

1. Короткий список, группируя по размеру файла
2. Сравните первые 256 байт всех эти файлы на группу, байт по байт. Это должно устранить много файлов.
3. петли на шаге 2, но в два раза больше размера буфера на каждой итерации (с макс 16K или около того)

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