Make your own free website on Tripod.com

第三章 アルゴリズムとデータ構造

3.1 アルゴリズム入門
□アルゴリズム
アルゴリズム(algorithm)は、問題を解くための手順を定めたものである。
そのため、ある処理をどのような手順で実行するのかをはっきりと定義したものでなければならない。
一般的に、1つの問題に対してその問題を解くアルゴリズムは1つではない。
数あるアルゴリズムの中から、その問題に最適なアルゴリズムを選択することが、システムの効率を左右する非常に大きなポイントとなってくる。

□プログラム
アルゴリズムが決まっただけでは、その問題をコンピュータに解かせることはできない。
なぜならば、アルゴリズムは人間には理解できるが、コンピュータには、そのままの形では理解できないからである。
そこで、アルゴリズムをコンピュータが理解できる形に書き換えたものが必要となり、これがプログラムである。
アルゴリズムが問題をどのような手順で解くかという抽象的なものであるのに対し、プログラムはコンピュータをどのように動かして問題を解いていくか、といった具体的なものである。
プログラムは、C言語やCOBOLなどといったプログラム言語を用いて記述される。

□流れ図
アルゴリズムを言葉の羅列で記述したのでは、非常にわかりづらいものになってしまう。
フローチャート(flow chart:流れ図)とは、記号を用いてアルゴリズムを図表化し、より簡潔に表現したものである。
フローチャートを用いると以下のような効果が期待できる。
(1)プログラム全体の構造や、相互間の関係が視覚的に容易に理解できる。
(2)処理の誤りや、条件の不明確な点などが見つけやすい。
(3)自分以外の人にアルゴリズムを説明するときに、他人でも理解しやすく便利である。
(4)プログラムを修正する場合、修正個所の絞り込みが容易で、かつ、その修正をすることによってプログラムのほかの部分にどのような影響があるのかが把握しやすい。

3.2 基本データ構造
□データ構造
データ構造とは、与えられた問題を解決するためのデータの表現方法である。
問題を解決するには、問題の本質を簡潔に表現し、しかも効率よく解く必要がある。
そのためには、それぞれの問題に応じて、最適な表現方法を選択することが重要となってくる。
データ構造には、基本的なものとして、リスト、スタック、待ち行列(キュー)、木構造などがある。

□配列
配列とは、同じ型のデータを一定の個数並べた形の構造で、データ構造の最も基本となるものである。
すべてのデータが同じ型であるために、特定のデータを参照する場合には添字を用いる。
配列の最も簡単な形である1次元配列が図3−1で、たとえば、データ1を参照したいときには添字を1に、データnを参照したいときには、添字をnにすればよい。
すなわち、配列名Aを使っていい換えると、A(1)=データ1、A(n)=データnということになる。

□ポインタ
ポインタとは、日本語でいえば矢印のことである。
ポインタを使って各要素をつなぐことで、各要素間に論理的な順番をもたせる。
たとえば、図3−2のような要素を考える

図3−2の要素B、C、Aの間には順番というものは存在しない。
この要素B、C、Aに、A→B→Cという順番をもたせるには、図3−3のように、各要素間を矢印で順番につなげばよい。
図3−3の各要素間の矢印のことをポインタとよぶ。
ポインタを先頭から矢印のさしている方向に、順番に終わりまでたどっていくことで、要素を論理的な順番で参照することができる。

□リスト
リストは、配列と同様にデータの並びを表現するための基本的な方法である。
リストは、図3−4のようにデータ値を格納するデータ部と、要素間の関係を示すポインタ部から構成されているのが特徴である。

データ部 ポインタ部

たとえばポインタ部に、次の要素はどれであるかといった情報をもたせれば、このポインタをたどることによって各要素を論理的な順番でアクセスすることができる。
また、要素の挿入や削除は、ポインタをつなぎ換えるだけで行えるので、配列における同様の処理と比較すると、はるかに高速に行うことが可能である。
リストには、ポインタの形式によって線形リスト、双方向リスト、環状リストなどがあるが、ここでは最も基本的な線形リストについて、リストの参照、挿入、削除の方法を説明する。
線形リストとは、図3−5のようにポインタ部に1つのアドレスをもち、一方向につながっているリストのことである。

データ データ データ null

