寄せられる感想メールに多い「軽い」「速い」そして「なぜ?」にお答えします。
まず、「軽い」ですが、これは単にマルチスレッドでの検索を行うようにして、検索中も操作を受け付けるようにしているためにそのように感じるのではないか、と言うことで納得して下さい。処理中に「待ち状態」にならず、制限付きでも操作を受け付ける状態というのは使ってみると、「軽く」感じるものなんです。
で、「速い」理由ですが、F_CHKで採用しているアルゴリズムを基本的な部分で流用していますので、それを解説しましょう。
検索は以下の順序で行われます。
- 指定された箇所のすべてのファイルを羅列
- 羅列したファイルをファイルサイズ順に並べ替える
- ファイルサイズが同じものを比較し、一致したものを表示する
ファイルの内容が一致しているならファイルサイズも同じハズですから、この順序は特に目新しいものではないでしょう。
その代わり、実際にファイルの内容を比較するところでかなり工夫してみました。
次のような感じでファイルがあったとします(ファイルサイズはすべて同じとする)。
ファイル名 | ファイルのタイプ | 一致状況 |
ファイル1 | テキスト | ☆ |
ファイル2 | プログラム | ◎ |
ファイル3 | テキスト | ☆ |
ファイル4 | テキスト | ☆ |
ファイル5 | MIDIファイル | |
ファイル6 | プログラム | ◎ |
ファイル7 | HTML | |
ファイル8 | WAV | |
一致状況に書かれている記号が同じもの同士が内容が一致しているとしてF_CHKとSAME_Fで採用しているアルゴリズムでの比較をしてみましょう。
本来ファイルタイプなんて関係ないんですが、説明しやすくするためにあげておきました。
通常のアルゴリズム(総当たりで比較する)であればこういう比較をするはずです。
比較ファイル1 | 比較ファイル2 | 結果 |
ファイル1 | ファイル2 | × |
ファイル1 | ファイル3 | ○ |
ファイル1 | ファイル4 | ○ |
ファイル1 | ファイル5 | × |
ファイル1 | ファイル6 | × |
ファイル1 | ファイル7 | × |
ファイル1 | ファイル8 | × |
ファイル2 | ファイル3 | × |
ファイル2 | ファイル4 | × |
ファイル2 | ファイル5 | × |
ファイル2 | ファイル6 | ○ |
ファイル2 | ファイル7 | × |
ファイル2 | ファイル8 | × |
ファイル3 | ファイル4 | ○ |
ファイル3 | ファイル5 | × |
ファイル3 | ファイル6 | × |
ファイル3 | ファイル7 | × |
ファイル3 | ファイル8 | × |
ファイル4 | ファイル5 | × |
ファイル4 | ファイル6 | × |
ファイル4 | ファイル7 | × |
ファイル4 | ファイル8 | × |
ファイル5 | ファイル6 | × |
ファイル5 | ファイル7 | × |
ファイル5 | ファイル8 | × |
ファイル6 | ファイル7 | × |
ファイル6 | ファイル8 | × |
ファイル7 | ファイル8 | × |
既に気力の持たない状態になってますね。
そこで、人間様の考えるような方法で比較します。
STEP1 ファイル1との比較
ファイル1とファイル2〜ファイル8までをとりあえず全部読み込んで比較します。この比較自体は省略できないので仕方ありません。
この時点ではファイル1とファイル3とファイル4が一致していることがわかります。
また、このとき、ファイルの内容をもとにちょっとした計算をして各ファイルの特徴を捉えておきます。
ファイルの特徴・・・・簡単に言えばファイルの中のデータを16進数としてそのまま合計しているような感じだと思って下さい。実際には単純な合計ではありませんが、ある程度特徴を捉えやすいように計算しています。また、この計算は最初にファイルを読み込んだときに行って、結果を記憶しておきます。
STEP2 ファイル2との比較
ファイル2とファイル3〜ファイル8の比較をしますが、STEP1と違う動きをします。
ファイル2とファイル3を比較しようとするのですが、ファイル3は既にファイル1と内容が一致していますし、ファイル2とファイル1は一致していません。
つまり、
A=BかつA≠CならばB≠C
ということを考え、ファイル2とファイル3の内容を読み込んで比較することはせず、そのまま次へ進みます。
ファイル4についても同様のことが言えるので、次へ。
そしてファイル5と比較です。
ファイル5は今のところファイルとも一致していませんので、まず、STEP1で計算しておいた「ファイルの特徴」を比較します。このとき、「ファイルの特徴の値」はファイルの内容が同じなら全く同じですが、ファイルの内容が違う場合、かなり高い確率で違う値になります(そうなるように工夫して計算いるつもりです)。
ファイル2はプログラムファイルでファイル5はMIDIファイルですから違う値になっている可能性が非常に高くなります。
逆に言えば同じ種類のファイルは同じ値を持つことも多くなるので、影響の出にくいように調整しています。
するとファイル5を読み込んで比較する必要がなくなるので次へ。
ファイル6との比較はきちんと行います。
ファイル7,ファイル8はおそらくわざわざ読み込んで比較することはしません。
STEP3 ファイル3との比較
ファイル3とファイル4〜ファイル8の比較です。
しかし、ファイル3とファイル4はファイル1と内容が一致していますので、
A=BかつA=CならばB=C
と言うことで改めて読み込んで比較する事はしません。
そしてファイル5〜ファイル8ですが、
A=BかつA≠CならばB≠C
ですから、読み込みません。
以降、同様の手順で比較をしていこうとしますが、比較する可能性のあるのは
- ファイル5とファイル7
- ファイル5とファイル8
- ファイル7とファイル8
です。しかも「可能性がちょっとだけある」だけで、多分読み込むことはありません。
すると処理全体を通して、ファイルの内容を読み込むのは最低8回多くて14回。
これに対して全部総当たりで読み込んだ場合、読み込み回数は28回。
最大で3分の一、最悪の場合でも半分の読み込み回数でファイルの比較が終了してしまいます。
ある程度検索対象のファイルの内容に依存する部分がありますが、ファイルの読み込み回数が減ると言うことは処理時間が短くなるって事に繋がるので、結構効果があるんじゃないかな〜と思ってこんなアルゴリズムを採用しています。
人の手で比較するのと非常によく似た方法で比較しているので思いついたときには画期的だったのですが、
実際にプログラムにするのは滅茶苦茶大変
ですよ。 |