Comment comparer deux byte[]?
Bonjour à tous,
Dans le cadre de mon projet actuel, je suis amené à comparer deux byte[]. J'ai régulièrement vu cette question apparaitre dans les forums et je souhaitent faire partager mon expérience à la communauté.
En ce qui me concerne, je dois uniquement savoir si les deux objets sont différents du point de vue du contenu. Cette différence est soit:
- une taille différente
- au moins un byte différent à une position donnée.
L'algorithme est plutôt simple. Voici une première méthode qui remplit les conditions:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public static bool AreEqual(byte[] left, byte[] right)
{
if ((left == null) || (right == null))
{
return false;
}
if (left.Length != right.Length)
{
return false;
}
for (int i = 0; i < left.Length; i++)
{
if (left[i] != right[i])
{
return false;
}
}
return true;
} |
La première question qui vient à l'esprit en lisant ce code est la performance. Dans le cas qui m'occupe, je n'ai aucune idée préalable sur la taille des arrays. A priori, l'algorithme est bon, je sort de la bouche dès qu'une différence est rencontrée. Mais s'il faut comparer deux arrays identiques de 200 megabytes?
J'ai alors écrit la méthode suivante, en partant de l'idée que comparer un hash serait toujours plus rapide.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static bool AreEqualWithHash(byte[] left, byte[] right)
{
if ((left == null) || (right == null))
{
return false;
}
if (left.Length != right.Length)
{
return false;
}
// md5 is a static variable defined in the Program class only once to
// avoid instanciation on each call
// static MD5CryptoServiceProvider md5 = new MD5CryptoServiceProvider();
byte[] hashLeft = md5.ComputeHash(left);
byte[] hashright = md5.ComputeHash(right);
return AreEqual(hashLeft, hashright);
} |
Sur le papier, on devrait y gagner, non? Sauf dans le cas le plus défavorable où la différence se situe en début d'array. Mais en réalité, qu'en est-il? Je décide donc d'écrire un programme de test, je génère une array et je la compare à elle-même, pour la parcourir intégralement.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| static void Main(string[] args)
{
const int MEGA = 1024 * 1024;
byte[] array = null;
Stopwatch stopwatch = new Stopwatch();
for (int i = MEGA; i < Int32.MaxValue; i += MEGA)
{
// First method
array = FillByteArray(i);
stopwatch.Reset();
stopwatch.Start();
AreEqual(array, array);
stopwatch.Stop();
TimeSpan ts1 = stopwatch.Elapsed;
// Second method
array = FillByteArray(i);
stopwatch.Reset();
stopwatch.Start();
AreEqualWithHash(array, array);
stopwatch.Stop();
TimeSpan ts2 = stopwatch.Elapsed;
Console.WriteLine("{0} megabytes: {1} - {2}", i / MEGA, ts1.TotalSeconds, ts2.TotalSeconds);
}
Console.WriteLine("END");
Console.Read();
} |
Je constate avec stupéfaction que la seconde méthode ne gagne jamais, le coût pour calculer le hash est systématiquement plus élevé. J'avoue, je n'ai jamais laissé l'application tourner jusqu'à la fin. Après réflexion, c'est assez logique, pour calculer le hash, il faut parcourir l'array en entier et faire des opérations arithmétiques.
Voila, j'espère que ce mini-article vous aura plus et vous aura convaincus.
Neptune
