ソックスの左右を揃える
目的：洗濯物の山に埋もれている、すべてのソックスの左右を正しく揃える
方法①
ソックスの片割れを1つ手に取る。それに合う片割れを山から探し、1足に揃えたら脇に置く。次に別のソックスの片割れを手に取る。それに合う片割れを山から探し、揃えたら脇に置く。これを繰り返す。
方法②
ソックスの片割れを1つ手に取る。それを脇に置く。別のソックスの片割れを1つ手に取る。すでに脇に置いたものの中に、それと合うものがあれば、1足に揃えて置く。なければ、まだ片方しかないソックスの列の中に、色またはサイズが同じものの横に並べる。
方法2では、片割れのソックスを一列に並べることで、山の中にあるどの片割れソックスも、絶対に1度しか手にしないで済む。つまり、方法2は「記憶」を利用するおかげで、方法1よりも作業が速くなる。
ソックスの左右を揃える
ソックスの形や色の種類がもっと多かったなら、片割れソックスの列はとても長くなり、山から新たに1枚取り出すたびに、長々とした列を見渡さねばならなくなる。対象物の数が大変多くなると、その列を見渡す作業に時間がかかってしまう。
配列検索に避けられない、遅さというリスクを軽減できるような、単純な配列に代わる構造に「ハッシュテーブル」がある。ハッシュテーブルは、対象物をすべて1つの集合として蓄えるという点では、配列と全く同じ機能をするが、ほぼ瞬間的な検索「定数時間検索」ができるようにするために、順序を犠牲にしている。
大抵の定数時間検索は、仕事が1つの式で表せる。そのため、手元にあるすべてのアイテムに対して同じことを反復して、順を追って仕事を進める必要がなくなる場合に可能になる。その役割は、1つのアイテムを山の中に入れ、あとでそのアイテムが素早く読み出せるようにしておくことだ。
知識を再利用するアプローチは、そうでないものよりも速い。これは、ある仕事を果たすために、何かを繰り返してやらねばならない時に特に役立つ。自分がすべき仕事は、記憶を利用すると素早くやれるかどうか、自問すること。
洗濯物の場合は、洗う直前に衣類の山の中を探し回るのではなく、常日頃から3種類を別々のバスケットに入れておくこと。
自分のサイズの服を見つける
物の集合の中から、1つの物を探し出そうとする時、物を全部一通り見ないことには、見つけられないこともある。これには線形時間がかかる。しかし、その集合が特別な性質を持っている時、つまり物がそこできちんと分類されて並んでいる時には、目的の物を、もっと短い対数時間で見つけることができる。言い換えれば、100のステップを実行する代わりに、7つくらいのステップで済む。
目的：1つのラックにある、自分のサイズのシャツを見つける
方法①：1つのラックの端から端まで、すべてのシャツに目を通す。
方法②：1つのラックの中央近くで、自分のサイズのシャツを探す。中央のシャツが大きすぎたら左に移る。そのシャツが小さすぎたら右に移る。以下、これを繰り返す。
2つの方法を比べると、ラックのシャツが増えるにつれ、方法1は方法2よりも遅くなる。直感的に、中央から始め、続いて左か右に移ることで、チェック範囲を毎回半分にするのは、典型的な対数時間アルゴリズムだ。これは「情報を捨てる」アプローチの1つと考えることができる。
対数関数はゆっくり増加してくれる。私たちは、対象物の個数の増加に対して、煩雑さがゆっくりとしか増加しない解決法を望む。対象物の数にあまり関係なく効率よく使えるからだ。
このようにきちんと分類された物の集合から何かを対数関数的に探し出す方法を「二分探索」と呼ぶ。
