مقارنة صفيفين بايت في .NET
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;
}
لكني أبحث عن إما أ بي سي إل وظيفة أو بعض الطرق المثبتة للغاية للقيام بذلك.
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، ولكن ليس بالسرعة التي كانت عليها.
إنه يؤدي حوالي سبعة توقيتات أسرع من البسيط for حلقة.يتم استخدام مكتبة J# بشكل مكافئ للأصل for حلقة.باستخدام .SequenceEqual يعمل حوالي سبع مرات أبطأ؛أعتقد أنه فقط لأنه يستخدم IEnumerator.MoveNext.أتخيل أن الحلول المستندة إلى LINQ بطيئة أو أسوأ على الأقل.
نصائح أخرى
يمكنك استخدام 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 لسبب ما، فإن طريقتك مناسبة.
ستعمل بيئة وقت التشغيل للمترجم على تحسين الحلقة الخاصة بك بحيث لا داعي للقلق بشأن الأداء.
ف/استدعاء تفعيل القوى!
[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 - IStructureEquatable
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
إذا لم تكن تعارض القيام بذلك، يمكنك استيراد مجموعة J# "vjslib.dll" واستخدامها طريقة Arrays.equals (بايت []، بايت [])....
ولا تلومني إذا ضحك عليك أحد..
يحرر:مقابل القليل من القيمة، استخدمت 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 لا يأتي في المقدمة بالنسبة لطرق الحد الأقصى لحجم المصفوفة، ولكن الفرق بسيط جدًا لدرجة أنني لا أعتقد أنه سيكون مهمًا على الإطلاق.
معلومات النظام الخاص بي:
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:System.Data.Linq.Binary
عاكس فك طريقة يساوي:
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 حلقة :-) ).
التنفيذ أعلاه يعني أنه في أسوأ الحالات قد تضطر إلى اجتياز المصفوفات ثلاث مرات:أولاً لحساب تجزئة الصفيف 1، ثم لحساب تجزئة الصفيف 2 وأخيرًا (لأن هذا هو السيناريو الأسوأ، الأطوال والتجزئات متساوية) لمقارنة البايتات في الصفيف 1 مع البايتات في الصفيف 2.
عموما، على الرغم من System.Data.Linq.Binary مدمج في BCL، لا أعتقد أنها أسرع طريقة لمقارنة صفيفتي بايت :-|.
أنا نشرت سؤال مشابه حول التحقق مما إذا كانت البايتة[] مليئة بالأصفار.(تم التغلب على رمز 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
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/Invoc أو تثبيت، والتنفيذ واضح تمامًا (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 |
لقد قمت أيضًا بإنشاء ملف جوهر مع جميع الاختبارات.
لقد طورت طريقة تتفوق قليلاً memcmp() (إجابة القاعدة) ويدق بشكل طفيف للغاية EqualBytesLongUnrolled() (إجابة أريك بولسكي) على جهاز الكمبيوتر الخاص بي.في الأساس، يقوم بفتح الحلقة بمقدار 4 بدلاً من 8.
تحديث 30 مارس.2019:
بدءًا من .NET core 3.0، لدينا دعم SIMD!
هذا الحل هو الأسرع بفارق كبير على جهاز الكمبيوتر الخاص بي:
#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.
ربما يجب عليك أيضًا التفكير في التحقق من أن المصفوفات غير فارغة.
إذا نظرت إلى كيفية قيام .NET بعمل string.Equals، فسترى أنه يستخدم أسلوبًا خاصًا يسمى EqualsHelper والذي يحتوي على تطبيق مؤشر "غير آمن". صافي العاكس هو صديقك لمعرفة كيف تتم الأمور داخليا.
يمكن استخدام هذا كقالب لمقارنة مصفوفة البايت التي قمت بتنفيذها في منشور المدونة مقارنة صفيف البايت السريع في C#.لقد قمت أيضًا ببعض المعايير الأولية لمعرفة متى يكون التنفيذ الآمن أسرع من التنفيذ غير الآمن.
ومع ذلك، ما لم تكن بحاجة حقًا إلى أداء قاتل، سأقوم بإجراء مقارنة بسيطة لحلقات fr.
لم أتمكن من العثور على حل أنا سعيد تمامًا به (الأداء المعقول، ولكن لا يوجد رمز/pinvoc غير آمن) لذلك توصلت إلى هذا، لا يوجد شيء أصلي حقًا، ولكنه يعمل:
/// <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
ف/استدعاء memcmp:369 علامة، 53.67
تم اختباره في linqpad، مصفوفات متطابقة بحجم 1000000 بايت (السيناريو الأسوأ)، 500 تكرار لكل منها.
يبدو أن EqualBytesLongUnrolled هو الأفضل من المقترح أعلاه.
الأساليب التي تم تخطيها (Enumerable.SequenceEqual،StructuralComparisons.StructuralEqualityComparer.Equals)، لم تكن صبورًا مقابل بطيء.لقد قمت بقياس هذا على صفائف بحجم 265 ميجابايت:
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 بدون إرفاق مصحح الأخطاء.أعتقد أن الناس يستخدمون مقياسًا خاطئًا لأن ما يهمك إذا كنت تهتم بالسرعة هنا هو المدة التي تستغرقها معرفة ما إذا كانت صفيفتا البايت متساويتين.أي.الإنتاجية بالبايت.
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);
إذن ربما سأصل إلى الحل المذكور في السؤال.
سيكون من المثير للاهتمام إجراء تحليل أداء لهذا الكود.
لقد فكرت في طرق تسريع نقل الكتلة المضمنة في العديد من بطاقات الرسومات.ولكن بعد ذلك سيتعين عليك نسخ جميع البيانات حسب البايت، لذلك لا يساعدك هذا كثيرًا إذا كنت لا ترغب في تنفيذ جزء كامل من المنطق الخاص بك في تعليمات برمجية غير مُدارة وتعتمد على الأجهزة...
هناك طريقة أخرى للتحسين مشابهة للنهج الموضح أعلاه وهي تخزين أكبر قدر ممكن من بياناتك في ملف طويل[] بدلاً من بايت[] منذ البداية، على سبيل المثال، إذا كنت تقرأها بشكل تسلسلي من ملف ثنائي، أو إذا كنت تستخدم ملفًا معينًا للذاكرة، فاقرأ البيانات كقيم طويلة [] أو قيم طويلة مفردة.بعد ذلك، ستحتاج حلقة المقارنة الخاصة بك فقط إلى 1/8 من عدد التكرارات التي يتعين عليها إجراؤها للبايت[] الذي يحتوي على نفس كمية البيانات.إنها مسألة متى وكم مرة تحتاج إلى المقارنة مع ما هو موجود.متى وكم مرة تحتاج إلى الوصول إلى البيانات بطريقة بايت بايت، على سبيل المثال.لاستخدامه في استدعاء API كمعلمة في طريقة تتوقع بايتًا [].في النهاية، لا يمكنك معرفة إلا إذا كنت تعرف حقًا حالة الاستخدام...
من المؤكد تقريبًا أن هذا أبطأ بكثير من أي إصدار آخر موجود هنا، لكن كتابته كانت ممتعة.
static bool ByteArrayEquals(byte[] a1, byte[] a2)
{
return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
لقد استقرت على حل مستوحى من طريقة EqualBytesLongUnrolled التي نشرتها ArekBulski مع تحسين إضافي.في حالتي، تميل اختلافات المصفوفات في المصفوفات إلى أن تكون بالقرب من ذيل المصفوفات.أثناء الاختبار، وجدت أنه عندما يكون هذا هو الحال بالنسبة للمصفوفات الكبيرة، فإن القدرة على مقارنة عناصر المصفوفة بترتيب عكسي يمنح هذا الحل زيادة كبيرة في الأداء مقارنة بالحل القائم على 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 للقيام بذلك.
يجب عليك إضافة بعض الاختبارات الأولية الفارغة ثم إعادة استخدامها كما لو كانت موجودة في 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 هذه: مقارنة مساواة صفيف البايت. وهو يتميز ببعض من أسرع التطبيقات لمقارنة مساواة مصفوفة البايت[]، والتي يتم تقديمها واختبار الأداء وتلخيصها.
يمكنك أيضًا التركيز على هذه التطبيقات:
BigEndianByteArrayComparer - مقارن صفيف بايت سريع [] من اليسار إلى اليمين (BigEndian)BigEndianByteArrayEqualityComparer - - بايت سريع [] مقارنة المساواة من اليسار إلى اليمين (BigEndian)LittleEndianByteArrayComparer - مقارن صفيف بايت سريع [] من اليمين إلى اليسار (LittleEndian)LittleEndianByteArrayEqualityComparer - بايت سريع [] مقارنة المساواة من اليمين إلى اليسار (LittleEndian)
في حال كان لديك مصفوفة بايت ضخمة، يمكنك مقارنتها عن طريق تحويلها إلى سلسلة.
يمكنك استخدام شيء مثل
byte[] b1 = // Your array
byte[] b2 = // Your array
string s1 = Encoding.Default.GetString( b1 );
string s2 = Encoding.Default.GetString( b2 );
لقد استخدمت هذا ورأيت تأثيرًا كبيرًا على الأداء.
