¿Cuál es la forma más rápida de comparar matrices de dos bytes?

Question

Estoy tratando de comparar dos bytearrays largos en VB.NET y me he encontrado con un problema. Comparar dos archivos de 50 megabytes lleva casi dos minutos, así que claramente estoy haciendo algo mal. Estoy en una máquina x64 con toneladas de memoria, así que no hay problemas allí. Aquí está el código que estoy usando en este momento y me gustaría cambiar.

_Bytes y item.Bytes son las dos matrices diferentes para comparar y ya tienen la misma longitud.

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

que necesitan ser capaces de comparar tan rápido como posibles archivos que son potencialmente cientos de megabytes e incluso, posiblemente, un gigabyte o dos. ¿Alguna sugerencia o algoritmo que podría hacer esto más rápido?

Item.bytes es un objeto tomado de la base de datos/sistema de archivos que se devuelve para comparar, porque su longitud de bytes coincide con el elemento que el usuario desea agregar. Al comparar las dos matrices, puedo determinar si el usuario ha agregado algo nuevo a la base de datos, y si no, puedo asignarlas al otro archivo y no perder espacio en el disco duro.

[Actualización]

que convierte las matrices de variables locales de Byte() y luego hizo la misma comparación, el mismo código y se corrieron en como un segundo (tengo que referencia todavía y compararlo con los demás), pero si haces lo mismo con las variables locales y usas una matriz genérica, se volverá masivamente más lenta. No estoy seguro de por qué, pero plantea muchas más preguntas sobre el uso de matrices.

Answer 1

Lo ¿Está haciendo la llamada _Bytes(I)? No está cargando el archivo cada vez, ¿o sí? Incluso con buffering, ¡eso sería una mala noticia!

Habrá un montón de maneras de optimizar micro- esto en cuanto a ver anhela a la vez, lo que podría utilizar código no seguro, etc. - pero que acababa de concentrarse en conseguir razonable rendimiento de primera. Claramente, está sucediendo algo muy extraño.

Sugiero que extraiga el código de comparación en una función separada que toma dos arrays de bytes. De esa forma sabes que no estarás haciendo nada extraño. También utilizaría un simple loop For en lugar de For Each, en este caso, será más simple. Ah, y compruebe si las longitudes son correctas primero :)

EDITAR: Aquí está el código (no probado, pero lo suficientemente simple) que usaría.Es en C# para el minuto - Voy a convertirlo en un segundo:

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: Y aquí está la 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

Si no necesita conocer el byte, use las entradas de 64 bits que le dan 8 a la vez. En realidad, se puede averiguar el byte mal, una vez que hemos aislado a un conjunto de 8.

Uso BinaryReader:

saveTime = binReader.ReadInt32() 

O para las matrices de enteros:

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

Answer 3

veo dos cosas que pueden ayudar:

Primeros , en lugar de acceder siempre a la segunda matriz como item.Bytes, usa una variable local para apuntar directamente a la matriz. Es decir, antes de iniciar el bucle, hacer algo como esto:

array2 = item.Bytes 

que salvará a la sobrecarga de eliminación de referencias del objeto cada vez que desee un byte. Eso podría ser costoso en Visual Basic, especialmente si hay un método Getter en esa propiedad.

Además, utilice un "bucle definido" en lugar de "para cada uno". Ya sabes la longitud de las matrices, así que simplemente codifica el ciclo usando ese valor. Esto evitará la sobrecarga de tratar la matriz como una colección. El bucle sería algo como esto:

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

Answer 4

no estrictamente relacionada con el algoritmo de comparación:

¿Seguro de su cuello de botella no está relacionado con la memoria disponible y el tiempo utilizado para cargar las matrices de bytes? Cargar dos matrices de bytes de 0   GB solo para compararlas podría poner a la mayoría de las máquinas de rodillas. Si el diseño del programa lo permite, intente utilizar secuencias para leer trozos más pequeños en su lugar.

Answer 5

La forma más rápida de comparar matrices de dos bytes de igual tamaño es utilizar interoperabilidad. Ejecute el código siguiente en una aplicación de consola:

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

mejor enfoque ... Si usted está tratando de ver si los dos son diferentes entonces ahorrar algo de tiempo al no tener que pasar por toda la matriz de bytes y generar una hash de cada matriz de bytes como cadenas y comparar las cadenas. MD5 debería funcionar bien y es bastante eficiente.