６さいからのプログラミング

第8話
アルゴリズムとデータ構造

第7話ポインタと配列と参照第9話オブジェクト指向とクラス

2023年03月26日くいなちゃん

「６さいからのプログラミング」第8話では、目的を達成するにはどのように処理させればよいかという「アルゴリズム」について解説します！

1アルゴリズム

1.1アルゴリズムと計算量

「アルゴリズム」とは、ある目的を達成するための手順のことです。

例えば、英和辞典を渡されて「『Egg』を探せ」と言われたときに、1ページ目から順に開いていけばいつかは『Egg』の項目にたどり着きます。この場合、「1ページ目から順に開く」という手順が「『Egg』を探す」ことの1つのアルゴリズムになります。

また目的を達成するまでにかかる手順の回数を、そのアルゴリズムの「計算量けいさんりょう」といい、計算にどれくらい時間がかかるかの目安にします。

特にこのアルゴリズムは、辞典のページ数が増えるとそれに比例して『Egg』を見つけるまでに開くページ数も増えますが、このように、データ量を

とするとに比例して手順の回数が増えていくとき、そのアルゴリズムの計算量は「オーダエヌ」であるといいます。

ちなみに先頭から順番に探すこのアルゴリズムは「線形探索せんけいたんさく」と呼ばれます。

1.2より速いアルゴリズム

さて「英和辞典の『Egg』を探す」という問題に対し、より計算量が少なくなるアルゴリズムを考えてみましょう。ここで本の中間のページを開き(全100ページの辞典なら50ページ目を開く)、そのページの左右のどちら側に『Egg』の項目があるかを判断して、『Egg』がある側の中間のページを開き同様の操作を繰り返す方法を考えます(図1-1)。

このアルゴリズムを「二分探索にぶんたんさく」といいます。先ほどの線形探索では見つかるまですべてのページを探す必要がありましたが、二分探索では探す必要のないページを半分ずつ切り捨てていくためより高速になります。このように、データ量

に対してを半分ずつにしていくようなアルゴリズムの計算量は「オーダログエヌ」であるといいます。

1.3様々な計算量

、

のほかにも様々な計算量が存在します。主な計算量とその大小関係を図1-2にまとめました。

「」のアルゴリズムとは、データ量

の値によらず、常に手順の回数が一定であるものです。「」は手順の回数がに比例するもの、「」は手順の回数がに比例するものです。

を超えると実用的でないほど計算に時間がかかるためあまり見かけません。

この「」という表記は数学的に厳密に定義されていますが、アルゴリズムの大まかな計算量を扱う用途では厳密な定義を知らなくても「計算量がの高々定数倍である」と考えておけば大丈夫です。例えばは、

かも

かもしれませんが、高々の定数倍の計算量です。

1.4アルゴリズムを考案する方法

速いアルゴリズムを考案することは容易ではなく、アルゴリズムを競う大会もあるほどです。試しに、図1-3の問題のアルゴリズムを考えてみましょう。

ぱっと思いつくのは、図1-4のアルゴリズムです。

確かにこの方法で、抜け落ちたカードが判ります。しかし、「

」のカードが存在するかを確認するだけでおよそ枚のカードを見る必要があり、またこれを「

」「

」…「」のカードまで繰り返さなければならないので、計算量はに比例し、「」となります。カードが1,000枚あった場合、最悪1,000,000回程度確認しなければなりません。

この問題に対する速いアルゴリズムは図1-5の通りです。

この場合、手順の回数はカードの枚数

に比例するだけなので「」となります。たとえカードが1,000枚あっても、抜け落ちたカードを手作業で当てることができそうです。このアルゴリズムが思い付きましたでしょうか。

速いアルゴリズムを考えるのは大変だと不安になったかもしれませんが大丈夫です。大抵の問題は先人によって優れたアルゴリズムが考案されているため、考えなくても調べるだけで解決することが多いです。

2データ構造

2.1リスト

データの扱い方を工夫することでも処理が効率的になります。例えば昇順に並んだデータ列を作りたい場合、配列で実現するとデータの追加や削除に時間がかかってしまいます(図2-1)。

この場合、配列に

個のデータがあったとすると、データの追加や削除における計算量はになります。

これを「リスト」と呼ばれるデータ構造にすると効率的になります。リストとは、「値」と「次の要素のアドレス」をセットにした図2-2のようなものです。

このようにリストではデータの追加や削除はポインタの繋ぎかえだけで済むため、データの数によらず計算量はです。

2.2キュー

リストのほかにも様々なデータ構造があります。ここでは主なデータ構造をいくつか紹介します。

窓口に並ぶ人々の行列のように、先に入れたデータから順番に取り出されるデータ構造を「キュー」といいます(図2-3)。

図の下側にメインメモリ内の状態を示しています。「3」「5」のデータを入れた後、「3」「5」の順序でデータが取り出されていきます。

キューを配列で実装する場合は図のように、「先頭」と「末尾」を指すポインタを用意し、末尾にデータを入れ、先頭から取り出す方法があります。ポインタが配列の末端に到達したときは、配列の先頭に戻します。

