Сравнение двухбайтовых массивов в .NET - PullRequest
Новая
       175

Сравнение двухбайтовых массивов в .NET

487 голосов
/ 04 сентября 2008

Как я могу сделать это быстро?

Конечно, я могу сделать это: 

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;
}

Но я ищу либо функцию BCL , либо какой-нибудь высоко оптимизированный проверенный способ сделать это. 

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

работает хорошо, но не похоже, что это будет работать для x64.

Обратите внимание на мой сверхбыстрый ответ здесь .

Ответы [ 27 ]

564 голосов
/ 04 сентября 2008

Вы можете использовать Enumerable.SequenceEqual метод. 

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

Если по какой-то причине вы не можете использовать .NET 3.5, ваш метод в порядке.
Среда компилятора \ среды выполнения оптимизирует ваш цикл, поэтому вам не нужно беспокоиться о производительности.

229 голосов
/ 18 сентября 2009

P / Invoke полномочия активируются! 

[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;
}
154 голосов
/ 15 ноября 2011

Для этого в .NET 4 есть новое встроенное решение - IStructuralEquatable 

static bool ByteArrayCompare(byte[] a1, byte[] a2) 
{
    return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
70 голосов
/ 10 января 2012

Пользователь gil предложил небезопасный код, который породил это решение: 

// 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;
  }
}

, который выполняет 64-битное сравнение для максимально возможного массива. Этот вид рассчитывает на то, что массивы начинаются с выравнивания qword. Это будет работать, если не выровнять qword, но не так быстро, как если бы это было.

Он работает примерно на семь таймеров быстрее, чем простой цикл for. Использование библиотеки J # выполняется аналогично исходному циклу for. Использование .SequenceEqual работает в семь раз медленнее; Я думаю только потому, что он использует IEnumerator.MoveNext. Я полагаю, что решения на основе LINQ, по крайней мере, так медленны или хуже.

25 голосов
/ 03 февраля 2018

Span<T> предлагает чрезвычайно конкурентоспособную альтернативу без необходимости вводить запутанный и / или непереносимый пух в базу кода вашего собственного приложения: 

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

(Суть) реализации .NET Core 2.2.3 можно найти здесь .

Я пересмотрел @ Суть EliArbel, чтобы добавить этот метод как SpansEqual, отбросить большинство менее интересных исполнителей в тестах других, запустить его с различными размерами массива, графами вывода и пометкой SpansEqual в качестве базового уровня, чтобы он сообщал, как различные методы сравниваются с SpansEqual.

Приведенные ниже цифры взяты из результатов, слегка отредактированных для удаления столбца «Ошибка». 

|        Method |  ByteCount |               Mean |            StdDev | Ratio |
|-------------- |----------- |-------------------:|------------------:|------:|
|    SpansEqual |         15 |           3.813 ns |         0.0043 ns |  1.00 |
|  LongPointers |         15 |           4.768 ns |         0.0081 ns |  1.25 |
|      Unrolled |         15 |          17.763 ns |         0.0319 ns |  4.66 |
| PInvokeMemcmp |         15 |          12.280 ns |         0.0221 ns |  3.22 |
|               |            |                    |                   |       |
|    SpansEqual |       1026 |          29.181 ns |         0.0461 ns |  1.00 |
|  LongPointers |       1026 |          63.050 ns |         0.0785 ns |  2.16 |
|      Unrolled |       1026 |          39.070 ns |         0.0412 ns |  1.34 |
| PInvokeMemcmp |       1026 |          44.531 ns |         0.0581 ns |  1.53 |
|               |            |                    |                   |       |
|    SpansEqual |    1048585 |      43,838.865 ns |        56.7144 ns |  1.00 |
|  LongPointers |    1048585 |      59,629.381 ns |       194.0304 ns |  1.36 |
|      Unrolled |    1048585 |      54,765.863 ns |        34.2403 ns |  1.25 |
| PInvokeMemcmp |    1048585 |      55,250.573 ns |        49.3965 ns |  1.26 |
|               |            |                    |                   |       |
|    SpansEqual | 2147483591 | 247,237,201.379 ns | 2,734,143.0863 ns |  1.00 |
|  LongPointers | 2147483591 | 241,535,134.852 ns | 2,720,870.8915 ns |  0.98 |
|      Unrolled | 2147483591 | 240,170,750.054 ns | 2,729,935.0576 ns |  0.97 |
| PInvokeMemcmp | 2147483591 | 238,953,916.032 ns | 2,692,490.7016 ns |  0.97 |

Я был удивлен, увидев, SpansEqual не вышел на первое место для методов max-array-size, но разница настолько незначительна, что я не думаю, что это когда-либо будет иметь значение.

Информация о моей системе: 

