2つのバイト配列を比較する最も速い方法は何ですか？
https://stackoverflow.com/questions/627742
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
VB.NETの2つの長いバイト配列を比較しようとしていますが、思わぬ障害に遭遇しました。 2つの50メガバイトのファイルを比較すると、ほぼ2分かかります。そのため、間違いを犯しています。私は大量のメモリを搭載したx64マシン上にいるので、問題はありません。以下は、現在使用している、変更したいコードです。
_Bytes と item.Bytes は比較する2つの異なる配列で、すでに同じ長さです。
For Each B In item.Bytes
If B <> _Bytes(I) Then
Mismatch = True
Exit For
End If
I += 1
Next
可能な限り数百メガバイト、場合によっては1ギガバイトまたは2ギガバイトのファイルをできるだけ速く比較できる必要があります。これをより速く行うことができる提案やアルゴリズムはありますか？
Item.bytes は、そのバイト長がユーザーが追加したいアイテムと一致するため、比較のために返されるデータベース/ファイルシステムから取得したオブジェクトです。 2つのアレイを比較することで、ユーザーがDBに何か新しいものを追加したかどうかを判断でき、そうでない場合は、それらを他のファイルにマップするだけで、ハードディスクドライブのスペースを無駄にせずに済みます。
[更新]
配列をByte（）のローカル変数に変換してから、同じ比較、同じコードを実行し、1秒で実行しました（まだベンチマークを行い、他と比較する必要があります）ローカル変数と一般的な配列を使用すると、非常に遅くなります。理由はわかりませんが、配列の使用についてさらに多くの疑問が生じます。
解決
_Bytes（I）呼び出しは何をしていますか？毎回ファイルをロードするわけではありませんか？バッファリングしても、それは悪いニュースです！
潜在的に安全でないコードなどを使用して、一度に長い時間を見るという観点でこれを微最適化する方法はたくさんありますが、合理的なパフォーマンスが最初。明らかに非常に奇妙なことが起こっています。
比較コードを2バイト配列を取る別の関数に抽出することをお勧めします。そうすれば、奇妙なことは何もしないでしょう。また、この場合は For Each ではなく、単純な For ループを使用します。これはより単純になります。ああ、最初に長さが正しいかどうかを確認してください：）
編集：ここに、私が使用するコード（テストされていないが、十分に単純なコード）を示します。それはちょっとC＃です-すぐに変換します：
public static bool Equals(byte[] first, byte[] second)
{
if (first == second)
{
return true;
}
if (first == null || second == null)
{
return false;
}
if (first.Length != second.Length)
{
return false;
}
for (int i=0; i < first.Length; i++)
{
if (first[i] != second[i])
{
return false;
}
}
return true;
}
編集：そして、これがVBです：
Public Shared Function ArraysEqual(ByVal first As Byte(), _
ByVal second As Byte()) As Boolean
If (first Is second) Then
Return True
End If
If (first Is Nothing OrElse second Is Nothing) Then
Return False
End If
If (first.Length <> second.Length) Then
Return False
End If
For i as Integer = 0 To first.Length - 1
If (first(i) <> second(i)) Then
Return False
End If
Next i
Return True
End Function
他のヒント
同じサイズの2つのバイト配列を比較する最も速い方法は、相互運用機能を使用することです。コンソールアプリケーションで次のコードを実行します。
using System;
using System.Runtime.InteropServices;
using System.Security;
namespace CompareByteArray
{
class Program
{
static void Main(string[] args)
{
const int SIZE = 100000;
const int TEST_COUNT = 100;
byte[] arrayA = new byte[SIZE];
byte[] arrayB = new byte[SIZE];
for (int i = 0; i < SIZE; i++)
{
arrayA[i] = 0x22;
arrayB[i] = 0x22;
}
{
DateTime before = DateTime.Now;
for (int i = 0; i < TEST_COUNT; i++)
{
int result = MemCmp_Safe(arrayA, arrayB, (UIntPtr)SIZE);
if (result != 0) throw new Exception();
}
DateTime after = DateTime.Now;
Console.WriteLine("MemCmp_Safe: {0}", after - before);
}
{
DateTime before = DateTime.Now;
for (int i = 0; i < TEST_COUNT; i++)
{
int result = MemCmp_Unsafe(arrayA, arrayB, (UIntPtr)SIZE);
if (result != 0) throw new Exception();
}
DateTime after = DateTime.Now;
Console.WriteLine("MemCmp_Unsafe: {0}", after - before);
}
{
DateTime before = DateTime.Now;
for (int i = 0; i < TEST_COUNT; i++)
{
int result = MemCmp_Pure(arrayA, arrayB, SIZE);
if (result != 0) throw new Exception();
}
DateTime after = DateTime.Now;
Console.WriteLine("MemCmp_Pure: {0}", after - before);
}
return;
}
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl, EntryPoint="memcmp", ExactSpelling=true)]
[SuppressUnmanagedCodeSecurity]
static extern int memcmp_1(byte[] b1, byte[] b2, UIntPtr count);
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl, EntryPoint = "memcmp", ExactSpelling = true)]
[SuppressUnmanagedCodeSecurity]
static extern unsafe int memcmp_2(byte* b1, byte* b2, UIntPtr count);
public static int MemCmp_Safe(byte[] a, byte[] b, UIntPtr count)
{
return memcmp_1(a, b, count);
}
public unsafe static int MemCmp_Unsafe(byte[] a, byte[] b, UIntPtr count)
{
fixed(byte* p_a = a)
{
fixed (byte* p_b = b)
{
return memcmp_2(p_a, p_b, count);
}
}
}
public static int MemCmp_Pure(byte[] a, byte[] b, int count)
{
int result = 0;
for (int i = 0; i < count && result == 0; i += 1)
{
result = a[0] - b[0];
}
return result;
}
}
}
バイトを知る必要がない場合は、一度に8を与える64ビット整数を使用します。実際、8のセットに分離したら、間違ったバイトを見つけることができます。
BinaryReader を使用：
saveTime = binReader.ReadInt32()
またはintの配列の場合：
Dim count As Integer = binReader.Read(testArray, 0, 3)
より良いアプローチ... 2つが異なるかどうかを確認する場合は、バイト配列全体を調べて各バイト配列のハッシュを文字列として生成し、文字列を比較する必要がないため、時間を節約できます。 MD5は正常に動作し、非常に効率的です。
次の2つのことがわかります。
最初に、常にitem.Bytesとして2番目の配列にアクセスするのではなく、ローカル変数を使用して配列を直接指すようにします。つまり、ループを開始する前に、次のようにします。
array2 = item.Bytes
これにより、バイトが必要になるたびにオブジェクトから逆参照するオーバーヘッドが節約されます。特にそのプロパティにGetterメソッドがある場合、Visual Basicではコストが高くなる可能性があります。
また、「確定ループ」を使用します。 「for each」の代わりに。配列の長さはすでにわかっているので、その値を使用してループをコーディングするだけです。これにより、配列をコレクションとして扱うオーバーヘッドが回避されます。ループは次のようになります。
For i = 1 to max Step 1
If (array1(i) <> array2(i))
Exit For
EndIf
Next
厳密に比較アルゴリズムとは関係ありません：
ボトルネックが利用可能なメモリとバイト配列のロードに使用された時間に関連していないことを確認しますか？ 2 GBの2バイトのバイト配列を比較するためだけにロードすると、ほとんどのマシンがひざまずきます。プログラムの設計で許可されている場合、代わりにストリームを使用して小さなチャンクを読み取ってください。
