Question Comparaison de deux tableaux d'octets dans .NET


Comment puis-je le faire rapidement?

Bien sûr, je peux le faire:

static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
    if (a1.Length != a2.Length)
        return false;

    for (int i=0; i<a1.Length; i++)
        if (a1[i]!=a2[i])
            return false;

    return true;
}

Mais je cherche soit un BCL fonction ou un moyen éprouvé hautement optimisé pour faire cela.

java.util.Arrays.equals((sbyte[])(Array)a1, (sbyte[])(Array)a2);

fonctionne bien, mais il ne semble pas que cela fonctionnerait pour x64.

Notez ma réponse super rapide ici.


422
2017-09-04 07:33


origine


Réponses:


Vous pouvez utiliser Enumerable.SequenceEqual méthode.

using System;
using System.Linq;
...
var a1 = new int[] { 1, 2, 3};
var a2 = new int[] { 1, 2, 3};
var a3 = new int[] { 1, 2, 4};
var x = a1.SequenceEqual(a2); // true
var y = a1.SequenceEqual(a3); // false

Si vous ne pouvez pas utiliser .NET 3.5 pour une raison quelconque, votre méthode est OK.
L'environnement Compiler \ run-time optimisera votre boucle pour que vous n'ayez pas à vous soucier des performances.


511
2017-09-04 07:53



P / Invoke les pouvoirs s'activent!

[DllImport("msvcrt.dll", CallingConvention=CallingConvention.Cdecl)]
static extern int memcmp(byte[] b1, byte[] b2, long count);

static bool ByteArrayCompare(byte[] b1, byte[] b2)
{
    // Validate buffers are the same length.
    // This also ensures that the count does not exceed the length of either buffer.  
    return b1.Length == b2.Length && memcmp(b1, b2, b1.Length) == 0;
}

221
2017-09-18 15:49



Il y a une nouvelle solution intégrée pour cela dans .NET 4 - IStructuralEquatable

static bool ByteArrayCompare(byte[] a1, byte[] a2) 
{
    return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}

150
2017-11-15 17:38



Utilisateur gil code dangereux suggéré qui a engendré cette solution:

// Copyright (c) 2008-2013 Hafthor Stefansson
// Distributed under the MIT/X11 software license
// Ref: http://www.opensource.org/licenses/mit-license.php.
static unsafe bool UnsafeCompare(byte[] a1, byte[] a2) {
  if(a1==a2) return true;
  if(a1==null || a2==null || a1.Length!=a2.Length)
    return false;
  fixed (byte* p1=a1, p2=a2) {
    byte* x1=p1, x2=p2;
    int l = a1.Length;
    for (int i=0; i < l/8; i++, x1+=8, x2+=8)
      if (*((long*)x1) != *((long*)x2)) return false;
    if ((l & 4)!=0) { if (*((int*)x1)!=*((int*)x2)) return false; x1+=4; x2+=4; }
    if ((l & 2)!=0) { if (*((short*)x1)!=*((short*)x2)) return false; x1+=2; x2+=2; }
    if ((l & 1)!=0) if (*((byte*)x1) != *((byte*)x2)) return false;
    return true;
  }
}

qui effectue une comparaison basée sur 64 bits pour la plus grande partie du tableau possible. Ce type de compte repose sur le fait que les tableaux commencent à aligner qword. Ça marchera sinon qword aligné, mais pas aussi vite que si c'était le cas.

Il effectue environ sept minuteries plus rapidement que le simple for boucle. Utilisation de la bibliothèque J # effectuée de manière équivalente à l'original for boucle. L'utilisation de .SequenceEqual est environ sept fois plus lente; Je pense juste parce qu'il utilise IEnumerator.MoveNext. J'imagine que les solutions basées sur LINQ sont au moins aussi lentes ou pires.


67
2018-01-10 18:11



Si vous n'êtes pas opposé à le faire, vous pouvez importer l'assembly J # "vjslib.dll" et utiliser son Méthode Arrays.equals (byte [], byte [])...

Ne me blâmez pas si quelqu'un se moque de toi ...