リストの挿入、削除はポインタをつなぎ換えるだけでよいので配列のそれと比較すると非常に効率がよい。
図3−5のAの削除方法を図3−6に、また、リストの挿入方法を図3−7に示す。

□スタック
スタックとは、最後に格納されたデータが最初に取り出されていく、というデータ構造であり、このことを後入れ先出し法LIFO:Last In First Out)という。
スタックは、プログラミングのアルゴリズムとして非常に有効であることはいうまでもないが、OS(オペレーティングシステム)内の機能においてもしばしば用いられる重要なデータ構造である。
スタック構造では、前述したようにデータの格納のされ方、取り出され方に、一定の決まりがある。
データは常に上部から格納され、上部から取り出されていく。
つまり、先に格納したデータは下部に残り、後から格納したデータのほうが先に取り出されていくのである。
図3−8においてデータ3を取り出す作業は、まずデータ4を取り出してからでないと行えないのである。
スタックからデータを取り出すことをポップアップ(POP)といい、逆にデータを入れることをプッシュダウン(PUSH)という。
現在、スタックのどこまでにデータが入っているのかを管理するために図3−9のようなスタックポインタを用いる。
データを1件ポップアップしたときには、スタックポインタを−1し、逆にデータをプッシュダウンしたときには、スタックポインタを+1すればよい。

□キュー
キューは待ち行列ともよばれ、先入れ先出し法FIFO:First In First Out)、すなわち、先に格納したものから先に取り出すというデータ構造である。
キューの例としては、窓口の順番待ちの行列などがあげられる。

IN
データ
データ
データ
データ
OUT

スタックでは、一方向のみでデータを取り出し、格納を行ったが、キューではデータの取出し側と格納側を分離する。
キューへデータを格納することをエンキューといい、格納すべきデータをキューのいちばん後ろに追加する。
逆に、キューからデータを取り出すことをデキューといい、キューに格納されているデータのいちばん先頭から取り出す。

□木
木構造は、各要素が2つ以上のポインタをもち、木の枝、木の葉のように枝分かれしているデータ構造である。
木構造は、階層構造を表現するのに適しており、数式の構造、プログラムのモジュール構成の表現方法としても用いられる。
木の基本構成を表したものが図3−11である。
個々のデータを示す部分を節点(node)、木の中心となるいちばんはじめの節点を(root)、根から見ていちばん末端の節点を(leaf)、節と節のつながりを示す関係を(arc)とよぶ。
木は親子関係に対応しており、上位にある節点を親とよび、枝分かれした下位の節点を子とよぶ。
また、木構造の中にある一部分のことを、部分木とよぶ。
なお、木の分岐数によって、2分木、B木などがある。
◇2分木
2分木は木構造の特殊な形で、各節点が0〜2個の枝をもつ木のことである。(図3−12)。
この2分木上で、各節点が子の節点の値よりも大きい値を持っているものをヒープという。
◇B木(Balanced Tree)
多分木上で、各節点のバランスにある制約を定めたものに、B木がある。
補助記憶装置に大量のデータを蓄え、探索を行うのに適している。

□ハッシュ法
データを格納したり探索したりするのに、上記のリストや2分木は、アクセスに一定の手順をたどる必要がある。
そのため、データの参照順序によっては効率が悪いことがある。
ハッシュ法は、データの値から、格納場所を決める方法で、参照の順序に影響を受けることなくデータを高速にアクセスすることができる。
具体的には、データ(キー値)をある関数で変換し、格納する場所を直接決め、そこにデータを格納する。
この関数のことをハッシュ関数とよぶ。
検索する場合も、検索対象データからハッシュ関数を用いて、格納されている場所を求めて直接アクセスすることができる。
このようにハッシュ法は非常に有効な方法であるのだが、1つ問題がある。
それは、異なるデータであるにもかかわらず、ハッシュ関数で計算した値が同じになってしまうことがある、ということである。
このことを衝突とよぶ。
また、この衝突したデータのことを同義語シノニム)とよぶ。
衝突に対する対応策としては、衝突したデータどうしをリストを用いてつなぎ、ハッシュ表にこのリストの先頭へのポインタをもたせて管理する連鎖法(チェーン法)と、データを直接ハッシュ表の中に格納してしまい、衝突したデータは、ある計算によって求められた、ハッシュ表の空いている部分に格納する開番地法(オープンアドレス法)がある。
図3−13は、前者のチェーン法の表現方法である。
例として、従業員情報をチェーン法を用いて管理する場合を考えてみる。
各従業員には6けたの従業員番号が割り当てられており、ハッシュ関数として、引数(従業員番号)を97で割ったときの余りを返すような関数h(x)を用いると仮定する。
h(x)=x mod 97
(A mod BはAをBで割ったときの余りを返す)

