Home English

Kuina-chan

くいなちゃんDec 15, 2017


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

アルゴリズム

アルゴリズムと計算量

「アルゴリズム」とは、ある目的を達成するための手順のことです。
例えば、英和辞典を渡されて「『Egg』を探せ」と言われたときに、1ページ目から順に開いていけばいつかは『Egg』の項目にたどり着きます。 この場合、「1ページ目から順に開く」という手順が「『Egg』を探す」ことの1つのアルゴリズムになります。
また目的を達成するまでにかかる手順の回数を、そのアルゴリズムの「計算量けいさんりょう」といい、計算にどれくらい時間がかかるかの目安にします。
特にこのアルゴリズムは、辞典のページ数が増えるとそれに比例して『Egg』を見つけるまでに開くページ数も増えますが、このようにデータ量をnとするとnに比例して手順の回数が増えていくとき、そのアルゴリズムの計算量は「Oオーダ(nエヌ)」であるといいます。
ちなみに先頭から順番に探すこのアルゴリズムは「線形探索せんけいたんさく」と呼ばれます。

より速いアルゴリズム

さて「英和辞典の『Egg』を探す」という問題に対し、より計算量が少なくなるアルゴリズムを考えてみます。 ここで本の中間のページを開き、そのページの左右のどちら側に『Egg』の項目があるかを判断して、『Egg』がある側の中間のページを開き同様の操作を繰り返す方法を考えます(二分探索)。
二分探索
二分探索
このアルゴリズムを「二分探索にぶんたんさく」といいます。 先ほどの線形探索では見つかるまですべてのページを探す必要がありましたが、二分探索では探す必要のないページを半分ずつ切り捨てていくためより高速になります。 このように、データ量nに対してnを半分ずつにしていくようなアルゴリズムの計算量は「Oオーダ(logログ nエヌ)」であるといいます。

様々な計算量

O(n)、O(log n)のほかにも様々な計算量が存在します。 主な計算量とその大小関係を主な計算量にまとめました。
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < …
主な計算量
「O(1)」のアルゴリズムとは、データ量nの値によらず、常に手順の回数が一定であるものです。 「O(n log n)」は手順の回数が「n log n」に比例するもの、「O(n2)」は手順の回数が「n2」に比例するものです。 O(n3)を超えると実用的でないほど計算に時間がかかるためあまり見かけません。
この「O(~)」という表記は数学的に厳密に定義されていますが、アルゴリズムの大まかな計算量を扱う用途では厳密な定義を知らなくても問題ありません。 計算量を専門的に扱うときには調べると良いでしょう。

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

速いアルゴリズムを考案することは容易ではなく、アルゴリズムを競う大会もあるほどです。 試しに、抜け落ちたカードの問題のアルゴリズムを考えてみましょう。
抜け落ちたカード
抜け落ちたカード
ぱっと思いつくのは、抜け落ちたカードのアルゴリズム1のアルゴリズムです。
  1. 「1」のカードが存在するかどうか、1枚ずつ探して確認する。
  2. 同様に、「2」のカード、「3」のカード、…、「n」のカードを順番に探す。
  3. 存在しなかったカードが抜け落ちたカードである。
抜け落ちたカードのアルゴリズム1
確かにこの方法で、抜け落ちたカードが判ります。 しかし、「1」のカードが存在するかを確認するだけでおよそn枚のカードを見る必要があり、またこれを「2」「3」…「n」のカードまで繰り返さなければならないので、計算量はn×n=n2に比例し、「O(n2)」となります。 カードが1,000枚あった場合、最悪1,000,000回程度確認しなければなりません。
この問題に対する速いアルゴリズムは抜け落ちたカードのアルゴリズム2の通りです。
  1. 1~nの合計値を計算しておく(A)。
  2. 全部のカードの合計値を計算する(B)。
  3. 「(A)-(B)」の値が抜け落ちたカードである。
抜け落ちたカードのアルゴリズム2
この場合、手順の回数はカードの枚数nに比例するだけなので「O(n)」となります。 たとえカードが1,000枚あっても、抜け落ちたカードを手作業で当てることができそうです。 このアルゴリズムが思い付きましたでしょうか。
速いアルゴリズムを考えるのは大変だと不安になったかもしれませんが大丈夫です。 大抵の問題は先人によって優れたアルゴリズムが考案されているため、考えなくても調べるだけで解決することが多いです。

データ構造

リスト

