情報と知恵(3)
構造化+知恵
2分探索法は非常に効率的ですが、それでもなお工夫の余地があります。
それは、データの調査位置を狭められた探索範囲の中心と決めている点です。
たとえば、英語のyellowを辞書で調べる場合、2分探索では辞書の中央に位置する言葉を最初に調べます。
しかし、yellowはyで始まるので語数は少なく s や t などの多くの語数の後にある等の知識があれば、当然辞書の後ろのほうの位置を調べるのが合理的です。
すなわち、知恵を動員して調べる位置の予測をするのです。
検索において構造化に加えて知恵を組み込むときは、その効率はさらに上がります。
それは、予測に伴う分布の知識から、つぎの探索範囲が大幅に縮まるからです。
理論的に計算すると、知恵を組み込むときの探索回数は2分探索を超えて、
log2(log2(n))
であることが分かりました。
n=256×1036のような膨大なデータからの検索でも
T(n)=log2(log2(1036))=7
すなわち、7回の検索回数で見つけられるのです。
神の検索
ほとんど架空の条件ですが、1回の探索後に残る探索範囲がlog(n)に縮まるような場合を考えてみました。
n=2128 として、数値的に検索回数
T(n)
を求めてみると、次のようになります。
T(n)=1+T(log2(n))=1+T(128)=1+(1+T(log2(128))=2+T(7)
すなわち、2回も調べれば残った検索範囲は7に激減しています。このような検索は、神の領域というべきか。
ここで、データ数 n=100000000(1億) として、この中から指定したものを見つけ出すまでの必要な各方法ごとの検索回数を、比較のためまとめておきましょう。
検索方法 検索回数
手当たりしだい 460000000 :99%見つけるのに必要回数
経験の墨守
50000000
整理・構造化 27
構造化+知恵 5
神の検索 3
全体のまとめ
全く考えず、慌てふためいた手当たり次第の対応は、結果を運のみに頼る愚かに近い行動です。これより少しマシなのが、経験の墨守です。経験したことしか学ばないのですから、かなりのことを学ぶには相当時間がかかります。
効率を格段に上げるには、考えなくてはなりません。自分の対面していることの構造を知り、その構造に照らして一つの経験から多くの情報を引き出し、次の自分の効率的な行動に結び付けるのです。物事の整理・構造化はlogのオーダで行動の効率を上げるのです。
整理・構造化の上に知恵を加えれば、一つの経験から引き出される情報の効率はlog(log)のオーダでさらに桁はずれの向上となることが分かりました。知恵とは、予測に似たものです。物事の構造化や知恵の活用という知的行為と検索効率におけるlogとが対応しているのは面白いことですね。
手当たり次第は何も学ばず、経験の墨守は経験したことしか学ばないことです。整理・構造化はこれまでの知見を活用するのですから歴史より学ぶことに対応すると考えると形になりますね。
“愚者は経験より学び、賢者は歴史より学ぶ”
とはこのことか。嗚呼。