従業員番号 氏名 部署コード
119723 タナカ A011
227492 スズキ C102
335258 イトウ A021
550793 ヤマダ B045

上のような従業員番号に対してハッシュ関数h(x)を用いて、各従業員情報を格納する場所を求めてみると、

従業員番号 ハッシュ関数h(x)の戻り値
119723 25
227492 27
335258 26
550793 27

となる。
従業員番号「119273」「335258」の従業員の情報はそれぞれ25、26という値によって示される場所に格納されるので、ハッシュ関数h(x)によって、これらの従業員情報を一意に識別することが可能である。
しかし、従業員番号「227492」「550793」については、ハッシュ関数h(x)の戻り値がともに27となってしまい、シノニムが発生する。
このような場合にチェーン法では、図3−14のように衝突が発生したデータをリストで管理する。
これらの従業員情報を検索する場合には、まずハッシュ関数を用いてリストの先頭を見つけ、そこからリストを順番にたどって目的のデータを探していかなければならない。
このようにシノニムが発生してしまうと、目的のデータにたどり着くまでに複数回の比較が必要となってしまい、ハッシュ法のメリットが軽減してしまう。
できるだけシノニムが発生しないようなハッシュ関数を用意することが、効率を向上させる最大のポイントである。

□抽象データ型(ADT:abstract data type)
前述のスタック構造を例にとって抽象データ型を説明する。
スタックとは、データを順番に積み上げていく形で格納し、取り出すときは積み上げられたデータのいちばん上から順番に取り出していくデータ構造であった。
このとき、プログラムはデータをスタックに積み上げたり取り出したりすることだけを考えていればよく、スタックを実現している配列の何番目にデータが格納されているのかは知る必要がない。
すなわち、データの格納(push)、データの取り出し(pop)を呼び出すプログラムは、これらの手続きを呼び出すだけでよく、その中で行っている配列の操作のたいへんさを知る必要がないのである。
このようにデータ構造(たとえばスタック)をプログラム中で定義し、それに対する操作をひとまとめ(たとえばpushやpop)にしておけば、プログラムは余計な心配をする必要がないのである。
このようなデータ構造と、それに対する操作(手続き)のまとまりを抽象データ型(ADT)という。
このようなADTを用いることにより、次のような利点が生まれる。
(1)余計なことを気にする必要がなくなる(たとえば、pushするときの配列の添字の変更などは手続きpushに任せておけばよい)。
(2)定義したデータ構造を直接操作する部分が限定されるため、修正、変更が容易になる。
なお、基本的な抽象データ型には、リスト、スタック、キュー、木などがある。

