c# - チェックサムを使用したファイル比較

Question

ファイルの重複を見つけるプログラムを書いています。

重複を見つける必要がある 2 つのフォルダーがあります。最悪のシナリオでは、すべてのファイルを互いに比較する必要があります。各ファイルのチェックサムを生成し、チェックサムを比較し、チェックサムが等しい場合はバイトごとのチェックを実行して、ファイルがまったく同じであることを確認することを考えていました。

問題は、バイトごとにチェックするだけでなく、時間を浪費するのに十分な速さのチェックサムジェネレーターはどれでしょうか?

Answer 1

ファイルの完全なリストを取得してから長さでソートすることにより、行う必要がある比較の数と I/O の量を減らすことができます。2 つのファイルは、長さが同じでなければ同一にはなりません。したがって、とにかく取得する必要があるディレクトリ情報を取得する以外に、I/O を実行せずに多数のファイルを削除できます。

同じ長さ X のファイルが 2 つしかない場合、それらのファイルのチェックサムを計算する必要はありません。それらを直接比較するだけです。

同じ長さのファイルが 3 つ以上ある場合は、3 つのファイルすべてのチェックサムを計算し、チェックサムを比較してから、チェックサムが一致する場合はバイトごとの比較を行うことをお勧めします。

Answer 2

チェックサムアルゴリズムは何でも構いません。たとえば、MD5 を使用できます。I/O はチェックサムの計算に費やされる CPU 時間よりもはるかに遅いため、時間を無駄にすることはほとんどありません。CRC32も使用できます。

あなたは言った：「私は重複を見つけなければならない2つのフォルダを持っています。」ここではっきりさせておきたいことがあります。重複ファイルを見つけることが目的の場合、ファイルが 1 つ、2 つ、または x の数のフォルダーにあるかどうかは問題ではありません。n 個のファイルがあると仮定すると、重複を見つけるには n log n の順序で比較する必要があります。n 個のファイルを 1 回読み取り、それらのチェックサムを計算してから、n log n 時間でチェックサムの並べ替えを実行して重複を見つけることは、実際に役立ちます。ただし、最初にファイルサイズを比較し、同じサイズの 3 つ以上のファイルを比較する場合にのみチェックサムに頼ることで、これを回避できることに注意してください。これにより、重複の検索が大幅に高速化されます。