BenchmarkDotNet=v0.11.5, OS=Windows 10.0.17134.706 (1803/April2018Update/Redstone4)
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
Frequency=3515626 Hz, Resolution=284.4444 ns, Timer=TSC
.NET Core SDK=2.2.202
  [Host]     : .NET Core 2.2.3 (CoreCLR 4.6.27414.05, CoreFX 4.6.27414.05), 64bit RyuJIT
  DefaultJob : .NET Core 2.2.3 (CoreCLR 4.6.27414.05, CoreFX 4.6.27414.05), 64bit RyuJIT
25 голосов
/ 04 сентября 2008

Если вы не против этого, вы можете импортировать сборку J # "vjslib.dll" и использовать ее метод Arrays.equals (byte [], byte []) ...

Не вините меня, если кто-то смеется над вами, хотя ...

РЕДАКТИРОВАТЬ: Для чего мало, я использовал Reflector, чтобы разобрать код для этого, и вот как это выглядит: 

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;
}
24 голосов
/ 01 мая 2009

.NET 3.5 и новее имеют новый открытый тип, System.Data.Linq.Binary, который инкапсулирует byte[]. Он реализует IEquatable<Binary>, который (по сути) сравнивает два байтовых массива. Обратите внимание, что System.Data.Linq.Binary также имеет оператор неявного преобразования из byte[].

Документация MSDN: System.Data.Linq.Binary

Декомпиляция рефлектора метода 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;
}

Интересным моментом является то, что они переходят к байтовому циклу сравнения, только если хэши двух двоичных объектов совпадают. Это, однако, происходит за счет вычисления хэша в конструкторе Binary объектов (путем обхода массива с помощью цикла for :-)).

Вышеприведенная реализация означает, что в худшем случае вам, возможно, придется обходить массивы три раза: сначала для вычисления хеша array1, затем для вычисления хеша array2 и, наконец, (поскольку это худший сценарий, длины и хеши равны ) сравнить байты в массиве 1 с байтами в массиве 2.

В целом, несмотря на то, что System.Data.Linq.Binary встроен в BCL, я не думаю, что это самый быстрый способ сравнения двухбайтовых массивов: - |.

16 голосов
/ 23 октября 2015

Я отправил аналогичный вопрос о проверке, заполнен ли ноль байта []. (Код SIMD был взломан, поэтому я удалил его из этого ответа.) Вот самый быстрый код из моих сравнений: 

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;
    }
}

Измеряется на двух байтах 256 МБ: 

UnsafeCompare                           : 86,8784 ms
EqualBytesSimd                          : 71,5125 ms
EqualBytesSimdUnrolled                  : 73,1917 ms
EqualBytesLongUnrolled                  : 39,8623 ms
10 голосов
/ 06 января 2011 
 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");
 }
8 голосов
/ 03 апреля 2017

Давайте добавим еще один!

Недавно Microsoft выпустила специальный пакет NuGet, System.Runtime.CompilerServices.Unsafe . Он особенный, потому что он написан на IL и обеспечивает низкоуровневую функциональность, прямо недоступную в C #.

Один из его методов, Unsafe.As<T>(object), позволяет приводить любой ссылочный тип к другому ссылочному типу, пропуская любые проверки безопасности. Обычно это очень плохая идея, но если оба типа имеют одинаковую структуру, она может работать. Таким образом, мы можем использовать это, чтобы привести byte[] к long[]: 

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

    var longSize = (int)Math.Floor(a1.Length / 8.0);
    var long1 = Unsafe.As<long[]>(a1);
    var long2 = Unsafe.As<long[]>(a2);

    for (var i = 0; i < longSize; i++)
    {
        if (long1[i] != long2[i]) return false;
    }

    for (var i = longSize * 8; i < a1.Length; i++)
    {
        if (a1[i] != a2[i]) return false;
    }

    return true;
}

Обратите внимание, что long1.Length будет по-прежнему возвращать длину исходного массива, поскольку он хранится в поле в структуре памяти массива.

Этот метод не такой быстрый, как другие методы, продемонстрированные здесь, но он намного быстрее, чем простой метод, не использует небезопасный код, P / Invoke или закрепление, а реализация довольно проста (IMO). Вот некоторые результаты BenchmarkDotNet с моей машины: 

BenchmarkDotNet=v0.10.3.0, OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4870HQ CPU 2.50GHz, ProcessorCount=8
Frequency=2435775 Hz, Resolution=410.5470 ns, Timer=TSC
  [Host]     : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
  DefaultJob : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0

                 Method |          Mean |    StdDev |
----------------------- |-------------- |---------- |
          UnsafeLibrary |   125.8229 ns | 0.3588 ns |
          UnsafeCompare |    89.9036 ns | 0.8243 ns |
           JSharpEquals | 1,432.1717 ns | 1.3161 ns |
 EqualBytesLongUnrolled |    43.7863 ns | 0.8923 ns |
              NewMemCmp |    65.4108 ns | 0.2202 ns |
            ArraysEqual |   910.8372 ns | 2.6082 ns |
          PInvokeMemcmp |    52.7201 ns | 0.1105 ns |

Я также создал гистолог со всеми тестами .

Страница:
...