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

2008年11月7日(金)
須藤 克彦

性能

 このプログラムの性能については、線形探索と同じことはわかるでしょう。データの個数が増えれば増えただけ探索時間も増えます。

 そこで高速化のために、データをソートしておいて二分探索はできないでしょうか?

 残念ながら、この構造では二分探索ができません。おわかりと思いますが、探索する区間を半分に分けるなどということができません。各要素のアクセスするためにはリンクを順にたどるしかないのです。

 そこで、リンクによるリスト構造でありながら、二分探索と同じ性能が出るものを考えますが、それは次回に譲って、その前に要素を削除することを考えましょう。

要素の削除

 図3-1を見てください。この状態で「C」の要素を削除することを考えます。削除した後は図3-2のようになるでしょう。

 ここでちょっと気をつけなければいけないことがあります。「C」を切り離す際に必要なことは、「C」の要素の内容(next)を書き換えることではなくて、ひとつ前の要素のnextを書き換えることです。図3-2では要素「A」のnextを書き換えることになります。

 さらにややこしいことに、もし「A」の要素を切り離すとしたらどうなるでしょう?

 その場合は図3-3のanchorの値を書き換えることになります。

 リンクトリストを扱う際、要素を切り離すのが一番ややこしいところです。この切り離しのための関数delete()は図3-4のようになるでしょう。

 このプログラムでは、切り離す要素がアンカーから直接つながっている場合と、そうでない場合とを区別しています。PHPでは、関数への引数を参照渡し(call by reference)で渡す場合のほかは、ポインタという概念が明確ではありません。それでこのように場合分けをしましたが、この部分は図3-5のように書くこともできます。

 図3-6のようにCで書いた例を見ればその意味がはっきりするでしょう。

 これでリンクトリストの追加と削除ができるようになりました。もちろん、探索もできます。

 ポインタの扱いはややこしいと思いましたか?でも、このように絵を見れば、どこを操作すればよいかわかったと思いますが、いかがでしたでしょうか?

 リンクトリストはデータの伸び縮みに対応できます。ただ、検索速度が遅いのが難点です。そこで次回は、リンクトリストとおなじようなポインタによってつながっている構造であっても、二分探索と同様のスピードが出る構造を考えてみましょう。

 なお、本稿の執筆にあたって、以下を参考にしました。

Robert Sedgewick『Algorithms』Addison-Wesley(発行年:1983)

神戸情報大学院大学
1980年立命館大学理工学部卒、独立系ソフトハウスに入社。CやFORTRANコンパイラなどの言語処理系の設計・開発に約10年間従事。その後ユーザ系企業でUNIXによるクライアントサーバシステムの設計・開発を主導。同時に企業の内外で人材育成に注力する。現在は神戸情報大学院大学で講師として教鞭(きょうべん)をとる。「ソフトウエア工学の基礎を勉強してオールラウンドプレーヤーを目指せ」が技術者育成についての口癖。http://www.kic.ac.jp/professors/sudo/index.html

Think ITメルマガ会員登録受付中

Think ITでは、技術情報が詰まったメールマガジン「Think IT Weekly」の配信サービスを提供しています。メルマガ会員登録を済ませれば、メルマガだけでなく、さまざまな限定特典を入手できるようになります。

Think ITメルマガ会員のサービス内容を見る

他にもこの記事が読まれています