сравнить содержимое больших файлов

Если вам действительно нужно гарантировать 100% 100% идентичность файлов, вам необходимо выполнить побайтовое сравнение. Это как раз и влечет за собой проблему — единственный метод хеширования с нулевым риском ложного совпадения — это функция тождества!

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

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

Таким образом, у нас остается короткий путь к поиску несоответствий. Ничего не делает для увеличения наших проходов, но ускоряет наши неудачи:

1. Разный размер, не побайтно равный. Простые!
2. Если вы будете проверять один и тот же файл более одного раза, хешируйте его и запишите хэш. Разный хэш, гарантированно не равный. Сокращение файлов, требующих прямого сравнения, огромно.
3. Многие форматы файлов, вероятно, имеют некоторые общие области. В частности, первые байты для многих форматов имеют тенденцию быть «магическими числами», заголовками и т. Д. Либо пропустите их, либо пропустите затем, а затем проверьте последним (если есть вероятность того, что они разные, но это мало).

Затем нужно сделать фактическое сравнение как можно быстрее. Загрузка пакетов из 4 октетов за раз в целое число и выполнение целочисленного сравнения часто будет быстрее, чем октет на октет.

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

Если у вас есть более одного потока, исследующего одни и те же файлы, пусть они работают далеко друг от друга. Например. если у вас четыре потока, вы можете разбить файл на четыре, или вы можете сделать так, чтобы один принимал байты 0, 4, 8, а другой — байты 1, 5, 9 и т. д. (или 4-октетная группа 0, 4, 8 и т. д. ). В последнем гораздо чаще возникают проблемы с ложным обменом, чем в первом, поэтому не делайте этого. .

Редактировать:

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

Если вы используете хэш для ускорения работы (по крайней мере, он может быстрее находить определенные несоответствия), тогда Spooky Hash Боба Дженкинса — хороший выбор; он не является криптографически безопасным, но если это не является вашей целью, он очень быстро создает 128-битный хэш (намного быстрее, чем криптографический хэш или даже чем подходы, применяемые во многих реализациях GetHashCode()), которые чрезвычайно хороши для предотвращения случайных коллизий (т. другое дело — преднамеренные коллизии, которых избегают криптографические хэши). Я реализовал его для .Net и поместил его в nuget, потому что ни у кого больше не было, когда я обнаружил, что хочу использовать его.

Серийное сравнение

Размер тестового файла: 118 МБ
Продолжительность: 579 мс
Равно? истинный

    static bool Compare(string filePath1, string filePath2)
    {
        using (FileStream file = File.OpenRead(filePath1))
        {
            using (FileStream file2 = File.OpenRead(filePath2))
            {
                if (file.Length != file2.Length)
                {
                    return false;
                }

                int count;
                const int size = 0x1000000;

                var buffer = new byte[size];
                var buffer2 = new byte[size];

                while ((count = file.Read(buffer, 0, buffer.Length)) > 0)
                {
                    file2.Read(buffer2, 0, buffer2.Length);

                    for (int i = 0; i < count; i++)
                    {
                        if (buffer[i] != buffer2[i])
                        {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }

Параллельное сравнение

Размер (-а) тестового файла: 118 МБ
Продолжительность: 340 мс
Одинаково? истинный

    static bool Compare2(string filePath1, string filePath2)
    {
        bool success = true;

        var info = new FileInfo(filePath1);
        var info2 = new FileInfo(filePath2);

        if (info.Length != info2.Length)
        {
            return false;
        }

        long fileLength = info.Length;
        const int size = 0x1000000;

        Parallel.For(0, fileLength / size, x =>
        {
            var start = (int)x * size;

            if (start >= fileLength)
            {
                return;
            }

            using (FileStream file = File.OpenRead(filePath1))
            {
                using (FileStream file2 = File.OpenRead(filePath2))
                {
                    var buffer = new byte[size];
                    var buffer2 = new byte[size];

                    file.Position = start;
                    file2.Position = start;

                    int count = file.Read(buffer, 0, size);
                    file2.Read(buffer2, 0, size);

                    for (int i = 0; i < count; i++)
                    {
                        if (buffer[i] != buffer2[i])
                        {
                            success = false;
                            return;
                        }
                    }
                }
            }
        });

        return success;
    }

MD5 Сравнить

Размер тестового файла: 118 МБ
Продолжительность: 702 мс
Равно? истинный

    static bool Compare3(string filePath1, string filePath2)
    {
        byte[] hash1 = GenerateHash(filePath1);
        byte[] hash2 = GenerateHash(filePath2);

        if (hash1.Length != hash2.Length)
        {
            return false;
        }

        for (int i = 0; i < hash1.Length; i++)
        {
            if (hash1[i] != hash2[i])
            {
                return false;
            }
        }

        return true;
    }

    static byte[] GenerateHash(string filePath)
    {
        MD5 crypto = MD5.Create();

        using (FileStream stream = File.OpenRead(filePath))
        {
            return crypto.ComputeHash(stream);
        }
    }

tl;dr Параллельно сравнивайте сегменты байтов, чтобы определить, равны ли два файла.

Почему не оба?

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

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

Итак, есть две вещи, которые вам нужно решить:

• Параллелизм. Убедитесь, что вы читаете данные одновременно с их проверкой.
• Размер буфера. Чтение файла по 1 байту за раз будет медленным, убедитесь, что вы читаете его в буфер приличного размера (около 8 МБ должно подойти для очень больших файлов).

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

В конечном счете, хэш все равно будет считывать файл побайтно... поэтому, если вы ищете точное сравнение, вы можете сделать сравнение. Можете ли вы рассказать больше о том, чего вы пытаетесь достичь? Насколько велики «большие» файлы? Как часто вам приходится их сравнивать?

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

1) группировать файлы по размеру. Файлы разного размера явно не могут быть одинаковыми. Эту информацию очень недорого получить. Если каждая группа содержит только 1 файл, все готово, дубликатов нет, в противном случае переходите к шагу 2.

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

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

Чтобы вычислить хеш, нужно прочитать весь файл.

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

Псевдокод:

open file A
open file B
while file A has more data
{
    if next chunk of A != next chunk of B return false
}
return true

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