.NET의 2바이트 배열 비교
https://stackoverflow.com/questions/43289
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
어떻게 하면 빨리 할 수 있나요?
물론이죠. 저는 이것을 할 수 있습니다:
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에서는 작동하지 않는 것 같습니다.
내 초고속 답변을 참고하세요 여기.
해결책 4
사용자 길 이 솔루션을 생성한 안전하지 않은 코드를 제안했습니다.
// 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가 정렬되지 않으면 작동하지만 속도는 빠르지 않습니다.
단순 타이머보다 약 7개의 타이머를 더 빠르게 수행합니다. for 고리.원본과 동일하게 수행되는 J# 라이브러리 사용 for 고리..SequenceEqual을 사용하면 약 7배 더 느리게 실행됩니다.IEnumerator.MoveNext를 사용하고 있기 때문이라고 생각합니다.나는 LINQ 기반 솔루션이 적어도 그만큼 느리거나 더 나쁘다고 생각합니다.
다른 팁
당신이 사용할 수있는 열거 가능.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/호출 능력이 활성화됩니다!
[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);
}
이를 반대하지 않는다면 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;
}
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
.NET 3.5 이상에는 새로운 공개 유형이 있습니다. System.Data.Linq.Binary 캡슐화하는 것 byte[].구현합니다 IEquatable<Binary> 이는 (사실상) 두 바이트 배열을 비교합니다.참고하세요 System.Data.Linq.Binary 또한 암시적 변환 연산자가 있습니다. byte[].
MSDN 문서:시스템.데이터.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 객체의 해시가 동일한 경우에만 바이트별 비교 루프를 진행한다는 것입니다.그러나 이는 생성자에서 해시를 계산하는 대가를 치르게 됩니다. Binary 객체(배열을 탐색하여 for 루프 :-) ).
위의 구현은 최악의 경우 배열을 세 번 순회해야 할 수도 있음을 의미합니다.먼저 array1의 해시를 계산한 다음 array2의 해시를 계산하고 마지막으로 (최악의 시나리오이므로 길이와 해시가 동일하므로) array1의 바이트를 배열 2의 바이트와 비교합니다.
전반적으로 그렇긴 하지만 System.Data.Linq.Binary BCL에 내장되어 있지만 2바이트 배열을 비교하는 가장 빠른 방법은 아니라고 생각합니다. :-|.
나는 게시했다 byte[]가 0으로 가득 차 있는지 확인하는 것과 비슷한 질문입니다.(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;
}
}
2개의 256MB 바이트 어레이에서 측정됨:
UnsafeCompare : 86,8784 ms
EqualBytesSimd : 71,5125 ms
EqualBytesSimdUnrolled : 73,1917 ms
EqualBytesLongUnrolled : 39,8623 ms
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");
}
하나 더 추가해보자!
최근 Microsoft는 특별한 NuGet 패키지를 출시했습니다. System.Runtime.CompilerServices.Unsafe.적혀있어서 특별해요 일리노이, 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).다음은 일부입니다. 벤치마크DotNet 내 컴퓨터의 결과:
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 |
나는 또한 모든 테스트의 요점.
조금 더 나은 방법을 개발했습니다. memcmp() (주각의 대답) 그리고 아주 약간 친다 EqualBytesLongUnrolled() (Arek Bulski의 답변) 내 PC에서.기본적으로 루프를 8 대신 4만큼 펼칩니다.
3월 30일 업데이트2019:
.NET Core 3.0부터 SIMD가 지원됩니다!
이 솔루션은 내 PC에서 상당한 차이로 가장 빠릅니다.
#if NETCOREAPP3_0
using System.Runtime.Intrinsics.X86;
#endif
…
public static unsafe bool Compare(byte[] arr0, byte[] arr1)
{
if (arr0 == arr1)
{
return true;
}
if (arr0 == null || arr1 == null)
{
return false;
}
if (arr0.Length != arr1.Length)
{
return false;
}
if (arr0.Length == 0)
{
return true;
}
fixed (byte* b0 = arr0, b1 = arr1)
{
#if NETCOREAPP3_0
if (Avx2.IsSupported)
{
return Compare256(b0, b1, arr0.Length);
}
else if (Sse2.IsSupported)
{
return Compare128(b0, b1, arr0.Length);
}
else
#endif
{
return Compare64(b0, b1, arr0.Length);
}
}
}
#if NETCOREAPP3_0
public static unsafe bool Compare256(byte* b0, byte* b1, int length)
{
byte* lastAddr = b0 + length;
byte* lastAddrMinus128 = lastAddr - 128;
const int mask = -1;
while (b0 < lastAddrMinus128) // unroll the loop so that we are comparing 128 bytes at a time.
{
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0), Avx.LoadVector256(b1))) != mask)
{
return false;
}
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 32), Avx.LoadVector256(b1 + 32))) != mask)
{
return false;
}
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 64), Avx.LoadVector256(b1 + 64))) != mask)
{
return false;
}
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 96), Avx.LoadVector256(b1 + 96))) != mask)
{
return false;
}
b0 += 128;
b1 += 128;
}
while (b0 < lastAddr)
{
if (*b0 != *b1) return false;
b0++;
b1++;
}
return true;
}
public static unsafe bool Compare128(byte* b0, byte* b1, int length)
{
byte* lastAddr = b0 + length;
byte* lastAddrMinus64 = lastAddr - 64;
const int mask = 0xFFFF;
while (b0 < lastAddrMinus64) // unroll the loop so that we are comparing 64 bytes at a time.
{
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0), Sse2.LoadVector128(b1))) != mask)
{
return false;
}
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 16), Sse2.LoadVector128(b1 + 16))) != mask)
{
return false;
}
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 32), Sse2.LoadVector128(b1 + 32))) != mask)
{
return false;
}
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 48), Sse2.LoadVector128(b1 + 48))) != mask)
{
return false;
}
b0 += 64;
b1 += 64;
}
while (b0 < lastAddr)
{
if (*b0 != *b1) return false;
b0++;
b1++;
}
return true;
}
#endif
public static unsafe bool Compare64(byte* b0, byte* b1, int length)
{
byte* lastAddr = b0 + length;
byte* lastAddrMinus32 = lastAddr - 32;
while (b0 < lastAddrMinus32) // unroll the loop so that we are comparing 32 bytes at a time.
{
if (*(ulong*)b0 != *(ulong*)b1) return false;
if (*(ulong*)(b0 + 8) != *(ulong*)(b1 + 8)) return false;
if (*(ulong*)(b0 + 16) != *(ulong*)(b1 + 16)) return false;
if (*(ulong*)(b0 + 24) != *(ulong*)(b1 + 24)) return false;
b0 += 32;
b1 += 32;
}
while (b0 < lastAddr)
{
if (*b0 != *b1) return false;
b0++;
b1++;
}
return true;
}
안전하지 않은 코드를 사용하고 for Int32 포인터를 비교하는 루프입니다.
어쩌면 배열이 null이 아닌지 확인하는 것도 고려해야 합니다.
.NET에서 string.Equals를 수행하는 방법을 살펴보면 "안전하지 않은" 포인터 구현이 있는 EqualsHelper라는 전용 메서드를 사용한다는 것을 알 수 있습니다. .NET 리플렉터 내부적으로 일이 어떻게 진행되는지 확인하는 친구입니다.
이는 블로그 게시물에서 구현한 바이트 배열 비교를 위한 템플릿으로 사용할 수 있습니다. C#의 빠른 바이트 배열 비교.또한 안전한 구현이 안전하지 않은 구현보다 빠른지 확인하기 위해 몇 가지 기본적인 벤치마크를 수행했습니다.
즉, 정말 뛰어난 성능이 필요하지 않은 한 간단한 fr 루프 비교를 진행하겠습니다.
완전히 만족스러운 솔루션(합리적인 성능, 안전하지 않은 코드/핀보크 없음)을 찾을 수 없어서 독창적인 것은 아니지만 작동하는 이 솔루션을 생각해냈습니다.
/// <summary>
///
/// </summary>
/// <param name="array1"></param>
/// <param name="array2"></param>
/// <param name="bytesToCompare"> 0 means compare entire arrays</param>
/// <returns></returns>
public static bool ArraysEqual(byte[] array1, byte[] array2, int bytesToCompare = 0)
{
if (array1.Length != array2.Length) return false;
var length = (bytesToCompare == 0) ? array1.Length : bytesToCompare;
var tailIdx = length - length % sizeof(Int64);
//check in 8 byte chunks
for (var i = 0; i < tailIdx; i += sizeof(Int64))
{
if (BitConverter.ToInt64(array1, i) != BitConverter.ToInt64(array2, i)) return false;
}
//check the remainder of the array, always shorter than 8 bytes
for (var i = tailIdx; i < length; i++)
{
if (array1[i] != array2[i]) return false;
}
return true;
}
이 페이지의 다른 솔루션과 비교한 성능:
단순 루프:19837틱, 1.00
*비트컨버터:4886틱, 4.06
안전하지 않음비교:1636틱, 12.12
EqualBytesLongUnrolled:637틱, 31.09
P/memcmp 호출:369틱, 53.67
linqpad에서 1000000바이트의 동일한 배열(최악의 경우), 각각 500회 반복으로 테스트되었습니다.
것 같다 EqualBytesLongUnrolled 위에서 제안한 것 중 최고입니다.
건너뛴 메서드(Enumerable.SequenceEqual,StructuralComparisons.StructuralEqualityComparer.Equals)는 인내심이 부족하지 않았습니다.265MB 어레이에서 다음을 측정했습니다.
Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-3770 CPU 3.40GHz, ProcessorCount=8
Frequency=3323582 ticks, Resolution=300.8802 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1590.0
Type=CompareMemoriesBenchmarks Mode=Throughput
Method | Median | StdDev | Scaled | Scaled-SD |
----------------------- |------------ |---------- |------- |---------- |
NewMemCopy | 30.0443 ms | 1.1880 ms | 1.00 | 0.00 |
EqualBytesLongUnrolled | 29.9917 ms | 0.7480 ms | 0.99 | 0.04 |
msvcrt_memcmp | 30.0930 ms | 0.2964 ms | 1.00 | 0.03 |
UnsafeCompare | 31.0520 ms | 0.7072 ms | 1.03 | 0.04 |
ByteArrayCompare | 212.9980 ms | 2.0776 ms | 7.06 | 0.25 |
OS=Windows
Processor=?, ProcessorCount=8
Frequency=3323582 ticks, Resolution=300.8802 ns, Timer=TSC
CLR=CORE, Arch=64-bit ? [RyuJIT]
GC=Concurrent Workstation
dotnet cli version: 1.0.0-preview2-003131
Type=CompareMemoriesBenchmarks Mode=Throughput
Method | Median | StdDev | Scaled | Scaled-SD |
----------------------- |------------ |---------- |------- |---------- |
NewMemCopy | 30.1789 ms | 0.0437 ms | 1.00 | 0.00 |
EqualBytesLongUnrolled | 30.1985 ms | 0.1782 ms | 1.00 | 0.01 |
msvcrt_memcmp | 30.1084 ms | 0.0660 ms | 1.00 | 0.00 |
UnsafeCompare | 31.1845 ms | 0.4051 ms | 1.03 | 0.01 |
ByteArrayCompare | 212.0213 ms | 0.1694 ms | 7.03 | 0.01 |
나는 여기서 많은 linq 솔루션을 보지 못했습니다.
성능에 미치는 영향은 확실하지 않지만 일반적으로 linq 경험에 따르면 필요한 경우 나중에 최적화합니다.
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
return !array1.Where((t, i) => t != array2[i]).Any();
}
이는 동일한 크기의 배열인 경우에만 작동한다는 점에 유의하세요.확장 프로그램은 다음과 같이 보일 수 있습니다
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
if (array1.Length != array2.Length) return false;
return !array1.Where((t, i) => t != array2[i]).Any();
}
디버거를 연결하지 않고 첨부된 프로그램 .net 4.7 릴리스 빌드를 사용하여 몇 가지 측정을 수행했습니다.나는 사람들이 잘못된 측정법을 사용하고 있다고 생각합니다. 여기서 속도에 관심이 있다면 2바이트 배열이 동일한지 알아내는 데 걸리는 시간이기 때문입니다.즉.처리량(바이트)입니다.
StructuralComparison : 4.6 MiB/s
for : 274.5 MiB/s
ToUInt32 : 263.6 MiB/s
ToUInt64 : 474.9 MiB/s
memcmp : 8500.8 MiB/s
보시다시피 이보다 더 좋은 방법은 없습니다. memcmp 그리고 그것은 훨씬 더 빠릅니다.간단한 for 루프는 두 번째로 좋은 옵션입니다.그리고 왜 Microsoft가 단순히 Buffer.Compare 방법.
[프로그램.cs]:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;
namespace memcmp
{
class Program
{
static byte[] TestVector(int size)
{
var data = new byte[size];
using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider())
{
rng.GetBytes(data);
}
return data;
}
static TimeSpan Measure(string testCase, TimeSpan offset, Action action, bool ignore = false)
{
var t = Stopwatch.StartNew();
var n = 0L;
while (t.Elapsed < TimeSpan.FromSeconds(10))
{
action();
n++;
}
var elapsed = t.Elapsed - offset;
if (!ignore)
{
Console.WriteLine($"{testCase,-16} : {n / elapsed.TotalSeconds,16:0.0} MiB/s");
}
return elapsed;
}
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
static extern int memcmp(byte[] b1, byte[] b2, long count);
static void Main(string[] args)
{
// how quickly can we establish if two sequences of bytes are equal?
// note that we are testing the speed of different comparsion methods
var a = TestVector(1024 * 1024); // 1 MiB
var b = (byte[])a.Clone();
// was meant to offset the overhead of everything but copying but my attempt was a horrible mistake... should have reacted sooner due to the initially ridiculous throughput values...
// Measure("offset", new TimeSpan(), () => { return; }, ignore: true);
var offset = TimeZone.Zero
Measure("StructuralComparison", offset, () =>
{
StructuralComparisons.StructuralEqualityComparer.Equals(a, b);
});
Measure("for", offset, () =>
{
for (int i = 0; i < a.Length; i++)
{
if (a[i] != b[i]) break;
}
});
Measure("ToUInt32", offset, () =>
{
for (int i = 0; i < a.Length; i += 4)
{
if (BitConverter.ToUInt32(a, i) != BitConverter.ToUInt32(b, i)) break;
}
});
Measure("ToUInt64", offset, () =>
{
for (int i = 0; i < a.Length; i += 8)
{
if (BitConverter.ToUInt64(a, i) != BitConverter.ToUInt64(b, i)) break;
}
});
Measure("memcmp", offset, () =>
{
memcmp(a, b, a.Length);
});
}
}
}
짧은 바이트 배열을 비교하기 위해 다음은 흥미로운 해킹입니다.
if(myByteArray1.Length != myByteArray2.Length) return false;
if(myByteArray1.Length == 8)
return BitConverter.ToInt64(myByteArray1, 0) == BitConverter.ToInt64(myByteArray2, 0);
else if(myByteArray.Length == 4)
return BitConverter.ToInt32(myByteArray2, 0) == BitConverter.ToInt32(myByteArray2, 0);
그렇다면 아마도 질문에 나열된 솔루션에 빠질 것입니다.
이 코드의 성능 분석을 수행하는 것은 흥미로울 것입니다.
많은 그래픽 카드에 내장된 블록 전송 가속 방법에 대해 생각했습니다.그러나 모든 데이터를 바이트 단위로 복사해야 하므로 관리되지 않는 하드웨어 종속 코드에서 논리의 전체 부분을 구현하지 않으려는 경우에는 별로 도움이 되지 않습니다.
위에 표시된 접근 방식과 유사한 또 다른 최적화 방법은 처음부터 byte[]가 아닌 long[]에 가능한 많은 데이터를 저장하는 것입니다. 예를 들어 바이너리 파일에서 순차적으로 읽는 경우 또는 메모리 매핑된 파일을 사용하는 경우 데이터를 long[] 또는 단일 긴 값으로 읽습니다.그러면 비교 루프에는 동일한 양의 데이터가 포함된 byte[]에 대해 수행해야 하는 반복 횟수의 1/8만 필요합니다.언제, 얼마나 자주 비교해야 하는지가 문제입니다.바이트 단위 방식으로 데이터에 언제, 얼마나 자주 액세스해야 하는지.API 호출에서 byte[]가 필요한 메서드의 매개변수로 이를 사용합니다.결국, 사용 사례를 실제로 아는 경우에만 알 수 있습니다.
이것은 여기에 제공된 다른 버전보다 거의 확실히 훨씬 느리지만 작성하는 것은 재미있었습니다.
static bool ByteArrayEquals(byte[] a1, byte[] a2)
{
return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
나는 추가 최적화를 통해 ArekBulski가 게시한 EqualBytesLongUnrolled 메서드에서 영감을 받은 솔루션을 선택했습니다.내 경우에는 배열의 배열 차이가 배열의 꼬리 근처에 있는 경향이 있습니다.테스트에서 대규모 배열의 경우 배열 요소를 역순으로 비교할 수 있으면 이 솔루션이 memcmp 기반 솔루션에 비해 성능이 크게 향상된다는 사실을 발견했습니다.그 해결책은 다음과 같습니다.
public enum CompareDirection { Forward, Backward }
private static unsafe bool UnsafeEquals(byte[] a, byte[] b, CompareDirection direction = CompareDirection.Forward)
{
// returns when a and b are same array or both null
if (a == b) return true;
// if either is null or different lengths, can't be equal
if (a == null || b == null || a.Length != b.Length)
return false;
const int UNROLLED = 16; // count of longs 'unrolled' in optimization
int size = sizeof(long) * UNROLLED; // 128 bytes (min size for 'unrolled' optimization)
int len = a.Length;
int n = len / size; // count of full 128 byte segments
int r = len % size; // count of remaining 'unoptimized' bytes
// pin the arrays and access them via pointers
fixed (byte* pb_a = a, pb_b = b)
{
if (r > 0 && direction == CompareDirection.Backward)
{
byte* pa = pb_a + len - 1;
byte* pb = pb_b + len - 1;
byte* phead = pb_a + len - r;
while(pa >= phead)
{
if (*pa != *pb) return false;
pa--;
pb--;
}
}
if (n > 0)
{
int nOffset = n * size;
if (direction == CompareDirection.Forward)
{
long* pa = (long*)pb_a;
long* pb = (long*)pb_b;
long* ptail = (long*)(pb_a + nOffset);
while (pa < ptail)
{
if (*(pa + 0) != *(pb + 0) || *(pa + 1) != *(pb + 1) ||
*(pa + 2) != *(pb + 2) || *(pa + 3) != *(pb + 3) ||
*(pa + 4) != *(pb + 4) || *(pa + 5) != *(pb + 5) ||
*(pa + 6) != *(pb + 6) || *(pa + 7) != *(pb + 7) ||
*(pa + 8) != *(pb + 8) || *(pa + 9) != *(pb + 9) ||
*(pa + 10) != *(pb + 10) || *(pa + 11) != *(pb + 11) ||
*(pa + 12) != *(pb + 12) || *(pa + 13) != *(pb + 13) ||
*(pa + 14) != *(pb + 14) || *(pa + 15) != *(pb + 15)
)
{
return false;
}
pa += UNROLLED;
pb += UNROLLED;
}
}
else
{
long* pa = (long*)(pb_a + nOffset);
long* pb = (long*)(pb_b + nOffset);
long* phead = (long*)pb_a;
while (phead < pa)
{
if (*(pa - 1) != *(pb - 1) || *(pa - 2) != *(pb - 2) ||
*(pa - 3) != *(pb - 3) || *(pa - 4) != *(pb - 4) ||
*(pa - 5) != *(pb - 5) || *(pa - 6) != *(pb - 6) ||
*(pa - 7) != *(pb - 7) || *(pa - 8) != *(pb - 8) ||
*(pa - 9) != *(pb - 9) || *(pa - 10) != *(pb - 10) ||
*(pa - 11) != *(pb - 11) || *(pa - 12) != *(pb - 12) ||
*(pa - 13) != *(pb - 13) || *(pa - 14) != *(pb - 14) ||
*(pa - 15) != *(pb - 15) || *(pa - 16) != *(pb - 16)
)
{
return false;
}
pa -= UNROLLED;
pb -= UNROLLED;
}
}
}
if (r > 0 && direction == CompareDirection.Forward)
{
byte* pa = pb_a + len - r;
byte* pb = pb_b + len - r;
byte* ptail = pb_a + len;
while(pa < ptail)
{
if (*pa != *pb) return false;
pa++;
pb++;
}
}
}
return true;
}
죄송합니다. 관리되는 방식을 찾고 있다면 이미 올바르게 수행하고 있는 것이며, 제가 아는 한 BCL에는 이 작업을 수행하기 위한 기본 제공 메서드가 없습니다.
몇 가지 초기 null 검사를 추가한 다음 BCL에 있는 것처럼 재사용해야 합니다.
사용 SequenceEquals 이를 비교하기 위해.
짧은 대답은 다음과 같습니다.
public bool Compare(byte[] b1, byte[] b2)
{
return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2);
}
이러한 방식으로 최적화된 .NET 문자열 비교를 사용하면 안전하지 않은 코드를 작성할 필요 없이 바이트 배열 비교를 수행할 수 있습니다.이것이 에서 수행되는 방법입니다. 배경:
private unsafe static bool EqualsHelper(String strA, String strB)
{
Contract.Requires(strA != null);
Contract.Requires(strB != null);
Contract.Requires(strA.Length == strB.Length);
int length = strA.Length;
fixed (char* ap = &strA.m_firstChar) fixed (char* bp = &strB.m_firstChar)
{
char* a = ap;
char* b = bp;
// Unroll the loop
#if AMD64
// For the AMD64 bit platform we unroll by 12 and
// check three qwords at a time. This is less code
// than the 32 bit case and is shorter
// pathlength.
while (length >= 12)
{
if (*(long*)a != *(long*)b) return false;
if (*(long*)(a+4) != *(long*)(b+4)) return false;
if (*(long*)(a+8) != *(long*)(b+8)) return false;
a += 12; b += 12; length -= 12;
}
#else
while (length >= 10)
{
if (*(int*)a != *(int*)b) return false;
if (*(int*)(a+2) != *(int*)(b+2)) return false;
if (*(int*)(a+4) != *(int*)(b+4)) return false;
if (*(int*)(a+6) != *(int*)(b+6)) return false;
if (*(int*)(a+8) != *(int*)(b+8)) return false;
a += 10; b += 10; length -= 10;
}
#endif
// This depends on the fact that the String objects are
// always zero terminated and that the terminating zero is not included
// in the length. For odd string sizes, the last compare will include
// the zero terminator.
while (length > 0)
{
if (*(int*)a != *(int*)b) break;
a += 2; b += 2; length -= 2;
}
return (length <= 0);
}
}
위의 멋진 솔루션 중 상당수는 UWP에서 작동하지 않으며 저는 Linq와 기능적 접근 방식을 좋아하므로 이 문제에 대한 제 버전을 알려드립니다.첫 번째 차이가 발생할 때 비교를 피하기 위해 .FirstOrDefault()를 선택했습니다.
public static bool CompareByteArrays(byte[] ba0, byte[] ba1) =>
!(ba0.Length != ba1.Length || Enumerable.Range(1,ba0.Length)
.FirstOrDefault(n => ba0[n] != ba1[n]) > 0);
매우 빠른 바이트 배열 동등 비교기를 찾고 있다면 다음 STSdb Labs 기사를 살펴보는 것이 좋습니다. 바이트 배열 동등 비교자. 이는 byte[] 배열 동등성 비교를 위한 가장 빠른 구현 중 일부를 제공하며 성능 테스트 및 요약을 제공합니다.
다음 구현에 집중할 수도 있습니다.
BigEndianByteArrayComparer - 왼쪽에서 오른쪽으로 빠른 바이트[] 배열 비교기(BigEndian)BigEndianByteArrayEqualityComparer - - 왼쪽에서 오른쪽으로 빠른 byte[] 동등 비교기(BigEndian)LittleEndianByteArrayComparer - 오른쪽에서 왼쪽으로 빠른 바이트[] 배열 비교기(LittleEndian)LittleEndianByteArrayEqualityComparer - 오른쪽에서 왼쪽으로 빠른 byte[] 동등 비교기(LittleEndian)
큰 바이트 배열이 있는 경우 문자열로 변환하여 비교할 수 있습니다.
당신은 다음과 같은 것을 사용할 수 있습니다
byte[] b1 = // Your array
byte[] b2 = // Your array
string s1 = Encoding.Default.GetString( b1 );
string s2 = Encoding.Default.GetString( b2 );
나는 이것을 사용했고 성능에 큰 영향을 미쳤습니다.
