ハッシュ関数
「重複ファイルを消すPythonスクリプト」について
「404 Blog Not Found:tips - MD5のコスト」にて
(MD5ハッシュ値を求めて比較するのは)ファイルどうしの単純比較の倍以上します。
という指摘がありました。
ごもっとも。
実際に比較対象のファイル群(のうち1セット。28個)を調べてみると、
ファイルサイズが一致したのは1組だけで、
ハッシュ関数としてはサイズを見ておけば十分だという気がします。
件のPythonスクリプトではファイルをMD5ハッシュ値とファイルサイズによって ソートしているんですけど、 アルゴリズムの上ではこのハッシュ関数は何でもいいわけです (衝突が起こると消えて欲しいファイルが消えないことがありますけど、 消したくないファイルが消えることはありません)。 今回調べたデータについては、ファイルサイズを使えばよかったぽいです。 もしかしたら「ファイルサイズ + mバイト目からnバイト」というのも ありかもしんない。
一応、想定している使い方は、 もともと大量のファイルがあって、毎日いくつかのファイルが追加され、 ときどき重複ファイルを消すというようなものです。 既存のファイルでサイズが同じ(でハッシュ値が異なるもの)が 大量にあれば、ハッシュを保存しておくので高速なんですが、 実際のところ、どうなっているのかよくわかりません。
対象のデータによって、 どういうハッシュ関数を使うかを考えるのも面白そうではあります。
Atom Feed