概要
本を読んで勉強しなおし、気になったことを書くシリーズです。
今回は、アルゴリズムクイックリファレンス５章の「探索」がテーマです。
探索の目的
「概観」の内容がいきなり重要です。
- 存在：$C$の中には探している要素$t$があるか。
- 検索：探している要素$t$に合致する$C$の要素を返す。
- 関連情報：目標のキー要素$k$の関連情報を集まり$C$の中から返す。
ここでいう「検索」と「関連情報」は、本質的には同じ意味であるように見えます。
いま、何らかの要素$t$を、母集合$C$から探索する場合を考えます。
例えば、「$t$が含まれているかどうか」ということは、$C$に関する情報です。一般的なプログラミングでは、しばしば$C$に$t$が含まれていれば処理１、含まれていなければ処理２、というような分岐を生じる場合がありますが、これは$C$そのものの性質から処理を変えている、と考えることができます。
一方で、日常生活で$t$を探すというと、$t$が$C$にあるということは必ずしも本質的ではなく、$t$を見つけて使うということに焦点がある場合があります。例えばパスワードを記した紙を探すときは、パスワードを記した紙がどこにあるかということではなく、パスワードを記した紙が本質的に持っている情報が重要であり、またその情報を利用することにこそ興味があります。
この場合、「$t$を探すときに使う情報」というのは、$t$を識別できる必要がありますが、$t$の性質すべてを表している訳ではない、ということに注意します。というのも、パスワードがわかっていれば、パスワードを記した紙を探す必要が元々ないからです。
その意味で、$C$から$t$を探す場合は、じつは$t$は探している対象のすべてではなくて、何らかの付帯する価値なり情報なりを持っていると考えるのが正しいように思われ、自然に「検索」と「関連情報」は同じものを指し示しているように思われます。
予備情報が無ければ逐次探索しかない
何の予備知識もなければ、一つ一つ要素を地道に検証するしかありません。
全順序が入っていて、かつソートされていれば、二分探索
各要素について、（重複の無い）全順序が入っていて、かつソートされているならば、よく知られた二分探索を利用することが可能です。
二分探索の手法自体も面白いですが、プログラムのアーキテクチャ的な意味では「処理を分割できる」ということにも意味があります。つまり、全体としてはソート＋探索になるので、必ずしも効率が良くなるとは限らないものの、ソートと探索のタイミングを分けることができるので、要請に応じて設計を変えられる（変えるべきである）という考え方もできます。
ハッシュに基づいた探索について
プログラミングの世界でしばしば登場する配列という概念があります。この配列へのアクセス自体、（無重複の）ハッシュであると思うこともできます。
二分探索木について
赤黒木についてですが、おそらくライブラリで作られているものを利用するぐらいに留まるので、いったん省略します。
AVLの実装とか入れてもよかったんですが、そこまで興味をそそられず。
おしまい
内容があまりなくなってしまいました。
もともとRubyとPythonの練習を兼ねてもいるので、とりあえず次のような計画で進めますあとは大体Pythonでやります。
ちなみに、このシリーズには、他に次のような記事があります。
バケツソートとn log nの壁 - アルゴリズムクイックリファレンス４章の補足 - ※Ruby
【この記事→】探索と計算の分割 - アルゴリズムクイックリファレンス５章の補足 - ※Python
Pythonで迷路を解く - アルゴリズムクイックリファレンス６章の補足 - ※Python
フォード・ファルカーソン法とその応用 - アルゴリズムクイックリファレンス８章の補足 - ※Python