EDIT: Pour quel peu ça vaut, j'ai utilisé Reflector pour démonter le code pour ça, et voici à quoi ça ressemble:

public static bool equals(sbyte[] a1, sbyte[] a2)
{
  if (a1 == a2)
  {
    return true;
  }
  if ((a1 != null) && (a2 != null))
  {
    if (a1.Length != a2.Length)
    {
      return false;
    }
    for (int i = 0; i < a1.Length; i++)
    {
      if (a1[i] != a2[i])
      {
        return false;
      }
    }
    return true;
  }
  return false;
}

25
2017-09-04 07:48



.NET 3.5 et plus récent ont un nouveau type public, System.Data.Linq.Binary qui encapsule byte[]. Il implémente IEquatable<Binary> cela (en effet) compare deux tableaux d'octets. Notez que System.Data.Linq.Binary a également un opérateur de conversion implicite de byte[].

Documentation MSDN:System.Data.Linq.Binary

Réflecteur de la méthode Equals:

private bool EqualsTo(Binary binary)
{
    if (this != binary)
    {
        if (binary == null)
        {
            return false;
        }
        if (this.bytes.Length != binary.bytes.Length)
        {
            return false;
        }
        if (this.hashCode != binary.hashCode)
        {
            return false;
        }
        int index = 0;
        int length = this.bytes.Length;
        while (index < length)
        {
            if (this.bytes[index] != binary.bytes[index])
            {
                return false;
            }
            index++;
        }
    }
    return true;
}

Ce qui est intéressant, c'est qu'ils ne procèdent à une boucle de comparaison octet par octet que si les hachages des deux objets binaires sont identiques. Ceci, cependant, se fait au prix du calcul du hachage dans le constructeur de Binary objets (en traversant le tableau avec for boucle :-) ).

L'implémentation ci-dessus signifie que dans le pire des cas, vous devrez traverser les tableaux trois fois: d'abord pour calculer le hachage de array1, puis pour calculer le hash de array2 et enfin (car c'est le pire scénario, longueurs et hachages égaux) pour comparer octets dans array1 avec octets dans le tableau 2.

Dans l'ensemble, même si System.Data.Linq.Binary est intégré dans BCL, je ne pense pas que ce soit le moyen le plus rapide de comparer deux tableaux d'octets: - |.


24
2018-05-01 13:14



Je posté une question similaire sur la vérification si l'octet [] est plein de zéros. (Le code SIMD a été battu alors je l'ai retiré de cette réponse.) Voici le code le plus rapide de mes comparaisons:

static unsafe bool EqualBytesLongUnrolled (byte[] data1, byte[] data2)
{
    if (data1 == data2)
        return true;
    if (data1.Length != data2.Length)
        return false;

    fixed (byte* bytes1 = data1, bytes2 = data2) {
        int len = data1.Length;
        int rem = len % (sizeof(long) * 16);
        long* b1 = (long*)bytes1;
        long* b2 = (long*)bytes2;
        long* e1 = (long*)(bytes1 + len - rem);

        while (b1 < e1) {
            if (*(b1) != *(b2) || *(b1 + 1) != *(b2 + 1) || 
                *(b1 + 2) != *(b2 + 2) || *(b1 + 3) != *(b2 + 3) ||
                *(b1 + 4) != *(b2 + 4) || *(b1 + 5) != *(b2 + 5) || 
                *(b1 + 6) != *(b2 + 6) || *(b1 + 7) != *(b2 + 7) ||
                *(b1 + 8) != *(b2 + 8) || *(b1 + 9) != *(b2 + 9) || 
                *(b1 + 10) != *(b2 + 10) || *(b1 + 11) != *(b2 + 11) ||
                *(b1 + 12) != *(b2 + 12) || *(b1 + 13) != *(b2 + 13) || 
                *(b1 + 14) != *(b2 + 14) || *(b1 + 15) != *(b2 + 15))
                return false;
            b1 += 16;
            b2 += 16;
        }

        for (int i = 0; i < rem; i++)
            if (data1 [len - 1 - i] != data2 [len - 1 - i])
                return false;

        return true;
    }
}