データの扱い方を工夫することでも処理が効率的になります。 例えば昇順に並んだデータ列を作りたい場合、配列で実現するとデータの追加や削除に時間がかかってしまいます(昇順に並んだ配列の追加)。
昇順に並んだ配列の追加
昇順に並んだ配列の追加
この場合、配列にn個のデータがあったとすると、データの追加や削除における計算量はO(n)になります。
これを「リスト」と呼ばれるデータ構造にすると効率的になります。 リストとは、「値」と「次の要素のアドレス」をセットにした昇順に並んだリストの追加のようなものです。
昇順に並んだリストの追加
昇順に並んだリストの追加
このようにリストではデータの追加や削除はポインタの繋ぎかえだけで済むため、データの数によらず計算量はO(1)です。

キュー

リストのほかにも様々なデータ構造があります。 ここでは主なデータ構造をいくつか紹介します。
窓口に並ぶ人々の行列のように、先に入れたデータから順番に取り出されるデータ構造を「キュー」といいます(キュー)。
キュー
キュー
図の下側にメインメモリ内の状態を示しています。 「3」「5」のデータを入れた後、「3」「5」の順序でデータが取り出されていきます。
キューを配列で実装する場合は図のように、「先頭」と「末尾」を指すポインタを用意し、末尾にデータを入れ、先頭から取り出す方法があります。 ポインタが配列の末端に到達したときは、配列の先頭に戻します。
キューはネットワーク通信やウインドウメッセージなど、寄せられてくるデータを非同期で処理したい場合によく使われます。

スタック

積み上げた荷物のように、後に入れたデータを先に取り出すデータ構造を「スタック」といいます(スタック)。
スタック
スタック
「3」「5」のデータを入れた後、「5」「3」の順序でデータが取り出されています。 関数呼び出しの際に確保される「スタック領域」はこの構造です。
以上で紹介した、リスト、キュー、スタックのデータ構造は、多くの言語では標準機能として用意されています。

ツリー

リストは直線状に連なったデータ構造でしたが、枝分かれして階層構造になったものを「ツリー」といいます(ツリー)。
ツリー
ツリー
ツリーは計算式やXMLのような階層構造になっているもの全般で使われます。

グラフ

ツリーは階層構造でしたが、ループを認めて網目状にしたものを「グラフ」といいます。(グラフ)。
グラフ
グラフ
グラフは各地点間の距離や流量など、要素間の関係を扱うときによく使われます。
グラフには様々なアルゴリズムが考案されています。 例えば、ある地点から別の地点までの最短経路を求めたい場合は、用途によって「ワーシャル・フロイド法」「ダイクストラ法」「ベルマン・フォード法」などのアルゴリズムが使い分けられます。

プログラムで実装する

アルゴリズムを調べて理解したり自分で考案したあとは、それをプログラムで実装しなければなりません。 最後に、プログラムで実装する際のヒントを示しておきます。
例題として、数字が書かれた100枚のカードが昇順に並んでいるときに「1234」と書かれたカードが存在するかを二分探索するプログラムを書いてみましょう。 つまり「1、5、12、30、…、2750、2987」のような中から1234を探すプログラムです。
ここではC言語で書くことにします。 100枚のカードはプログラム上では配列で表現できそうですので、とりあえず配列を宣言します(binary_search1.c)。
int main(void)
{
  int cards[100];
  /* ここで昇順に並んだ100枚のカードをcardsに代入する(省略) */
  
  return 0;
}
binary_search1.c
アルゴリズムを一気にプログラムに書こうとすると、どこから手をつけたら良いのか判らなくなってしまいますので、行われる操作を「順番に」実装していくことが大切です。
二分探索では、まず全データの中間のデータを見て、目的のデータが左右のどちら側にあり得るかを判断するのでした。 これをプログラムに追記しましょう(binary_search2.c)。
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;
}
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を用いて書き直してみましょう(binary_search3.c)。
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;
}
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が存在しなかったことを意味するので、これをループの終了条件にします。 完成したプログラムはbinary_search4.cの通りです。
#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;
}
binary_search4.c
コメントの行で適当に100枚のカードの値を設定すると、1234が存在するかどうかを判定してくれるでしょう。
今回は、アルゴリズムと主なデータ構造について解説しました。 次回は、プログラムが大規模になったときや多人数開発のときに役に立つ「オブジェクト指向」の考え方と機能について解説します。
1513346897ja