【プログラミング全般】アルゴリズム入門
ここではアルゴリズムの基本について解説します。
アルゴリズムとは
さっそくですがアルゴリズムとはいったい何でしょうか。
アルゴリズムとは、「ある特定の目的を達成するための処理手順」だそうです。
何かをするときの手順、あるいはやり方のことです。
アルゴリズムにおいて大事なことは、誰がやっても、同じ結果が再現できることです。
逆に言うと、再現ができなかったり、人によって異なる結果になるのであれば、それはアルゴリズムではないということになります。
アルゴリズムの例でよく登場するのは、料理のレシピです。
レシピ通りの材料を揃えて、レシピ通りの手順で作ることができれば、料理がうまい人でも、料理が下手な人でも同じ味になるはずです。
これはまさしくアルゴリズムの例です。
アルゴリズムと聞くとなんだか難しそうに聞こえますが、実は日常の中にも探せば色々あることでしょう。
ただし、レシピに関しては1点注意が必要です。
料理のレシピでは、「塩コショウ：少々」のような、曖昧な表現がある場合もあります。
「5g」のように、具体的な数字で表現されている場合、誰がやっても同じ結果になりますが、「少々」のような表現は人によって解釈が異なるので量がバラバラになる可能性があります。
少々という表現方法はレシピとしては問題ないかもしれませんが、アルゴリズムという観点から見ると厳密にはNGです。
アルゴリズムを学ぶ必要性
アルゴリズムが処理の手順というのは先の説明で理解したかと思います。
では、なぜアルゴリズムを学ぶ必要があるのでしょうか。
それは、プログラミングを学ぶ上では、アルゴリズムを考える力が必須だからです。
私たちが普段生活している中で、何かを実行するときに処理手順を細かく考えるようなことはあまりないかもしれません。
それは、人間は普段から自分で考えながら行動することができるからです。
コンピュータというのは、プログラムという決められた処理の手順書がなければ動くことはできません。
また、予め決められたプログラム通りにしか動くことができません。
つまり、人間のようにその場で考えて柔軟に動くことができないのです。
なので、コンピュータでプログラムを使って何かを実現したい時には、コンピュータに漏れのない正確な処理の手順を与えなければいけません。
この処理の手順こそがコンピュータにおけるアルゴリズムです。
プログラミングというのは、言い換えるとコンピュータに実行させるアルゴリズムを作ることでもあるのです。
なので、アルゴリズムを考える力というのは非常に重要になってきます。
プログラミングの力 = プログラミング言語の知識 + アルゴリズム力
だと思ってもらって構わないでしょう。
コンピュータアルゴリズム
コンピュータにおけるアルゴリズムで代表的なものではどんなものがあるでしょうか。
プログラムの処理の流れは全てアルゴリズムだと言えますが、その中でも代表的なのは、検索と並び替えの処理です。
普段あまり意識しないかもしれませんが、パソコンやスマホを使って作業をするとき、検索と並び替えを行う頻度は意外と多いはずです。
そのため、プログラムを考えるとき、検索と並び替えがどのようなアルゴリズムなのか考えることは大きな意味があります。
人によっては、検索や並び替えがそんなに難しいことなの？
と感じる人もいるかもしれません。
例えば、机の上にバラバラに散らばったトランプがあるとします。
人間なら、その散らばったトランプから特定のマークのトランプを探すのは簡単です。
処理の手順など考えなくても、全体を見渡しながらなんとなーく探してもそこまで時間はかからないでしょう。
また、散らばったトランプを同じ絵柄で数が小さいものから並び替えることも対して難しくありません。
目についたものから適当に動かしていってもそのうち並び終えることでしょう。
しかし、コンピュータこういった人間にとって感覚的にできる作業も細かく指示を与えなければうまく処理できないのです。
ここでは深くは踏み込みませんが、たかが検索や並び替えの処理をするのに、ここまで複雑なことをしなければいけないのか、と驚くかもしれません。
アルゴリズムと速度
コンピュータのアルゴリズムでは検索と並び替えが代表的なアルゴリズムと書きました。
ただ、検索はデータを最初から1つずつ探していけばいずれ見つかります。
また、並び替えに関しても、1つ1つ比較しながら入れ替えていけばいずれ並び変わります。
なので、実現するだけならそこまで難しくなかったりもします。
ただ、速度のことを考えると難易度が増してきます。
皆さんが検索エンジンを使って調べ物をするとき、検索結果が1秒以内に返ってくる検索エンジンと、結果が返ってくるまでに3秒かかる検索エンジンがあった場合、どちらを使いたいと思うでしょうか。
ネットショッピングのサイトで、商品の検索や並び替えが速いサイトと遅いサイトではどちらを使いたいと思うでしょうか。
あえて遅い方を使いたいと思う人はほどんどの場合いないでしょう。
多くの場合、検索や並び替えの速度というのは、ユーザーがサービスを利用したいと思うかどうかの大きな指標となります。
そう考えると、サービスを提供する企業にとって、処理速度を速めることはかなり優先度が高くなります。
ここで大事な要素の1つが、アルゴリズムです。
検索や並び替えなどの処理は、アルゴリズムによって処理速度に大きく差が出てきます。
ここでは詳細な解説はしませんが、どんなに性能のよいハードウェアを使用していたとしても、アルゴリズムが悪ければ速度が遅いものになってしまうのです。
つまり、企業よっては、アルゴリズムを考える力が直接売上に関わる場合もあるのです。
これはある本に書かれていた内容ですが、Googleではブラウザの動作を0コンマ数秒速めるためだけのプログラマーが何名もいるそうです。
そして、その0コンマ数秒単位で、売上が数千万単位で変わってくるのだそうです。
具体的な数字は分かりませんが、それくらいの世界もあるのがエンジニアの世界ということですね。
日本とアメリカの違い
これもとある本で読んだ内容なのですが、日本の場合、プログラムを書く人のことも、アルゴリズムを考える人も、プログラマーと呼んだりエンジニアと呼んだりします。
一方でアメリカでは、アルゴリズムを考える人はディベロッパーという呼ばれ方をしていて、プログラマーとは区別されているのだそうです。
そもそも、日本ではアルゴリズムを考えられる人があまりいないのだと言います。
アメリカでは大学でコンピュータサイエンスを学んだ、アルゴリズムの専門家が多くいるようなのですが、日本ではそのような人は少ないとのこと。
仮にAmazonやFaceBookと同じようなサービスを日本の平均的なプログラマーの人が作ったとしたら、検索結果が30分返ってこないようなことはざらに起こるとのこと。
それくらい、アルゴリズム力というのは国によって差があるということ。
何が言いたいかというと、プログラミングは、プログラミング言語の知識を習得すれば、アルゴリズム力が高くなくてもできてしまう部分があるということ。
しかし、その分、速度や効率まで意識したスマートなアルゴリズムを考える力のある人は、それだけプログラマーとして重宝される存在になれるということでもあります。
フローチャート
フローチャートとは、日本語では流れ図といい、簡単に言うとアルゴリズムを視覚的に表現するための図です。
詳しくはWikipediaなどで説明を見てください。
アルゴリズムは処理の手順を表したものなので、文章で羅列しても構いません。
例えばレシピの場合を考えます。
- 材料を用意する
- 材料を洗う
- 野菜の皮をむく
- 野菜を切る
- 野菜を炒める ・・・
後半は省略しますが、ざっくりこんな感じでしょうか。
では、次に通勤の場合のアルゴリズムを考えてみます。
- 玄関を出る
- 右折する
- 道路を30m直進する
- 信号が青だった場合直進
- 信号が赤だった場合一時停止、青になったら直進
- 20m直進する
- 右折する ・・・
後半部分は省略しますが、通勤の場合はレシピよりも複雑になります。
何が複雑化というと、条件（信号の色）によって行動が変わったり、同じこと（道路をまっすぐ進む）が何度も繰り返されたりします。
これだけならまだ単純ですが、改札を通るときにICカードに残高があるかどうか、電車が満員かどうかなど、条件で行動が変わりそうな要因がいくつかあります。
こうなると、文章の羅列だけで分かりやすく表現するのは大変です。
そういう場合はフローチャートを使用することで、視覚的に分かりやすい表現になります。
フローチャートは、順次（上から下に順序良く処理が進む）、選択（条件によって実行する処理を分ける）、反復（条件が続く限り同じ処理を繰り返す）という3つの要素から成り立ちます。
文章で書くと分かりにくい表現でも、フローチャートにすることでそれぞれの要素を視覚的に認識で切るようになります。
プログラミングをする前にアルゴリズムを整理する場合や、業務の流れをフローチャートとして表現する場合などもあります。
フローチャートの作成はアルゴリズムを考えるうえで必須事項ではありませんが、頭を整理したい時のツールをとして活用できるようになると良いでしょう。
探索のアルゴリズム
ここからは具体的な探索のアルゴリズムについてみていきます。
探索は線形探索（リニアサーチ）と二分探索（バイナリーサーチ）があります。
線形探索（リニアサーチ）
線形探索は、データを最初から順番に探していく探索方法です。
例えば、以下の様に1～10までの数値がランダムに10個並んでいるとします。
10, 5, 8, 9, 7, 2, 3, 1, 6, 4
この中から「2」を探す場合を考えます。
線形探索の場合、最初のデータから順番に探すため、まずは1番目にある10の場所を見て、2と等しいか比較します。
2と等しければそこで終了。
異なる場合は2番目のデータに進みます。
10は2と等しくないため、そのまま2番目へと進みます。
2番目は5なので、ここでも2とは異なります。
そのまま3番目に進みます。
この処理を続けていくと、6番目で「2」を見つけることができます。
これが最もシンプルな探索のアルゴリズムです。
今回の例の場合、運が良ければ1番目で該当のデータが見つかりますが、運が悪ければ10番目まで見つかりません。
平均すると5回の探索でデータが見つかることになります。
二分探索（バイナリーサーチ）
2つ目の探索のアルゴリズムは、二分探索と呼ばれるものです。
これは、データがソート（並び替え）がされていることを前提として、対象のデータがのデータよりも大きいか小さいかの比較を繰り返すアルゴリズムになります。
ここでも1～10までの数値で考えます。
二分探索ではデータは順番に並べられている前提のため、以下の様になります。
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
ここでも「2」を探す例で考えます。
まずデータの中心をみて、その値が探す値より小さいか大きいかを比較します。
ここではまず5を真ん中とし、2と比較します。 そして2より小さいため、5よりも左側にあるデータを対象に考えます。
1, 2, 3, 4
次にこの中からまた中心を見ます。
今回は2となり、探しているデータと一致するためここで処理終了になります。
二分探索では2回の比較でデータを探すことができました。
データの数が偶数の場合、真ん中のデータをどこにするかで処理回数が変わることがありますが、
今回は最初に6で分割したとしても、最大3回の比較で探すことができます。
一度比較するごとにデータを半分にすることができるので、
10 ⇒ 5 ⇒ 2 ⇒ 1
となり、どのデータを対象としても最大3回の比較で絞り込むことができます。
計算量（オーダー）
ここまで線形探索と二分探索の2つの探索に関するアルゴリズムを紹介しましたが、実際どちらの方が処理が高速になるでしょうか。
実際に処理にどれだけの時間がかかるかについては、実行するコンピュータのハードウェアなどにも依存するため、単純比較はできません。
なので、ここでは比較回数によってどちらが処理が高速なのかを判断します。
データの数が10個の場合、整形探索では平均5回の探索で見つかります。
二分探索では、2～3回の比較で見つかります。
線形探索の場合はデータの並び方にもよりますが、一般には二分探索の方が速いと言えそうです。
ただ、データが10個の場合だとそこまで差は感じませんね。
そこで、データ量を10倍にして100個にした場合を考えてみましょう。
線形探索の場合、運が良ければ1個目で見つけることができますし、運が悪ければ100個目で見つかることになります。
つまり、平均すると50回の比較で見つけることができます。
二分探索の場合はどうでしょうか。
データが1個になるまで比較を続けると、
100 ⇒ 50 ⇒ 25 ⇒ 12 ⇒ 6 ⇒ 3 ⇒ 1
となるため、最大で6回の比較で見つかることになります。
こう見ると、データ量が多くなればなるほど二分探索の方が処理が速くなることが分かります。
アルゴリズムの世界では、それぞれのアルゴリズムで計算（処理）がどの程度必要になるかを測る指標があります。
それが計算量（オーダー）と呼ばれるものです。
O(n)
のように表記し、「オーダーエヌ」と呼びます。
nとはデータの数のことです。
線形探索の計算量はまさにO(n)です。
データ量が10の時は平均5回、データ量が100の時は平均50回でした。
そうなると平均の計算量はn/2となりますが、nが十分に大きくなった時、係数は無視することができると考え、O(n)と表します。
データ量がn倍に増えた時に、計算量もn倍増えると理解しても良いでしょう。
では二分探索の場合はどうなるでしょうか。
二分探索の計算量は
O(log2n)
となります。（厳密には2は小さく表記します。）
数学的に言えば2を底とするnの対数です。
※以降lognと書きます。
2を底とする対数は、2を何乗すればnになるかを表します。
例えば、2の3乗は8で、4乗は16です。
そのためデータ量（n）が10の場合は3回の比較で済みます。
そして2の6乗は64、7乗は128のため、データ量（n）が100の場合は6回の比較で済むことになります。
lognの値は、nの値が大きくなっても、そこまで大きくなりません。
そのためデータ量が増えれば増えるほど二分探索の方が有利になるのです。
データ量が2倍になっても比較回数が1回しか増えないことを知っていれば理解しやすいかもしれません。
ただし二分探索はデータが並び替えられている前提でしか使えないことに注意してください。
整列のアルゴリズム
整列は並び替え、ソートなどとも呼ばれます。
要はデータを値が小さい順、あるいは大きい順に並べる時のアルゴリズムのことです。
整列については様々なアルゴリズムがありますので、代表的なものを見ていきます。
バブルソート
バブルソートは数あるソートの中でも最も処理の回数が多くなるソートのため、プログラムの実装で使われることはおそらくほとんどありませんが、アルゴリズム自体はシンプルで最も理解しやすいです。
そのためソートのアルゴリズムの中では最初に紹介されることが多いアルゴリズムです。
バブルとは泡のことですが、データを並び替えるアルゴリズムが水の中の泡が水面に上がっていく様子に似ていることからこの名前が付いたようです。
バブルソートでは、まず1番目のデータと2番目のデータを比較し、1番目のデータの方が大きい場合は入れ替えます。
次に2番目のデータと3番目のデータを比較し、2番目のデータの方が大きい場合は入れ替えます。
まずはこの操作を最後のデータに達するまで繰り返します。
つまり、データがｎ個あるとすると、n-1番目とn番目を比較するまでn-1回繰り返すことになります。
1週目が終われば、最後のデータは並び替えられたことになりますが、そのほかのデータはまだ並び替えられていません。
結局、n個のデータを並び替えるには、n周並び替えの処理を行ことが必要になります。
バブルソートの計算量（オーダー）はどうなるでしょうか。
最初の1周はn-1回の比較を行います。
1週目が終わった時点では最後のデータ（n番目のデータ）は並び替えられた状態です。
2週目は1番目からn-1番目までの比較と入れ替えを行うことで、n-1番目のデータが並び替えられた状態になります。
このように考えると、バブルソートでの比較の回数は、
(n-1) + (n-2) + ... + 2 + 1
となることが分かります。
これは、1/2n(n - 1) = 1/2n2 - 1/2n
と表すことができます。(*は掛け算、^は乗算を表してします)
ソートの場合、比較の回数だけではなくて入れ替えの回数も考慮する必要があります。
バブルソートの場合、最悪の場合は全ての比較で入れ替えを行う必要があります。
つまり、(1/2n2 - 1/2n) 回分の入れ替えの処理が発生します。
要は計算量は(1/2n2 - 1/2n) * 2 = n2 - n
となります。
ただし、オーダーを取る場合にはnの次数が最も大きいもので係数を無視した形で取ります。
そのためオーダーは
O(n2)
となります。
選択ソート
選択ソートは、2番目以降のデータの中から最小のデータを探し、1番目のデータよりも小さい場合はそのデータと入れ替えます。
次は3番目以降のデータの中から最小のデータを探し、2番目のデータよりも小さい場合はそのデータと入れ替えます。
最小のデータを探して順番に入れ替えていくこと繰り返す並び替え方法です。
選択ソートの比較回数はバブルソートと同じです。
そのためnの次数は2となり、オーダーはバブルソートと同じくO(n2)となります。
ただし、選択ソートの場合は交換回数がバブルソートよりも少なくなります。
バブルソートは、最悪の場合(n2 - n)回、つまり比較の度に交換が必要になりますが、選択ソートの場合は1巡につきデータの入れ替えは1回です。
そのため交換回数は多くてもn-1回となります。
これを比較回数とあわせると1/2n2 + 1/2n
となります。
n2の係数が1/2となるので、実質バブルソートの半分程度のコストで処理が可能になります。
挿入ソート
挿入ソートは、1番目のデータが整列されている（ソート済み）状態と考え、2番目以降のデータを1番目のデータのよりも大きいのか小さいのかを比較して適切な場所に挿入していく並び替え方法です。
バブルソートと選択ソートは1巡目、2巡目、周回が増すごとに比較回数は減っていきますが、挿入ソートは逆に周回が増すごとに比較回数が増えるソートになっています。
並び替えが全くされていない状態の場合は比較回数はバブルソートや選択ソートと同じになるので、オーダーはO(n2)です。
ある程度並び替えが行われている場合はその分比較回数は少なく、最短の場合のオーダーはO(n)となります。
参考図書
Googleのブラウザの速度に関する話はこちらの書籍に載っていました。
ディベロッパーの話はこちらの書籍にあります。
検索や並び替え、他にもデータ構造といった、コンピュータアルゴリズムの基本をイラストで分かりやすく解説した本です。
