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

Question

Я пытаюсь сравнить два длинных bytearrays в 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 - это будет проще. О, и проверьте, правильно ли указаны длины:

EDIT: Вот код (непроверенный, но достаточно простой), который я бы использовал.Это в 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; 
} 

EDIT: А вот 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

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

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

saveTime = binReader.ReadInt32() 

Или для массивов Интса:

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

Answer 3

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

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

array2 = item.Bytes 

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

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

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

Answer 4

Не строго связанные с алгоритмом сравнения:

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

Answer 5

Самый быстрый способ сравнить два байтовых массива равного размера - использовать 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 6

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