Какой самый быстрый способ сравнить два байтовых массива?

Question

Я пытаюсь сравнить два длинных байт-массива в VB.NET и столкнулся с загадкой. Сравнение двух 50-мегабайтных файлов занимает почти две минуты, поэтому я явно что-то делаю не так. Я на машине x64 с тоннами памяти, поэтому там нет проблем. Вот код, который я сейчас использую и хочу изменить.

_Bytes и item.Bytes - это два различных массива для сравнения, которые уже имеют одинаковую длину.

For Each B In item.Bytes
   If B <> _Bytes(I) Then
        Mismatch = True
        Exit For
   End If
   I += 1
Next

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

Item.bytes - это объект, взятый из базы данных / файловой системы, который возвращается для сравнения, поскольку его длина в байтах соответствует элементу, который пользователь хочет добавить. Сравнивая два массива, я могу определить, добавил ли пользователь что-то новое в БД, и если нет, то я могу просто сопоставить их с другим файлом и не тратить место на жестком диске.

[Update]

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

Answer 1

Что делает вызов _Bytes(I)? Это не загрузка файла каждый раз, не так ли? Даже с буферизацией это будет плохой новостью!

Будет много способов микрооптимизировать это с точки зрения просмотра длинных за один раз, потенциально использования небезопасного кода и т. Д., Но я бы просто сконцентрировался на получении разумного производительность в первую очередь. Очевидно, что происходит что-то очень странное.

Я предлагаю вам извлечь код сравнения в отдельную функцию, которая принимает два байтовых массива. Таким образом, вы знаете, что не будете делать ничего странного. В этом случае я бы также использовал простой цикл For вместо For Each - это будет проще. Да, и проверьте правильность длины сначала:)

РЕДАКТИРОВАТЬ: Вот код (не проверенный, но достаточно простой), который я бы использовал. Это на C # на минуту - я преобразую его в секунду:

public static bool Equals(byte[] first, byte[] second)
{
    if (first == second)
    {
        return true;
    }
    if (first == null || second == null)
    {
        return false;
    }
    if (first.Length != second.Length)
    {
        return false;
    }
    for (int i=0; i < first.Length; i++)
    {
        if (first[i] != second[i])                
        {
            return false;
        }
    }
    return true;
}

РЕДАКТИРОВАТЬ: И вот VB:

Public Shared Function ArraysEqual(ByVal first As Byte(), _
                                   ByVal second As Byte()) As Boolean
    If (first Is second) Then
        Return True
    End If

    If (first Is Nothing OrElse second Is Nothing) Then
        Return False
    End If
    If  (first.Length <> second.Length) Then
         Return False
    End If

    For i as Integer = 0 To first.Length - 1
        If (first(i) <> second(i)) Then
            Return False
        End If
    Next i
    Return True
End Function

Answer 2

Самый быстрый способ сравнения двухбайтовых массивов одинакового размера - использовать interop. Запустите следующий код в консольном приложении:

using System;
using System.Runtime.InteropServices;
using System.Security;

namespace CompareByteArray
{
    class Program
    {
        static void Main(string[] args)
        {
            const int SIZE = 100000;
            const int TEST_COUNT = 100;

            byte[] arrayA = new byte[SIZE];
            byte[] arrayB = new byte[SIZE];

            for (int i = 0; i < SIZE; i++)
            {
                arrayA[i] = 0x22;
                arrayB[i] = 0x22;
            }

            {
                DateTime before = DateTime.Now;
                for (int i = 0; i < TEST_COUNT; i++)
                {
                    int result = MemCmp_Safe(arrayA, arrayB, (UIntPtr)SIZE);

                    if (result != 0) throw new Exception();
                }
                DateTime after = DateTime.Now;

                Console.WriteLine("MemCmp_Safe: {0}", after - before);
            }

            {
                DateTime before = DateTime.Now;
                for (int i = 0; i < TEST_COUNT; i++)
                {
                    int result = MemCmp_Unsafe(arrayA, arrayB, (UIntPtr)SIZE);

                    if (result != 0) throw new Exception();
                }
                DateTime after = DateTime.Now;

                Console.WriteLine("MemCmp_Unsafe: {0}", after - before);
            }


            {
                DateTime before = DateTime.Now;
                for (int i = 0; i < TEST_COUNT; i++)
                {
                    int result = MemCmp_Pure(arrayA, arrayB, SIZE);

                    if (result != 0) throw new Exception();
                }
                DateTime after = DateTime.Now;

                Console.WriteLine("MemCmp_Pure: {0}", after - before);
            }
            return;
        }

        [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl, EntryPoint="memcmp", ExactSpelling=true)]
        [SuppressUnmanagedCodeSecurity]
        static extern int memcmp_1(byte[] b1, byte[] b2, UIntPtr count);

        [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl, EntryPoint = "memcmp", ExactSpelling = true)]
        [SuppressUnmanagedCodeSecurity]
        static extern unsafe int memcmp_2(byte* b1, byte* b2, UIntPtr count);

        public static int MemCmp_Safe(byte[] a, byte[] b, UIntPtr count)
        {
            return memcmp_1(a, b, count);
        }

        public unsafe static int MemCmp_Unsafe(byte[] a, byte[] b, UIntPtr count)
        {
            fixed(byte* p_a = a)
            {
                fixed (byte* p_b = b)
                {
                    return memcmp_2(p_a, p_b, count);
                }
            }
        }

        public static int MemCmp_Pure(byte[] a, byte[] b, int count)
        {
            int result = 0;
            for (int i = 0; i < count && result == 0; i += 1)
            {
                result = a[0] - b[0];
            }

            return result;
        }

    }
}

Answer 3

Если вам не нужно знать байт, используйте 64-битные числа, которые дают вам 8 одновременно. На самом деле, вы можете определить неправильный байт, как только вы изолировали его от набора 8.

Использование BinaryReader :

saveTime  = binReader.ReadInt32()

Или для массивов целых:

Dim count As Integer = binReader.Read(testArray, 0, 3)

Answer 4

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

Answer 5

Не относится строго к алгоритму сравнения:

Вы уверены, что ваше узкое место не связано с доступной памятью и временем, используемым для загрузки байтовых массивов? Загрузка двух 2 ГБ байтовых массивов только для сравнения может поставить большинство машин на колени. Если дизайн программы позволяет, попробуйте вместо этого использовать потоки для чтения небольших фрагментов.

Answer 6

Я вижу две вещи, которые могут помочь:

Во-первых, вместо того, чтобы всегда обращаться ко второму массиву как item.Bytes, используйте локальную переменную, чтобы указать непосредственно на массив. То есть перед запуском цикла сделайте что-то вроде этого:

 array2 = item.Bytes

Это позволит сэкономить на разыменовании объекта каждый раз, когда вы хотите получить байт. Это может быть дорого в Visual Basic, особенно если в этом свойстве есть метод Getter.

Кроме того, используйте «определенный цикл» вместо «для каждого». Вы уже знаете длину массивов, поэтому просто закодируйте цикл, используя это значение. Это позволит избежать затрат на обработку массива как коллекции. Цикл будет выглядеть примерно так:

For i = 1 to max Step 1
   If (array1(i) <> array2(i)) 
       Exit For
   EndIf 
Next