□ポーランド記法(Poland Natation)
数式では、かっこを用いて計算の優先順位を決めている。
この表現方法は人間には理解しやすい形式だが、コンピュータにとっては必ずしも理解しやすい形式であるとは限らない。
ポーランド記法を用いると、かっこを使わずに数式の計算の優先順位を表すことができ、この記法は多くのコンパイラで利用されている。
(a+b)*cの数式をポーランド記法で表現すると、
*+abc
となる。
ポーランド記法で数式を表現するためには、演算子を2つの被演算子の前に置けばよい。
また、ポーランド記法に対して逆ポーランド記法というものも存在し、上記の例を逆ポーランド記法で表現すると、
ab+c*
となる。
逆ポーランド記法で数式を表現するためには、演算子を2つの被演算子のあとに置けばよい。
また、逆ポーランド記法は日本語の読み方とよく似ており、上記の逆ポーランド記法は「aとbを足してcを掛ける」と読むことができる。
また数式を木を用いて表現すると、ポーランド記法、逆ポーランド記法の表現を簡単に導き出すことができる。
数式を木を用いて表現するためには、
・葉には被演算子を割り当てる
・葉でない節点には演算子を割り当てる
ということにしたがって割り当てを行えばよい。
たとえば、(a-b)*(c+d)の数式を木を用いて表現すると次のようになる。
図中の部分木1は(a-b)を表しており、部分木2は(c+d)を表している。
根は、部分木1の数式と部分木2の数式を乗算することを表している。
この木をある規則にしたがってたどっていくことによって、さまざまな数式の表現が可能になる。
その規則には次のようなものがある。
・行きがけ順(先行順)
その節点を通るのが初めてであれば立ち寄る。
2回目以降は立ち寄らない。
・通りがけ順(中間順)
葉ならば立ち寄る。
葉でない節点ならば、そこを通るのが2回目であれば立ち寄る。
・帰りがけ順(後行順)
その節点を通るのが最後であれば立ち寄る。
これらの木のたどり方と、表現方法の対応は次のようになる。
行きがけ順→ポーランド記法
通りがけ順→元の数式(部分木ごとにかっこをつける必要有)
帰りがけ順→逆ポーランド記法
では、(a+b)*cをポーランド記法、逆ポーランド記法の表現にすると、どのようになるだろうか。
数式を木に割り当て、それを行きがけ順でたどればポーランド記法、帰りがけ順でたどれば逆ポーランド記法になるので、答えは次のようになる。

3.3 基本アルゴリズム
□整列(ソート)
整列(ソート)とは、データの並び換えのことである。
たとえば、数字データを小さいものから(昇順)並べ換えたり、あるいは、文字データをアルファベット順に並べ換えるといったアルゴリズムである。
整列は、探索と同様にコンピュータで行う最も基本的なアルゴリズムで、高速化が重要な課題となる。
整列の代表的なものとしては、セレクションソート(選択法)、バブルソート(交換法)、クイックソート、マージソートなどがある。

□セレクションソート(選択法)
セレクションソートは、最も簡単な整列アルゴリズムであるが、効率はよくない。
セレクションソートは、未整列部分の最大値(あるいは最小値)を探して未整列部分の左側のデータと直接交換する方法である。
まず、配列の中から最大値(あるいは最小値)を求め、配列の1番目の要素と交換する。
次に、配列の1番目の要素は整列済みなので、1番目の要素を除いて、配列の2番目以降の要素の中から最大値(あるいは最小値)を求め、配列の2番目の要素と交換する。
これと同様な処理を、配列の要素数がN個であるとすると、N−1番目の要素まで繰り返すことによって、N個のデータを降順(あるいは昇順)に整列することができる。
要素が5個の場合のセレクションソートの流れを、図3−15に示す。

□バブルソート(交換法)
バブルソートは、セレクションソートと同様に基本的な整列アルゴリズムであり、効率はよくない。
バブルソートの基本的な走査方法は、隣接する2つの要素どうしを配列の端から順番に、整列しようとしている大小関係を満たしているかどうかを比較し、大小関係が逆であればそれらの2つの要素を交換していく。
これと同様の操作を、配列の要素数がN個であれば、N−1回繰り返すことによって配列の要素を整列させることができる。
図3−16のように配列を縦に記述して、配列の要素の値が小さいものが、配列の添字の小さいほうに格納されるように交換(昇順に整列)すると、値の小さいものほど上に(軽い泡のように)浮かび上がってくるところから、バブルソート(泡立ち法)と名づけられた。
具体的な例として、n個の要素を昇順に整列することを考える。
まず、n番目(1番下)の要素から1番目(1番上)の要素まで順番に、隣接する2つの要素の大小関係を比較して、値の小さいものが添字の小さいほうに格納されるように交換していく。
この操作によって、配列の要素の中でいちばん小さい値(1番軽い値)が配列の1番目(1番上)に浮かび上がってくる。
次に、n番目の要素から2番目の要素(1番目は整列済み)について同様の操作を行うと、次に小さい要素が配列の2番目に浮かび上がる。
同様の操作をn−1回繰り返すことによって、整列が完了する。
図3−16に、配列の要素の数が4個の場合のバブルソートの操作例を示す。
図3−16のような場合は、n-1回(4−1=3)の操作で整列が完了した。
しかし、整列の要素の並び方によっては、n-1回の操作を行う必要がない場合がある。
整列が完了したあとで、残りの操作を繰り返すのは無駄なので、ある操作を行って1回も交換が発生しなかったら、整列処理を終了させるようなアルゴリズムのほうがより効率がよい。

