.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 ベースのソリューションは、少なくともそれと同じくらい遅いか、それよりも遅いと思います。
他のヒント
使用できます 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/呼び出し 力が発動する！
[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> これは (実質的に) 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;
}
興味深いのは、2 つの Binary オブジェクトのハッシュが同じ場合にのみ、バイトごとの比較ループに進むことです。ただし、これには、コンストラクターでハッシュを計算するというコストがかかります。 Binary オブジェクト (配列を走査することによって) for ループ:-))。
上記の実装は、最悪の場合、配列を 3 回走査する必要がある可能性があることを意味します。最初に配列 1 のハッシュを計算し、次に配列 2 のハッシュを計算し、最後に (これは最悪のシナリオであるため、長さとハッシュが等しいため) 配列 1 のバイトと配列 2 のバイトを比較します。
全体的に見ても、 System.Data.Linq.Binary は BCL に組み込まれていますが、これが 2 バイト配列を比較する最速の方法とは思えません :-|。
私が投稿しました 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;
}
}
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)。ここにあるいくつかの ベンチマークドットネット 私のマシンからの結果:
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() （アレック・バルスキーの答え）私の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);
そうなると、おそらく質問に記載されている解決策に落ちてしまうでしょう。
このコードのパフォーマンス分析を行うと興味深いでしょう。
多くのグラフィックス カードに組み込まれているブロック転送高速化手法について考えました。ただし、すべてのデータをバイト単位でコピーする必要があるため、ロジックの一部をアンマネージドでハードウェアに依存するコードで実装したくない場合には、これはあまり役に立ちません...
上記のアプローチと同様の最適化のもう 1 つの方法は、最初からできるだけ多くのデータを byte[] ではなく long[] に格納することです。たとえば、バイナリ ファイルから順番に読み取る場合は、または、メモリ マップ ファイルを使用する場合は、データをlong[]または単一のlong値として読み取ります。そうすれば、比較ループに必要な反復回数は、同じ量のデータを含む byte[] の場合に必要な反復回数の 1/8 だけになります。いつ、どのくらいの頻度で比較する必要があるかが問題です。いつ、どのくらいの頻度でバイト単位でデータにアクセスする必要があるか。byte[] を期待するメソッドのパラメータとして API 呼び出しで使用します。結局のところ、ユースケースを本当に知っているかどうかだけがわかります...
これはほぼ間違いなく、ここで挙げた他のバージョンよりもはるかに遅いですが、書くのは楽しかったです。
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 - 左から右への高速 byte[] 配列比較子 (BigEndian)BigEndianByteArrayEqualityComparer - - 左から右への高速 byte[] 等価比較子 (BigEndian)LittleEndianByteArrayComparer - 右から左への高速 byte[] 配列比較子 (LittleEndian)LittleEndianByteArrayEqualityComparer - 右から左への高速 byte[] 等価比較子 (LittleEndian)
巨大なバイト配列がある場合は、文字列に変換することで比較できます。
次のようなものを使用できます
byte[] b1 = // Your array
byte[] b2 = // Your array
string s1 = Encoding.Default.GetString( b1 );
string s2 = Encoding.Default.GetString( b2 );
私はこれを使用しましたが、パフォーマンスに大きな影響があることが分かりました。