キューはネットワーク通信やウインドウメッセージなど、寄せられてくるデータを非同期で処理したい場合によく使われます。

2.3スタック

積み上げた荷物のように、後に入れたデータを先に取り出すデータ構造を「スタック」といいます(図2-4)。

「3」「5」のデータを入れた後、「5」「3」の順序でデータが取り出されています。関数呼び出しの際に確保される「スタック領域」はこの構造です。

以上で紹介した、リスト、キュー、スタックのデータ構造は、多くの言語では標準機能として用意されています。

2.4ツリー

リストは直線状に連なったデータ構造でしたが、枝分かれして階層構造になったものを「ツリー」といいます(図2-5)。

ツリーは計算式やXMLのような階層構造になっているもの全般で使われます。

2.5グラフ

ツリーは階層構造でしたが、ループを認めて網目状にしたものを「グラフ」といいます。(図2-6)。

グラフは各地点間の距離や流量など、要素間の関係を扱うときによく使われます。

グラフには様々なアルゴリズムが考案されています。例えば、ある地点から別の地点までの最短経路を求めたい場合は、用途によって「ワーシャル・フロイド法」「ダイクストラ法」「ベルマン・フォード法」などのアルゴリズムが使い分けられます。

3プログラムで実装する

アルゴリズムを調べて理解したり自分で考案したあとは、それをプログラムで実装しなければなりません。最後に、プログラムで実装する際のヒントを示しておきます。

例題として、数字が書かれた100枚のカードが昇順に並んでいるときに「1234」と書かれたカードが存在するかを二分探索するプログラムを書いてみましょう。つまり「1、5、12、30、…、2750、2987」のような中から1234を探すプログラムです。

ここではC言語で書くことにします。 100枚のカードはプログラム上では配列で表現できそうですので、とりあえず配列を宣言します(図3-1)。


		
			int main(void)
			{
			  int cards[100];
			  /* ここで昇順に並んだ100枚のカードをcardsに代入する(省略) */
			 
			  return 0;
			}

図3-1: binary_search1.c

アルゴリズムを一気にプログラムに書こうとすると、どこから手をつけたら良いのか判らなくなってしまいますので、行われる操作を「順番に」実装していくことが大切です。

二分探索では、まず全データの中間のデータを見て、目的のデータが左右のどちら側にあり得るかを判断するのでした。これをプログラムに追記しましょう(図3-2)。


		
			int main(void)
			{
			  int cards[100];
			  int median;
			  /* ここで昇順に並んだ100枚のカードをcardsに代入する(省略) */
			  median = 100 / 2;
			  if (1234 < cards[median]) { /* 左側にある */ }
			  else if (1234 > cards[median]) { /* 右側にある */ }
			  else { /* cards[median]は1234である */ }
			 
			  return 0;
			}

図3-2: binary_search2.c

データの中間の要素番号を指すmedianという変数を用意して、1234がそのどちら側にあるかをif文で判定しました。

このとき仮に1234が左側にあった場合は「cards[0]～cards[median-1]」の中にあるといえます。 1234が右側にあった場合は「cards[median+1]～cards[99]」の中にあるといえます。そこでこれを、minとmaxという変数を使って「cards[min]～cards[max]」の中にあると表現すれば、以後1234が存在しうる範囲が変わっても同様に処理できそうです。

試しに、今書いたプログラムをminとmaxを用いて書き直してみましょう(図3-3)。


		
			int main(void)
			{
			  int cards[100];
			  int min = 0, max = 99, median;
			  /* ここで昇順に並んだ100枚のカードをcardsに代入する(省略) */
			  median = (min + max) / 2;
			  if (1234 < cards[median]) { max = median - 1; }
			  else if (1234 > cards[median]) { min = median + 1; }
			  else { /* cards[median]は1234である */ }
			 
			  return 0;
			}

図3-3: binary_search3.c

最初はcards[0]～cards[99]の中から探すので、「min=0」、「max=99」とし、minとmaxの中間であるmedianは、両者の平均を取って「median=(min+max)/2」としています。

仮にmedianより左側に1234があった場合、cards[min]～cards[median-1]の中にあることになるので、探索範囲を「max=median-1」に狭めています。 medianより右側に1234があった場合は、cards[median+1]～cards[max]の中にあることになるので、探索範囲を「min=median+1」に狭めています。

さて、あとは新しく更新したminとmaxに対して、同様の操作を繰り返すだけです。もしminとmaxの間隔が無くなればデータ中に1234が存在しなかったことを意味するので、これをループの終了条件にします。完成したプログラムは図3-4の通りです。


		
			#include <stdio.h>
			 
			int main(void)
			{
			  int cards[100];
			  int min = 0, max = 99, median;
			  /* ここで昇順に並んだ100枚のカードをcardsに代入する(省略) */
			  while (max - min >= 0)
			  {
			    median = (min + max) / 2;
			    if (1234 < cards[median]) { max = median - 1; }
			    else if (1234 > cards[median]) { min = median + 1; }
			    else
			    {
			      printf("Found!\n");
			      return 0;
			    }
			  }
			  printf("Not found!\n");
			  return 0;
			}