□クイックソート
セレクションソート、バブルソートは配列の要素の最終的な位置(整列後の位置)を1つひとつ決めていたが、クイックソートの場合は、要素が最終的に格納される位置の決定はあとで行うことにして、全体を2分割する方法を用いている。
まず、配列の中から適当な値を1つ選択する(この値のことを基準値という)。
次の配列の要素を1つひとつ、この基準値と比較して、基準値以下の要素を配列の左側、基準値以上の値を配列の右側に集める。
この操作のことを分割という。
分割が終わったあとの状態は、図3−17の分割後aのようになる。
分割操作後、2つの分割にそれぞれ分割操作を再帰的に適用すれば、全体の配列が完了する(分割後b)。

□マージソート
マージソートはクイックソートと並ぶ高速の整列アルゴリズムである。
しかし、このマージソートにも欠点がある。
それは、主記憶装置上で整列操作を行う場合、ほかの整列アルゴリズムよりも、より多くの記憶容量を必要とする点である。
このため、内部ソート(主記憶上での整列処理)のアルゴリズムとしては、あまり実用化はされていない。
しかし、外部ソート(磁気ディスク装置上での整列処理)のアルゴリズムとしては実用化されている。
マージソートの基本的な考え方は、マージを繰り返し行っていく過程で、整列していこうというものである。
図3−18のような8個のデータを例にとって説明する。
8個のデータを全体としてみれば、5,8,4,7・・・、6,2と、まったく整列されていないが、1個1個のデータを独立してみれば、それらはすでに整列済みであると考えられる。
そこで、これらの整列済みのデータをマージすることによって、次に2個の整列済みのデータを得ることができる。
同様のことを行っていくと、2個の整列済みのデータどうしをマージすることによって、4個の整列済みのデータが得られ、4個の整列済みのデータどうしをマージすることによって8個の整列済みのデータが得られる。
これで、整列が完了するのである。
マージソートでは、データが2n個あれば、n回マージを繰り返すことによって整列は完了する。
マージソートのアルゴリズムは、次の2つのステップから構成されている。
まず第1ステップは、データを2等分、2等分と分割していき、この作業をこれ以上分割できないというところまで続ける(図3−19の第1段階)。
次の第2ステップとして、分割されたデータどうしを繰り返しマージしていき、この作業をすべてのデータがマージされるまで続ける。

□文字列探索
文字列探索とは、ある文字列(テキスト)の中に、特定の文字列(パターン)が存在するかどうかを探索するということである。
前述してきた探索というものは、ある配列の要素の中から、特定の1つの要素を探索するものであったのに対し、文字列探索は、特定の1文字を探索するのではなく、特定の文字列(パターン)を探索するという点が大きく異なる。
つまり、文字列探索では文字の並びということが非常に重要なポイントとなってくるのである。
文字列探索の基本的な考え方は、探索したいパターンを、テキストの最初から1文字ずつ後ろにずらしながら比較していくというものである。
パターンと1文字も異ならず、かつ文字の順番もパターンとまったく同じものが見つかって、はじめて探索できたことになる。

3.4 アルゴリズムの計算量
□計算量(手間、計算複雑度)
1つの問題にはいくつものアルゴリズムが考えられる。
アルゴリズムを評価するうえで重要なのは、結果を出すまでに計算時間がどれくらいかかるか、である。
これを、アルゴリズムの計算量(手間、計算複雑度)という。
ここで、よく試験にも出題される、逐次探索法と2分探索法の計算量を比較してみよう。
図3−20のように、逐次探索法では、端から順番に探索していくため、データがn個あれば、ある値を探索するのに、平均して(n+1)/2回、最大でn回の比較が必要になる。
これに対して、2分探索法では、図3−21のように探索対象範囲を2分していくので、ある値の探索に必要な比較回数は、平均で[log2n]回、最大で
[log2n]+1回となる([x]はxを超えない最大の整数)。
この2つのアルゴリズムは、データ数が多くなればなるほど、2分探索法の効率のよさがわかる。


TOPへ  第四章へ