在.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; } 但是我正在寻找一个BCLfunction或一些高度优化的经过validation的方式来做到这一点。
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中有一个新的内置解决scheme – IStructuralEquatable
static bool ByteArrayCompare(byte[] a1, byte[] a2) { return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2); }
用户gil提出了产生这个解决scheme的不安全的代码：
// 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位进行比较。 这种计数就是数组开始qwordalignment的事实。 这将工作，如果没有qwordalignment，只是没有那么快。
它比简单的for循环执行大约七个定时器。 使用与原始for循环等效执行的J＃库。 使用.SequenceEqual运行速度慢七倍; 我认为只是因为它使用IEnumerator.MoveNext。 我想基于LINQ的解决scheme至less是缓慢或更糟的。
如果您不反对，可以导入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和更新版本有一个新的公共typesSystem.Data.Linq.Binary封装了byte[] 。 它实现了IEquatable<Binary> （实际上）比较两个字节数组。 请注意， System.Data.Linq.Binary也具有来自byte[]隐式转换运算符。
MSDN文档： System.Data.Linq.Binary
等式方法的Reflector反编译：
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中，我不认为这是比较两个字节数组的最快方法： – |。
我发布了一个类似的问题，检查byte []是否为零。 （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; } }
在两个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"); }
我会使用不安全的代码，并运行比较Int32指针的for循环。
也许你还应该考虑检查数组是否为非null。
如果你看看.NET如何实现string.Equals，你会发现它使用了一个名为EqualsHelper的私有方法，它有一个“不安全的”指针实现。 .NET Reflector是你的朋友，看看事情是如何完成的。
这可以用作字节数组比较的模板，我在博客文章中使用C＃进行快速字节数组比较 。 我也做了一些基本的基准，看看什么时候安全执行比不安全的更快。
这就是说，除非你真的需要杀手性能，否则我会去做一个简单的循环比较。
让我们再添加一个！
最近微软发布了一个特殊的NuGet包， System.Runtime.CompilerServices.Unsafe 。 这很特别，因为它是用IL编写的，并且提供了C＃中不能直接使用的低级function。
它的一个方法， Unsafe.As<T>(object)允许将任何引用types转换为另一个引用types，跳过任何安全检查。 这通常是一个非常糟糕的想法，但是如果两种types都有相同的结构，它就可以工作。 所以我们可以用这个来把一个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或者pinning，而且实现非常简单（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 |
我也创build了所有testing的要点 。
我开发了一个方法，略微击败memcmp() （基座的答案），非常EqualBytesLongUnrolled()击败EqualBytesLongUnrolled() （Arek Bulski的答案）。 基本上，它展开循环4而不是8。
public static unsafe bool NewMemCmp(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; } public static unsafe bool NewMemCmp(byte[] arr0, byte[] arr1, int length) { fixed (byte* b0 = arr0) fixed (byte* b1 = arr1) { return NewMemCmp(b0, b1, length); } }
运行速度比memcmp()快大约25％，比我的机器上的EqualBytesLongUnrolled()快大约5％。
为了比较短字节数组，以下是一个有趣的黑客行为：
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);
那么我可能会掉到问题中列出的解决scheme。
对代码进行性能分析会很有趣。
找不到解决scheme，我完全满意（合理的性能，但没有不安全的代码/ pinvoke），所以我想出了这个，没有真正的原创，但工程：
/// <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; }
与此页面上的一些其他解决scheme相比的性能：
简单的循环：19837刻度，1.00
* BitConverter：4886滴答，4.06
不安全比较：1636个滴答声，12.12
EqualBytesLongUnrolled：637个滴答声，31.09
P /调用memcmp：369个滴答，53.67
testingLINQpad，1000000字节相同的arrays（最坏的情况下），每个500次迭代。
从上面的build议看来， EqualBytesLongUnrolled是最好的。
被跳过的方法（Enumerable.SequenceEqual，StructuralComparisons.StructuralEqualityComparer.Equals），不耐用。 在265MB的arrays上，我测量了这个：
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 |
我想过在许多graphics卡中内置的块传输加速方法。 但是，那么你将不得不复制所有的数据字节明智的，所以这不会帮你很多，如果你不想在非托pipe和硬件相关的代码中实现你的逻辑的整个部分…
另一种类似于上面所示方法的优化方法是，从一开始就将尽可能多的数据存储在long []而不是byte []中，例如，如果从二进制文件中顺序读取数据，或者如果使用内存映射文件，请以long []或单个long值的forms读入数据。 然后，比较循环只需要包含相同数据量的byte []所需的迭代次数的1/8。 这是一个什么时候需要比较的频率，以及您需要多长时间一次访问数据的频率，例如，在API调用中将其用作预期方法中的参数一个字节[]。 最后，你只能告诉你是否真的知道用例…
这几乎肯定比这里给出的任何其他版本都要慢，但写起来很有趣。
static bool ByteArrayEquals(byte[] a1, byte[] a2) { return a1.Zip(a2, (l, r) => l == r).All(x => x); }
对不起，如果你正在寻找一个pipe理的方式，你已经做得正确，据我所知，BCL没有内置的方法来做到这一点。
你应该添加一些初始的空检查，然后就像在BCL中那样重用它。
使用SequenceEquals进行比较。
简短的答案是这样的：
public bool Compare(byte[] b1, byte[] b2) { return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2); }
以这种方式，您可以使用优化的.NETstring比较来进行字节数组比较，而无需编写不安全的代码。 这是如何在后台完成的：
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); } }
我做了一些测量使用附加的程序.net 4.7发布没有附加debugging器。 我认为人们一直在使用错误的度量标准，因为如果您关心速度，那么您需要花多长时间才能确定两个字节数组是否相等。 即吞吐量以字节为单位
StructuralComparison : 2838.8 MiB/s for : 30553811.0 MiB/s ToUInt32 : 23864406.8 MiB/s ToUInt64 : 5526595.7 MiB/s memcmp : 1848977556.1 MiB/s
正如你所看到的，没有比memcmp更好的方法，它的速度更快。 一个简单for循环是第二好的select。 而且它仍然令我难以置信，为什么微软不能简单地包含一个Buffer.Compare方法。
[Program.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(); var offset = Measure("offset", new TimeSpan(), () => { return; }, ignore: true); 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); }); } } }
如果你正在寻找一个非常快速的字节数组相等比较器，我build议你看看这个STSdb实验室的文章： 字节数组相等比较器。 它具有byte []数组相等比较的一些最快的实现，它们被呈现，性能testing和总结。
你也可以专注于这些实现：
BigEndianByteArrayComparer – 从左到右的BigEndianByteArrayComparer – BigEndianByteArrayEqualityComparer – – BigEndianByteArrayEqualityComparer – BigEndianByteArrayComparer – BigEndianByteArrayComparer – 快速byte []数组比较从右到左（LittleEndian） LittleEndianByteArrayEqualityComparer – 快速字节[]等号比较器从右到左（LittleEndian）
如果你有一个巨大的字节数组，你可以通过将它们转换为string来进行比较。
你可以使用类似的东西
byte[] b1 = // Your array byte[] b2 = // Your array string s1 = Encoding.Default.GetString( b1 ); string s2 = Encoding.Default.GetString( b2 );
我已经使用了这个，我看到了巨大的性能影响。
