非常に大きなファイルの内容を比較する必要があります。プログラムの速度は重要です。100% 一致する必要があります。多くの情報を読みましたが、最適な解決策が見つかりませんでした。私は 2 つの選択肢と両方の問題を考えています。
何を提案しますか？多分私はスレッドを利用できますか？MemoryMappedFile は役に立ちますか?
ファイルが 100% 同一であることを 100%保証する必要がある場合は、バイト単位で比較する必要があります。それが問題に内包されているだけです - 誤マッチングのリスクが 0% の唯一のハッシュ方法は恒等関数です!
残っているのは、バイトごとの比較をスキップできるようにするための迅速な回答をすぐに提供できるショートカットです。
原則として、平等を証明するための唯一の近道は同一性を証明することです。オブジェクト指向コードでは、実際には同じオブジェクトである 2 つのオブジェクトが表示されます。ファイルで最も近いのは、バインディングまたは NTFS ジャンクションが 2 つのパスが同じファイルへのパスであることを意味する場合です。これは非常にまれにしか発生しないため、仕事の性質上、通常よりも頻繁に行われるようになっている場合を除き、チェックする純利益にはなりません。
そのため、ミスマッチを見つけるための近道が残されています。パスを増やすために何もしませんが、失敗をより速くします:
次に、実際の比較をできるだけ速く行うという問題があります。一度に 4 オクテットのバッチを整数にロードし、整数比較を行うと、多くの場合、オクテットごとのオクテットよりも高速になります。
スレッド化が役立ちます。1 つの方法は、ファイルの実際の比較を複数の操作に分割することですが、可能であれば、異なるスレッドで完全に異なる比較を行うことで、より大きな効果が得られます。多くのアドバイスをするには、あなたが何をしているのかについてもう少し知る必要がありますが、主なことは、テストの出力がスレッドセーフであることを確認することです。
同じファイルを調べるスレッドが複数ある場合は、それらが互いに離れて動作するようにします。たとえば、4 つのスレッドがある場合、ファイルを 4 つに分割するか、1 つにバイト 0、4、8 を使用させ、別のスレッドにバイト 1、5、9 などを使用させることができます (または 4 オクテット グループ 0、4、8等）。後者は、前者よりも誤った共有の問題が発生する可能性がはるかに高いため、そうしないでください。
編集：
また、ファイルで何をしているかにも依存します。あなたは 100% の確実性が必要だと言っているので、このビットはあなたには当てはまりませんが、偽陽性のコストが実際の失敗ではなく、リソース、時間、またはメモリの浪費である場合、より一般的な問題について追加する価値があります。 、そしてあいまいな近道を介してそれを減らすことはネットウィンになる可能性があり、これが当てはまるかどうかを確認するためにプロファイリングする価値があります.
処理を高速化するためにハッシュを使用している場合 (少なくともいくつかの明確な不一致をより速く見つけることができます)、Bob Jenkins の Spooky Hashが適切な選択です。暗号学的に安全ではありませんが、それが目的でない場合は、128 ビット ハッシュとして非常に迅速に作成されます (暗号化ハッシュよりも、または多くのGetHashCode()実装で採用されているアプローチよりもはるかに高速です)。暗号化ハッシュが意図的に衝突を回避することは別の問題です)。私はそれを.Net用に実装し、それを使いたいと思ったときに他の誰も持っていなかったので、それをナゲットに置きました。
テスト ファイル サイズ: 118 MB
所要時間: 579 ミリ秒
等しいか? 真実
static bool Compare(string filePath1, string filePath2)
{
using (FileStream file = File.OpenRead(filePath1))
{
using (FileStream file2 = File.OpenRead(filePath2))
{
if (file.Length != file2.Length)
{
return false;
}
int count;
const int size = 0x1000000;
var buffer = new byte[size];
var buffer2 = new byte[size];
while ((count = file.Read(buffer, 0, buffer.Length)) > 0)
{
file2.Read(buffer2, 0, buffer2.Length);
for (int i = 0; i < count; i++)
{
if (buffer[i] != buffer2[i])
{
return false;
}
}
}
}
}
return true;
}
テスト ファイル サイズ: 118 MB
所要時間: 340 ミリ秒
等しいか? 真実
static bool Compare2(string filePath1, string filePath2)
{
bool success = true;
var info = new FileInfo(filePath1);
var info2 = new FileInfo(filePath2);
if (info.Length != info2.Length)
{
return false;
}
long fileLength = info.Length;
const int size = 0x1000000;
Parallel.For(0, fileLength / size, x =>
{
var start = (int)x * size;
if (start >= fileLength)
{
return;
}
using (FileStream file = File.OpenRead(filePath1))
{
using (FileStream file2 = File.OpenRead(filePath2))
{
var buffer = new byte[size];
var buffer2 = new byte[size];
file.Position = start;
file2.Position = start;
int count = file.Read(buffer, 0, size);
file2.Read(buffer2, 0, size);
for (int i = 0; i < count; i++)
{
if (buffer[i] != buffer2[i])
{
success = false;
return;
}
}
}
}
});
return success;
}
テスト ファイルのサイズ: 118 MB
所要時間: 702 ミリ秒
等しいか? 真実
static bool Compare3(string filePath1, string filePath2)
{
byte[] hash1 = GenerateHash(filePath1);
byte[] hash2 = GenerateHash(filePath2);
if (hash1.Length != hash2.Length)
{
return false;
}
for (int i = 0; i < hash1.Length; i++)
{
if (hash1[i] != hash2[i])
{
return false;
}
}
return true;
}
static byte[] GenerateHash(string filePath)
{
MD5 crypto = MD5.Create();
using (FileStream stream = File.OpenRead(filePath))
{
return crypto.ComputeHash(stream);
}
}
tl;dr バイト セグメントを並列に比較して、2 つのファイルが等しいかどうかを判断します。
なぜ両方ではない？
最初のパスのハッシュと比較してから、競合に戻り、バイトごとの比較を実行します。これにより、100％の一致信頼性が保証された最大速度が可能になります。
大量のファイルがあり、重複を特定しようとしている場合は、費用の順に作業を分類しようとします。私は次のようなことを試みるかもしれません：
1）ファイルをサイズでグループ化します。サイズの異なるファイルは明らかに同一にすることはできません。この情報は非常に安価に取得できます。各グループにファイルが1つしかない場合は、完了です。重複はありません。それ以外の場合は、手順2に進みます。
2）各サイズグループ内で、ファイルの最初のnバイトのハッシュを生成します。違いを検出する可能性が高い妥当なnを特定します。多くのファイルには同じヘッダーがあるため、nがそのヘッダーの長さよりも大きいことを確認する必要はありません。ハッシュでグループ化します。各グループに1つのファイルが含まれている場合は完了です（このグループ内に重複はありません）。それ以外の場合は、手順3に進みます。
3）この時点で、ファイル全体のハッシュを生成したり、バイトごとの比較を行ったりするなど、よりコストのかかる作業を行う必要があります。ファイルの数とファイルの内容の性質に応じて、さまざまなアプローチを試すことができます。うまくいけば、以前のグループ化によって重複の可能性が絞り込まれ、実際に完全にスキャンする必要のあるファイルの数が非常に少なくなります。
いずれにせよ、最終的にハッシュはファイルをバイトごとに読み取ることになります...したがって、正確な比較を探している場合は、比較を行うこともできます。あなたが達成しようとしていることについて、もう少し背景を教えていただけますか? 「大きな」ファイルの大きさはどのくらいですか? どのくらいの頻度でそれらを比較する必要がありますか?
完全な比較が必要な場合は、バイト単位の比較を避けることはできません (ハッシュを行うには、ファイルをバイト単位で読み取る必要があります)。そのため、問題はデータの読み取りと比較の方法です。
そのため、次の 2 つの点に対処する必要があります。
目的は、ハードディスクがデータを読み取るのと同じ速さで比較を実行できること、および常に遅延なくデータを読み取っていることを確認することです。ドライブからデータを読み取ることができるのと同じくらい速くすべてを実行している場合、ハードディスクの読み取り速度がボトルネックになるため、それは可能な限り高速です。
ハッシュを計算するには、ファイル全体を読み取る必要があります。
両方のファイルを一緒に開いて、チャンクごとに比較するのはどうですか？
擬似コード：
open file A
open file B
while file A has more data
{
if next chunk of A != next chunk of B return false
}
return true
このようにして、一緒にロードしすぎたり、以前に不一致を見つけた場合にファイル全体を読み取ったりすることはありません。最適なパフォーマンスを得るための適切なサイズを決定するには、チャンクサイズを変更するテストを設定する必要があります。