ファイルの全比較とHASH値比較
同一ファイルかどうかを調べるのにMD5を使うというのは、比較するファイルが両方手元にある場合はおすすめ出来ません。
その一番の理由は、コストです。
ファイルどおしの単純比較の倍以上します。
という話があり、
MD5比較は先にファイル数分だけHASH計算して比較はHASH値(16bytes)なのに対して、実データ比較は常に全データの比較が必要だから、ファイル数が増えるほど実データ比較が不利になると思うけど。10ファイルで45回比較?
と反応しました。
Fuktommy氏から
ファイルのサイズが違ったり、頭のところでもう内容が違うことがわかったりすることが多いんじゃないかな。MD5を求めるときは最後まで読むけど、サイズと内容の比較は必ずしも最後まで読まなくてよい。
と言われました。
先頭バイトから違うファイルばかりだと全比較が速いのはその通りだけど、最悪条件の場合がMD5比較に比べて桁違いに遅いのが全比較の問題だと思ってる。条件によってオプションで切り替えるのがいいのかな。
と返しました。そのまとめ的なもの。
まず、わたしがMD5比較のほうがいいと思う理由は、
ということからで、
- 最悪条件の場合(たとえば1GBのファイルが255個あって終端1バイトが全て違うなど)のファイル全比較の速度は許容できない可能性があるのでは?
という心配事があるからです。
Fuktommy氏や元記事の人の意見は、「一般的に同じファイルはそんなにたくさんないし、違うファイルは先頭数バイトからして違う」というものだと解釈しています。
この意見自体は確かに正しいと思ったので、条件によってオプションで切り替えれるのがいいのかなと逃げました。わたしが気にしていることは例外でした。
わたしの感覚だと、MapクラスやDBMの実装は、set時にHASH値*1を計算しておいて、検索木のcompare関数を、『1.先にHASH値で比較を行う 2.HASH値が一致した場合のみ実データを比較』とするような方法が普通なのですが、これはキー値が同一カラムなど関連性の高いものだから、全比較だとHASH値*2比較よりも計算量の多い比較が頻発する可能性が高いと見積もっての仕様だから?
なんとなく、データ検索というひとつのカテゴリと考えて楽したいのですが、統計やベンチマークをだされると確実に負けそうなのであまり反論はできないです。