сравнете съдържанието на големи файлове

Ако наистина трябва да гарантирате 100%, че файловете са 100% идентични, тогава трябва да направите сравнение байт към байт. Това просто е включено в проблема - единственият метод за хеширане с 0% риск от фалшиво съвпадение е функцията за идентичност!

Това, което ни остава, са преки пътища, които могат бързо да ни дадат бързи отговори, за да прескочим сравнението байт по байт някои от времето.

По правило единственият пряк път за доказване на равенство е доказването на идентичност. В OO код, който ще показва два обекта, където всъщност е един и същ обект. Най-близкото нещо във файловете е, ако обвързване или NTFS съединение означава, че два пътя са към един и същ файл. Това се случва толкова рядко, че освен ако естеството на работата не го направи по-обичайно от нормалното, няма да бъде чиста печалба за проверка.

Така че ни остава кратък път за намиране на несъответствия. Не прави нищо, за да увеличи пропуските ни, но прави пропуските ни по-бързи:

1. Различен размер, не равен байт по байт. Простички!
2. Ако ще прегледате един и същ файл повече от веднъж, хеширайте го и запишете хеша. Различен хеш, гарантирано не равен. Намаляването на файловете, които се нуждаят от сравнение едно към едно, е огромно.
3. Много файлови формати вероятно имат някои общи области. Особено първите байтове за много формати обикновено са "магически числа", заглавки и т.н. Или ги пропуснете, или пропуснете тогава и след това проверете последното (ако има шанс да са различни, но е нисък).

След това е въпросът да направите действителното сравнение възможно най-бързо. Зареждането на партиди от 4 октета наведнъж в цяло число и извършването на сравнение на цели числа често ще бъде по-бързо от октет по октет.

Нарязването на резби може да помогне. Един от начините е да разделите действителното сравнение на файла на повече от една операция, но ако е възможно по-голяма печалба ще бъде намерена чрез извършване на напълно различни сравнения в различни нишки. Трябва да знам малко повече за това, което правите, за да давам много съвети, но основното нещо е да се уверя, че резултатът от тестовете е безопасен за нишки.

Ако имате повече от една нишка, разглеждаща едни и същи файлове, накарайте ги да работят далеч една от друга. напр. ако имате четири нишки, можете да разделите файла на четири или можете да имате един да вземе байт 0, 4, 8, докато друг вземе байт 1, 5, 9 и т.н. (или 4-октетна група 0, 4, 8 и т.н. ). Последното е много по-вероятно да има проблеми с фалшиво споделяне от първото, така че не го правете .

Редактиране:

Зависи и какво точно правите с файловете. Казвате, че се нуждаете от 100% сигурност, така че тази част не се отнася за вас, но си струва да добавите за по-общия проблем, че ако цената на фалшиво положителен резултат е загуба на ресурси, време или памет, а не действителен провал , тогава намаляването му чрез размит пряк път може да бъде нетна печалба и може да си струва профилиране, за да видите дали това е така.

Ако използвате хеш, за да ускорите нещата (поне може да намери някои определени несъответствия по-бързо), тогава Призрачният хеш на Боб Дженкинс е добър избор; не е криптографски защитен, но ако това не е целта ви, той създава като 128-битов хеш много бързо (много по-бързо от криптографския хеш или дори от подходите, предприети с много GetHashCode() реализации), които са изключително добри, за да нямат случайни сблъсъци ( вид умишлени сблъсъци, избягване на криптографски хешове е друг въпрос). Приложих го за .Net и го сложих на nuget, защото никой друг нямаше, когато установих, че искам да го използвате.

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

Размер(и) на тестови файлове: 118 MB
Продължителност: 579 ms
Равно ли е? вярно

    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 MB
Продължителност: 340 ms
Равно ли е? вярно

    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 MB
Продължителност: 702 ms
Равно ли е? вярно

    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 MB би трябвало да е добре за много големи файлове)

Целта е да се уверите, че можете да направите сравнението си толкова бързо, колкото твърдият диск може да прочете данните, и че винаги четете данни без забавяне. Ако правите всичко толкова бързо, колкото данните могат да бъдат прочетени от устройството, това е толкова бързо, колкото е възможно да го направите, тъй като скоростта на четене на твърдия диск се превръща в тясното място.

В крайна сметка хешът така или иначе ще прочете файла байт по байт ... така че ако търсите точно сравнение, тогава можете да направите сравнението. Можете ли да дадете малко повече информация за това, което се опитвате да постигнете? Колко големи са „големите“ файлове? Колко често трябва да ги сравнявате?

Ако имате голям набор от файлове и се опитвате да идентифицирате дубликати, ще се опитам да разбия работата по ред на разходите. Може да опитам нещо като следното:

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

По този начин не зареждате твърде много заедно и не четете целия файл, ако откриете несъответствие по-рано. Трябва да настроите тест, който променя размера на парчето, за да определите правилния размер за оптимална производителност.