そのため下記のようなコードを書いたのですが、これがサーバーにとってどのくらいの負荷になるか想像ができずに、やっていいものか躊躇しています。
-----
$a = file_get_contents('a.bin');
$b = file_get_contents('b.bin');
if ($a==$b) {
print "同じデータ";
} else {
print "違うデータ";
}
-----
比較対象のa.binとb.binは10kくらいのデータサイズが想定されています。
このコードは単純な文字列比較と同じように負荷など気にせず気軽に書いていいコードなものでしょうか。アドバイスいただけますと幸いです。
よろしくお願いいたします
実行される回数や、そのコードがのっかてるページ全体の処理にもよると思うんです。
Cherenkov さんから、ハッシュが提案されてますけど、ハッシュ値を求めるには、データ全体を舐める必要があります。
比較対象のデータが、どういうふうに違うかにもよりますが、比較演算子だと先頭のバイトから順番に比較していくという実装になっていると思います。
ということは、比較対象が 10KB あっても先頭の数十倍とを比較しただけで違うという結果が分かる場合があるわけです。
比較する回数が少ないのであれば、単純な比較の方が早いと思います。
<?php $a = (binary)file_get_contents('a.bin'); $b = (binary)file_get_contents('b.bin'); if ($a == $b) { print "同じデータ"; } else { print "違うデータ"; } ?>
上記が当てはまらないのは、何度も比較が繰り返される場合。
その場合は、ハッシュをあらかじめ求めておいて、どこかに取っておくのが良いです。
file_get_contens をする前にハッシュ値だけを比較する。
ハッシュ値が違っていれば、「違うデータ」。
もし、ハッシュ値が同じであれば、あらためて、それぞれのデータを file_get_contents してバイナリで比較する。
という感じになるかと思います。
「同一のハッシュ値になる可能性はあるにはあるが、無視できる程度に非常に確率は低い」という理解であっていますでしょうか。
例えば、SHA-1 の場合、どんなデータでも 160bit のハッシュ値にします。
160bit の情報量は、2 の 160 乗ですから、相手が完全にランダムなデータであれば、衝突する確率は となります。
こういう書き方をすると、「無視できます」って書いてるみたいですね。
同一判定が「たまに間違っても良い」ということが許されるならば、ハッシュ値だけの比較でも良いです。
でも、ハッシュを扱う場合には、「ハッシュ値は衝突することがあるから、ハッシュ値の比較だけで、同一判定をしてはいけない」です。
アドバイスありがとうございます!
なるほど、ハッシュ値を比較するのは手軽でコストも低く済みそうです、大変参考になりました、ありがとうございます。
ただ、対象ファイルがbit単位で細かく中身が変わるので、ハッシュによる比較というのが厳密なものなのかどうか少し気になるのですが・・前のファイルと1bitでも違えば違うハッシュ値が得られるものなのでしょうか。
萩原栄幸が斬る! IT時事刻々:ハッシュ値の有効性 ITに疎い裁判官が起こした問題 (1/2) - ITmedia エンタープライズ http://www.itmedia.co.jp/enterprise/articles/1109/10/news001.html
[鏡] ハッシュ値の衝突問題 -- 戯れ言++ http://www.baldanders.info/spiegel/remark/archives/000048.shtml
上記のURLなどで調べてみたのですが、「同一のハッシュ値になる可能性はあるにはあるが、無視できる程度に非常に確率は低い」という理解であっていますでしょうか。
また、URLによるとMD5よりSHA1(?)というアルゴリズムのほうがよさそうに思いますので、下記の関数で代用してみようかと思います。
これに関しましても、ご意見いただければ嬉しいです。
PHP: sha1_file - Manual http://php.net/manual/ja/function.sha1-file.php
最初にファイルサイズを比較し、それが合致していたら先頭から1バイトずつ比較する関数です。
全体を一気に計算するハッシュ関数に比べ、一般的にCPUにかかる負荷は小さくなります。
function unlike($a, $b) { //サイズ比較 $len_a = file_get_contents($a); $len_b = file_get_contents($b); if ($len_a != $len_b) return FALSE; //バイト比較 $fpa = fopen($a, 'r'); $fpb = fopen($b, 'r'); while (! feof($fpa)) { if (fgetc($fpa) != fgetc($fpa)) return FALSE; } fclose($fpb); fclose($fpa); return TRUE; }
ご回答ありがとうございます。
検討してみたのですが、今回の目的のデータは同一のデータになるケースがほとんどになる想定でして、この方法だとほとんどの場合でデータの末尾まで比較し続ける必要が出てきてしまいますので、CPU負荷が抑えにくそうです。
ご提案いただいてありがとうございました、今後の参考にさせていただきます!
実行される回数や、そのコードがのっかてるページ全体の処理にもよると思うんです。
Cherenkov さんから、ハッシュが提案されてますけど、ハッシュ値を求めるには、データ全体を舐める必要があります。
比較対象のデータが、どういうふうに違うかにもよりますが、比較演算子だと先頭のバイトから順番に比較していくという実装になっていると思います。
ということは、比較対象が 10KB あっても先頭の数十倍とを比較しただけで違うという結果が分かる場合があるわけです。
比較する回数が少ないのであれば、単純な比較の方が早いと思います。
<?php $a = (binary)file_get_contents('a.bin'); $b = (binary)file_get_contents('b.bin'); if ($a == $b) { print "同じデータ"; } else { print "違うデータ"; } ?>
上記が当てはまらないのは、何度も比較が繰り返される場合。
その場合は、ハッシュをあらかじめ求めておいて、どこかに取っておくのが良いです。
file_get_contens をする前にハッシュ値だけを比較する。
ハッシュ値が違っていれば、「違うデータ」。
もし、ハッシュ値が同じであれば、あらためて、それぞれのデータを file_get_contents してバイナリで比較する。
という感じになるかと思います。
「同一のハッシュ値になる可能性はあるにはあるが、無視できる程度に非常に確率は低い」という理解であっていますでしょうか。
例えば、SHA-1 の場合、どんなデータでも 160bit のハッシュ値にします。
160bit の情報量は、2 の 160 乗ですから、相手が完全にランダムなデータであれば、衝突する確率は となります。
こういう書き方をすると、「無視できます」って書いてるみたいですね。
同一判定が「たまに間違っても良い」ということが許されるならば、ハッシュ値だけの比較でも良いです。
でも、ハッシュを扱う場合には、「ハッシュ値は衝突することがあるから、ハッシュ値の比較だけで、同一判定をしてはいけない」です。
なかなか難しいですね・・
今回のケースでは、ほとんどの場合で同一のデータの比較を繰り返す想定でして、同一時になるべく負荷を抑えたいと考えています。
そのため、ご提案いただいた下記の方法だと
> ハッシュ値が違っていれば、「違うデータ」。
> もし、ハッシュ値が同じであれば、あらためて、それぞれのデータを file_get_contents してバイナリで比較する。
結局バイナリ比較を行う必要があることがほとんどになってしまいそうです。
そのため、同一判定に多少の誤りがあることが承知の上で、
「ハッシュ値が同一であれば同一データとして扱う。ただし、一定以上古いデータもしくはランダムに低い確率で同一データであっても違うデータとして扱う」
というような形で誤りを許容できるようなアルゴリズムにしようと思います。
諸々アドバイスいただいてありがとうございました!
今回のケースでは、ほとんどの場合で同一のデータの比較を繰り返す想定でして
データのバリエーションが、あまりないってことなんですね。
であれば、ハッシュ値の比較でも、それなりの精度が期待できるかもしれません。
ハッシュ値をキャッシュしておけるなら、複数のキャッシュ値を保存して、それらを比較することで、精度はかなり上がると思います。
なかなか難しいですね・・
2012/09/17 11:47:44今回のケースでは、ほとんどの場合で同一のデータの比較を繰り返す想定でして、同一時になるべく負荷を抑えたいと考えています。
そのため、ご提案いただいた下記の方法だと
> ハッシュ値が違っていれば、「違うデータ」。
> もし、ハッシュ値が同じであれば、あらためて、それぞれのデータを file_get_contents してバイナリで比較する。
結局バイナリ比較を行う必要があることがほとんどになってしまいそうです。
そのため、同一判定に多少の誤りがあることが承知の上で、
「ハッシュ値が同一であれば同一データとして扱う。ただし、一定以上古いデータもしくはランダムに低い確率で同一データであっても違うデータとして扱う」
というような形で誤りを許容できるようなアルゴリズムにしようと思います。
諸々アドバイスいただいてありがとうございました!
データのバリエーションが、あまりないってことなんですね。
2012/09/17 12:30:23であれば、ハッシュ値の比較でも、それなりの精度が期待できるかもしれません。
ハッシュ値をキャッシュしておけるなら、複数のキャッシュ値を保存して、それらを比較することで、精度はかなり上がると思います。