サーチのアルゴリズムを学ぶ

サーチ（探索）でPHPの基礎を学ぼう

　「【一気に覚えるPHP！】アルゴリズムで頭の体操（http://www.thinkit.co.jp/article/62/）」では、定石と呼べる基本的なソートのアルゴリズムを勉強することで、より本質的なプログラムの考え方を身につけることを目指しました。今回は、好評だったこの連載の続編として、サーチ（探索）のアルゴリズムをPHPで書いてみましょう。

　前回も説明しましたように「いまさら」サーチのプログラムをPHPで書く必要はありません。実際のプロジェクトを戦いとするならば、アルゴリズムを学ぶことは、戦う自分の基礎となる「筋力」を鍛えることです。そして、これを鍛えるには、先人たちの知恵に学び、また、すでにあるものでもそれを自分で（＝独力で）作ってみることが一番です。プログラミング言語やライブラリ関数がカバーしてくれる範囲のものを手作りすることで、考え方の基本を身につけることができます。

　では早速今回もサーチとそれに関連するデータ構造をPHPで書いていきましょう。はじめに基本を学びましょう。サーチには2種類の方法があります。

　1つ目がリニアサーチ（線形探索）と呼ばれるサーチです。サーチ（search：探索）とは文字通りものを「探す」ことです。一番簡単な方法がこの線形探索です。この方法では、データを端から順番に見ていきます。平均探索時間は要素数をn個とすればn/2です。

　2つ目がバイナリサーチ（2分探索）と呼ばれるサーチです。バイナリサーチの平均探索回数はlog2(n)です。ただし、データがソートされていることが条件でした。それぞれの方法での探索時間を表すために、要素数nとの関係を図1-1にしておきます。

　さて、紹介した方法は、探索する対象が配列であり、その中身は固定されていることを暗黙の前提としてきました。しかし実際のシステムではデータは増えたり減ったりします。新しいデータが追加され、また、古いデータが削除されます。

　このようにデータ増減する場合の探索方法を考えるのが今回のシリーズの目的です。

　PHPの配列は、途中にデータを追加したり、あるいは途中のデータを削除することが簡単にできます。配列も伸び縮みするわけです。ですから、ここでの議論はPHPで実際にプログラムすることはありえないでしょう。しかし、内部構造を探るためにあえてPHPで書いてみます。

　要素が増えたり減ったりする可変長のデータ構造としていくつかありますが、その代表選手はリンクトリスト（linked list）です（図1-2）。個々の要素はデータそのものと、要素をつなぐポインタから構成されます。

　ここではデータ（data）としてどのようなものが含まれるかは重要ではありません。このような「構造」があって、データを追加したり削除したりできるという点に注意してください。

リストとアンカー

　図1-2で左端には「ポインタ」だけのものがあります。これをアンカー（anchor）と呼びます。船のいかりのことですね。後でプログラムを紹介しますが、その際、変数に$anchorという名前を与えています。これを表すものだと思ってください。

　このリスト構造に新しい要素を追加することを考えます。

　はじめは、空っぽのanchorがあるだけです。つまり、$anchorという変数があったとして、その中身がnullになっている状態です。

　ここにひとつの要素を「追加」します。ひとつひとつの要素はリスト構造のひとつの「箱」の形をしています。この要素を「作って」、それをアンカーにつなぐだけです（図1-3）。

　要素がすでにいくつかつながっている場合は少し考えなければなりませんが、それほど難しくはありません。

　追加する場所を気にしなくてよいのであれば、先頭に挿入するのが最も簡単です（図1-4）。図1-4のようにポインタをつなぎ替えるだけです。

　すでにソートされているリストに追加するには、挿入するための場所を探すことになります（図1-5）。ここではアルファベットの小さい順に要素がつながっていますが、いま「B」を追加しようとしていますが、「B」より大きな「D」を見つけたところで、その「前」に要素を挿入しています。

　これは「【一気に覚えるPHP！】アルゴリズムで頭の体操（http://www.thinkit.co.jp/article/62/）」で説明した「挿入ソート」（insertion sort）そのものです。

　では、続いて図示したリスト構造とそれを操作する機能をPHPで書いてみましょう。