Quel est le moyen le plus rapide de comparer des tableaux à deux octets?
Question
J'essaie de comparer deux longs bytearrays dans VB.NET et j'ai rencontré un problème. La comparaison de deux fichiers de 50 mégaoctets prend presque deux minutes, je fais donc clairement quelque chose de mal. Je suis sur une machine x64 avec des tonnes de mémoire, donc il n'y a pas de problèmes là-bas. Voici le code que j'utilise en ce moment et que j'aimerais changer.
_Bytes
et item.Bytes
sont les deux tableaux différents à comparer et ont déjà la même longueur.
For Each B In item.Bytes
If B <> _Bytes(I) Then
Mismatch = True
Exit For
End If
I += 1
Next
Je dois pouvoir comparer aussi rapidement que possible des fichiers pouvant représenter des centaines de mégaoctets et même éventuellement un gigaoctet ou deux. Des suggestions ou des algorithmes qui pourraient faire cela plus rapidement?
Item.bytes
est un objet extrait de la base de données / du système de fichiers renvoyé pour comparaison, car sa longueur en octets correspond à l'élément que l'utilisateur souhaite ajouter. En comparant les deux tableaux, je peux ensuite déterminer si l'utilisateur a ajouté quelque chose de nouveau à la base de données. Sinon, je peux simplement les mapper vers l'autre fichier et ne pas gaspiller de l'espace sur le disque dur.
[Mise à jour]
J'ai converti les tableaux en variables locales de Byte (), puis j'ai fait la même comparaison, le même code et il a fonctionné comme une seconde (je dois le comparer et le comparer à d'autres), mais si vous faites la même chose chose avec des variables locales et utiliser un tableau générique, il devient extrêmement lent. Je ne sais pas trop pourquoi, mais cela me pose beaucoup plus de questions sur l'utilisation des tableaux.
La solution
Que fait l'appel _Bytes (I)
? Ce n'est pas le chargement du fichier à chaque fois, n'est-ce pas? Même avec la mise en mémoire tampon, ce serait une mauvaise nouvelle!
Il y aura de nombreuses façons de micro-optimiser en examinant longuement, en utilisant éventuellement un code peu sûr, etc. - mais je me concentrerais simplement sur une raisonnable performance en premier. Clairement, il se passe quelque chose de très étrange.
Je vous suggère d'extraire le code de comparaison dans une fonction distincte qui prend des tableaux de deux octets. De cette façon, vous saurez que vous ne ferez rien d’étrange. J'utiliserais également une simple boucle For
plutôt que For Each
dans ce cas, ce sera plus simple. Oh, et vérifie si les longueurs sont correctes en premier:)
EDIT: Voici le code (non testé, mais assez simple) que je voudrais utiliser. C'est en C # pour la minute - je vais le convertir en une seconde:
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: Et voici le 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
Autres conseils
Le moyen le plus rapide de comparer des tableaux de deux octets de taille égale consiste à utiliser interop. Exécutez le code suivant sur une application console:
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;
}
}
}
Si vous n'avez pas besoin de connaître l'octet, utilisez un inte de 64 bits qui vous en donne 8 à la fois. En fait, vous pouvez trouver le mauvais octet après l'avoir isolé en un ensemble de 8.
Utilisez BinaryReader :
saveTime = binReader.ReadInt32()
Ou pour les tableaux d'ints:
Dim count As Integer = binReader.Read(testArray, 0, 3)
Meilleure approche ... Si vous voulez simplement savoir si les deux sont différents, gagnez du temps en évitant de parcourir l'intégralité du tableau d'octets, de générer un hachage de chaque tableau d'octets sous forme de chaînes et de comparer les chaînes. MD5 devrait fonctionner correctement et est assez efficace.
Je vois deux choses qui pourraient aider:
Premièrement, plutôt que d’accéder toujours au second tableau en tant qu’élément.Bytes, utilisez une variable locale pour pointer directement sur le tableau. C’est-à-dire que, avant de commencer la boucle, faites quelque chose comme ceci:
array2 = item.Bytes
Cela économisera la surcharge de la suppression des références de l'objet chaque fois que vous souhaitez un octet. Cela peut coûter cher en Visual Basic, surtout s’il existe une méthode Getter sur cette propriété.
Utilisez également une "boucle définie". au lieu de "pour chaque". Vous connaissez déjà la longueur des tableaux, il vous suffit donc de coder la boucle en utilisant cette valeur. Cela évitera la surcharge de traiter le tableau comme une collection. La boucle ressemblerait à quelque chose comme ceci:
For i = 1 to max Step 1
If (array1(i) <> array2(i))
Exit For
EndIf
Next
Pas strictement lié à l'algorithme de comparaison:
Êtes-vous sûr que votre goulet d’étranglement n’est pas lié à la mémoire disponible ni au temps utilisé pour charger les tableaux d’octets? Le chargement de deux tableaux d’octets de 2 Go juste pour les comparer peut amener la plupart des machines à genoux. Si la conception du programme le permet, essayez d’utiliser des flux pour lire des fragments plus petits.