[c#] .NET에서 두 바이트 배열 비교

어떻게 빨리 할 수 ​​있습니까?

물론 내가 할 수있는 일 :

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에서는 작동하지 않는 것 같습니다.

여기 내 초고속 답변을 참고 하십시오 .



답변

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를 사용할 수 없으면 방법이 정상입니다.
컴파일러 / 런타임 환경은 루프를 최적화하므로 성능에 대해 걱정할 필요가 없습니다.


답변

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


답변

.NET 4에는이를위한 새로운 내장 솔루션이 있습니다 -IStructuralEquatable

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


답변

사용자 길은 이 솔루션을 생성 한 안전하지 않은 코드를 제안했습니다.

// 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루프 보다 약 7 개의 타이머를 더 빠르게 수행합니다 . J # 라이브러리 사용은 원래 for루프 와 동일하게 수행 됩니다. .SequenceEqual을 사용하면 약 7 배 느리게 실행됩니다. IEnumerator.MoveNext를 사용하고 있기 때문에 생각합니다. 나는 LINQ 기반 솔루션이 적어도 느리거나 더 나쁘다고 생각합니다.


답변

Span<T> 혼란스럽고 이식 불가능한 보풀을 자신의 응용 프로그램 코드 기반에 넣지 않고도 매우 경쟁력있는 대안을 제공합니다.

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

.NET Core 3.1.0의 구현은 여기 에서 찾을 수 있습니다 .

나는 한 개정 이 같은 방법을 추가 EliArbel의 요점 @ SpansEqual, 다른 배열 크기, 출력 그래프를 실행, 다른 사람의 벤치 마크에서 덜 흥미로운 공연의 대부분을 삭제하고 마크 SpansEqual는 다른 방법을 비교하는 방법을보고 그렇게하는 기준으로 SpansEqual.

아래 숫자는 결과에서 가져온 것으로 “오류”열을 제거하기 위해 약간 편집되었습니다.

|        Method |  ByteCount |               Mean |            StdDev | Ratio |
|-------------- |----------- |-------------------:|------------------:|------:|
|    SpansEqual |         15 |           3.562 ns |         0.0035 ns |  1.00 |
|  LongPointers |         15 |           4.611 ns |         0.0028 ns |  1.29 |
|      Unrolled |         15 |          18.035 ns |         0.0195 ns |  5.06 |
| PInvokeMemcmp |         15 |          11.210 ns |         0.0353 ns |  3.15 |
|               |            |                    |                   |       |
|    SpansEqual |       1026 |          20.048 ns |         0.0286 ns |  1.00 |
|  LongPointers |       1026 |          63.347 ns |         0.1062 ns |  3.16 |
|      Unrolled |       1026 |          39.175 ns |         0.0304 ns |  1.95 |
| PInvokeMemcmp |       1026 |          40.830 ns |         0.0350 ns |  2.04 |
|               |            |                    |                   |       |
|    SpansEqual |    1048585 |      44,070.526 ns |        35.3348 ns |  1.00 |
|  LongPointers |    1048585 |      59,973.407 ns |        80.4145 ns |  1.36 |
|      Unrolled |    1048585 |      55,032.945 ns |        24.4745 ns |  1.25 |
| PInvokeMemcmp |    1048585 |      55,593.719 ns |        22.4301 ns |  1.26 |
|               |            |                    |                   |       |
|    SpansEqual | 2147483591 | 253,648,180.000 ns | 1,112,524.3074 ns |  1.00 |
|  LongPointers | 2147483591 | 249,412,064.286 ns | 1,079,409.5670 ns |  0.98 |
|      Unrolled | 2147483591 | 246,329,091.667 ns |   852,021.7992 ns |  0.97 |
| PInvokeMemcmp | 2147483591 | 247,795,940.000 ns | 3,390,676.3644 ns |  0.98 |

SpansEqualmax-array-size 방법을 사용하지 않는 것에 대해 놀랐지 만 그 차이는 너무 작아서 중요하지 않다고 생각합니다.

내 시스템 정보 :

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18362
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=3.1.100
  [Host]     : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT
  DefaultJob : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT


답변

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


답변

.NET 3.5 이상에는 System.Data.Linq.Binary을 캡슐화 하는 새로운 공개 유형이 byte[]있습니다. 실제로 IEquatable<Binary>2 바이트 배열을 비교합니다. 의 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객체 생성자에서 해시를 계산하는 비용이 듭니다 ( forloop :-)으로 배열을 순회하여 ).

위의 구현은 최악의 경우 배열을 세 번 통과해야한다는 것을 의미합니다. 먼저 배열 1의 해시를 계산 한 다음 배열 2의 해시를 계산하고 마지막으로 (이는 최악의 시나리오이기 때문에 길이와 해시가 동일하므로) 배열 1의 바이트와 배열 2의 바이트

전반적 System.Data.Linq.Binary으로 BCL에 내장되어 있지만 두 바이트 배열을 비교하는 가장 빠른 방법이라고는 생각하지 않습니다.