Mesuré sur deux tableaux de 256 Mo d'octets:

UnsafeCompare                           : 86,8784 ms
EqualBytesSimd                          : 71,5125 ms
EqualBytesSimdUnrolled                  : 73,1917 ms
EqualBytesLongUnrolled                  : 39,8623 ms

14
2017-10-23 17:07



Span<T> offre une alternative extrêmement compétitive sans avoir à jeter des pellicules déroutantes et / ou non portables dans la base de code de votre propre application:

// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
    return a1.SequenceEqual(a2);
}

Les (entrailles de la) implémentation peuvent être trouvées ici.

J'ai modifié @ EliArbel veut ajouter cette méthode comme SpansEqual, déposez la plupart des artistes moins intéressants dans les benchmarks des autres, exécutez-le avec différentes tailles de tableaux, graphiques de sortie et marque SpansEqual comme la ligne de base afin qu'il rapporte comment les différentes méthodes se comparent à SpansEqual.

Les chiffres ci-dessous proviennent des résultats, légèrement modifiés pour supprimer la colonne "Erreur".

|        Method |  ByteCount |               Mean |         StdDev | Scaled |
|-------------- |----------- |-------------------:|---------------:|-------:|
|    SpansEqual |         15 |           3.614 ns |      0.0069 ns |   1.00 |
|  LongPointers |         15 |           4.762 ns |      0.0009 ns |   1.32 |
|      Unrolled |         15 |          16.933 ns |      0.0024 ns |   4.68 |
| PInvokeMemcmp |         15 |          11.448 ns |      0.0183 ns |   3.17 |
|               |            |                    |                |        |
|    SpansEqual |       1026 |          25.957 ns |      0.0081 ns |   1.00 |
|  LongPointers |       1026 |          60.336 ns |      0.0211 ns |   2.32 |
|      Unrolled |       1026 |          37.216 ns |      0.0042 ns |   1.43 |
| PInvokeMemcmp |       1026 |          43.531 ns |      0.0229 ns |   1.68 |
|               |            |                    |                |        |
|    SpansEqual |    1048585 |      42,708.279 ns |      6.7683 ns |   1.00 |
|  LongPointers |    1048585 |      57,952.010 ns |      6.0004 ns |   1.36 |
|      Unrolled |    1048585 |      52,768.967 ns |      5.1800 ns |   1.24 |
| PInvokeMemcmp |    1048585 |      53,270.846 ns |     11.9056 ns |   1.25 |
|               |            |                    |                |        |
|    SpansEqual | 2147483591 | 243,281,911.498 ns | 65,006.3172 ns |   1.00 |
|  LongPointers | 2147483591 | 237,786,969.675 ns | 96,332.7202 ns |   0.98 |
|      Unrolled | 2147483591 | 237,151,053.500 ns | 74,137.6513 ns |   0.97 |
| PInvokeMemcmp | 2147483591 | 235,829,644.641 ns | 50,390.2144 ns |   0.97 |

J'ai été surpris de voir SpansEqual Je ne suis pas d'accord avec les méthodes de taille max-array, mais la différence est si minime que je ne pense pas que ce soit important.

Mon info système:

BenchmarkDotNet=v0.10.14, OS=Windows 10.0.17134
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
Frequency=3515619 Hz, Resolution=284.4449 ns, Timer=TSC
.NET Core SDK=2.1.300
  [Host]     : .NET Core 2.1.0 (CoreCLR 4.6.26515.07, CoreFX 4.6.26515.06), 64bit RyuJIT
  DefaultJob : .NET Core 2.1.0 (CoreCLR 4.6.26515.07, CoreFX 4.6.26515.06), 64bit RyuJIT

12
2018-02-03 15:45



 using System.Linq; //SequenceEqual

 byte[] ByteArray1 = null;
 byte[] ByteArray2 = null;

 ByteArray1 = MyFunct1();
 ByteArray2 = MyFunct2();

 if (ByteArray1.SequenceEqual<byte>(ByteArray2) == true)
 {
    MessageBox.Show("Match");
 }
 else
 {
   MessageBox.Show("Don't match");
 }

10
2018-01-06 16:15