小学校でもプログラミング教育が注目されるように、プログラミングが話題になっていますが、プログラミングにはさまざまな知識が必要です。そんな中で、プログラミングに関わる人でなくても知っておきたいのが「アルゴリズムの考え方」。プログラマがどんなことを考えてプログラムを作っているのか、その考え方をぜひ参考にしてみてください。
プログラミングとアルゴリズムの違い
「プログラミング」という言葉は開発工程全体を指すこともありますが、プログラムを実装する作業のことを指すこともあります。
図のような開発工程において、要件定義で開発する内容を決め、設計の工程ではどのように作るかを決めます。実装は実際にソースコードを作成することで、テストでは開発されたプログラムが正しく動作するか確認します。問題なければ、運用や保守といった工程に進みます。
この全体のことをプログラミングということもありますし、実装の部分だけをプログラミングやコーディングと呼ぶこともあります。
一方で、「アルゴリズム」は問題を解決するための手順や計算方法のことです。私たちの身の回りの問題には、同じ答えが得られる複数の解き方があります。いくつかの候補の中から、良い方法を選ばなければなりません。このとき、効率の良い方法を使えば、処理時間を大幅に短縮できます。
高速なアルゴリズムが求められる理由
効率の良い方法を考えるため、アルゴリズムの教科書では、「探索」や「ソート（並べ替え）」がよく取り上げられます。問題がイメージしやすく、さまざまなアルゴリズムで処理時間を比較できるだけでなく、プログラミング初心者の練習にちょうど良いこともその理由です。
探索は、多くのデータの中から欲しいものを探すことです。多くのデータがあるとき、前から順番に探していると欲しいデータが見つかるまでに時間がかかってしまいます。そこで、高速に見つける手順が求められます。
ソートはたくさんのデータを昇順や降順に並べかえることです。Excelなどの表計算ソフトではボタンを押すだけで簡単に並べ替えてくれますが、自分でプログラムを開発する場合は自分で実装しないといけません。これもうまく作らないと、データが増えたときに処理に時間がかかってしまいます。
アルゴリズムの必要性が感じられるのは、多くの場合、開発してから少し時間が経ってからのことです。開発した当初はデータが少なくて、問題なく動作しているように見えても、時間が経ってデータ量が増えてきたときに急速に処理が遅くなるのです。
開発しているときには納期があって、それに間に合わせないといけないからとりあえず動くものを作るのですが、データの追加や機能の追加などによって処理が複雑になると、処理に時間がかかるようになるのです。
「良い」アルゴリズムとは？
一般的に、アルゴリズムを比べるときに「良い」というのは「速い」という意味で使われます。アルゴリズムでは計算量という呼び方をしますが、「時間計算量」と「空間計算量」があり、一般的には計算量といえば「時間計算量」のことを指します。時間計算量というのは、データ量が多くなってもあまり処理時間が増えない考え方です。
例えば、図のような2つのアルゴリズムがあったとします。
アルゴリズムAは入力データ量の2乗に比例して処理時間が増えています。つまり、データ量が1件であれば1の時間で処理できるものが、データ量が10件になれば100の時間に、データ量が100件になると10000の時間に、と急速に増えていきます。
一方のアルゴリズムBでは、入力データ量が1件であれば1の時間で処理できるものが、データ量が10件になると10の時間、100件になると100の時間で処理できます。つまり、この2つならアルゴリズムBの方が良い、ということがいえます。
探索にかかる時間の比較
具体的な例として、探索の手法の中から「線形探索」と「二分探索」を考えてみましょう。
線形探索は、前から順番に調べることです。例えば、図のようなデータがあったとき、前から順番に調べていけば、いつかは欲しいデータが見つかります。ただし、データの数が増えるとそれだけ時間がかかります。
もう1つの方法が二分探索で、名前の通り2つに分ける方法です。半分に分けて調べれば、調べる範囲が減ります。しかも、真ん中と比べて大きいか小さいかを考えるだけなので、今回の場合であればどのデータでも4回くらい調べれば見つかります。ただし、データがソート（並べ替え）されていることが前提です。
ソート（並べ替え）にかかる時間の比較
並べ替えの場合も考えてみましょう。シンプルな方法として、選択ソートがあります。名前の通り、一番小さいものを選択して入れ替える方法で、左から順番に処理していきます。
例えば、最初は1が一番小さいので入れ替えは発生しませんが、次は2が小さいので10と入れ替える、次は3が小さいので18と入れ替える、ということを繰り返せば並べ替えができます。わかりやすい方法ですが、データの数が増えると時間がかかりそうだということは想像できると思います。
そこで、高速に処理する方法としてクイックソートがあります。
二分探索と同じように、ある値で分割して、それよりも小さいものと大きいものに分ける方法です。例えば、最初は8よりも小さいものと大きいものに分けます。さらに、それぞれについて4よりも小さいものと大きいもの、17よりも小さいものと大きいものに分ける、ということを繰り返します。すると、最終的には小さいものが左に、大きいものが右に並びます。
これは効率が良さそうですが、分ける基準をうまく選ぶ必要がありそうです。実際には、多くの場合はクイックソートが高速に処理できることが知られています。
処理時間の測定方法
どうやって処理時間を調べるのか、ということを考えてみましょう。実際にプログラムを作ってみれば処理時間は測定できますが、それでは実装してみないと処理時間がわかりません。もし作ってみて、問題があると修正にも時間がかかります。結果として、納期に間に合わないことになってしまいます。
そこで、作る前の段階でざっくりと処理時間を見積もる必要があります。このとき、どのくらい繰り返すのかをオーダーという方法で表現します。
例えば、線形探索の場合、前から順番に処理していくので、データがn個あればそれだけ時間がかかります。これをO（n）と書きます。これは、nの数が2倍になれば処理時間も2倍に、10倍になれば処理時間も10倍になるものです。
一方で、選択ソートのような場合を考えてみると、まず一番小さいデータを探す作業を繰り返します。次に、2番目のデータを探す作業を繰り返します。これを最後まで繰り返すので、ざっくり考えると二乗になります。これをO（n2）と書きます。
他の方法についても整理すると、次の表のようになります。
これを見ると、線形探索よりも二分探索の方が速いことがわかります。この表の下にいけばいくほど時間がかかり、難しい問題なのだということがわかります。
アルゴリズムを学ぶ必要性
このようなアルゴリズムを考えるとき、発想力が必要になりますが、大事なのは新しいことを思いつくのではなく、掛け合わせや組み合わせが大事だということです。ひらめくというよりも、考えつく、といった方がいいかもしれません。
例えば線形探索と二分探索の違い、選択ソートとクイックソートの違いを知っている上で、今の自分の解きたい問題をどうやって工夫して解くか、を考えるときに、それを参考にして考えると、いい方法が思いつくかもしれません。
アルゴリズムを考えるとき、過去の知識がないとアイデアは出てきません。このため、色々なアルゴリズムを知っていることが重要になります。高速に処理できないアルゴリズムは知らなくていいと思うかもしれませんが、色々な手法があることを知っておくと、自分の仕事がそれに近い状況になったときに、他にいい方法があることに気づけるのです。
実際にはソートなどを一から実装することはほとんどありません。例えば、Javaで書くときには、データを配列に入れて、「sort」という関数を呼び出すだけです。すでに他の人が作ったライブラリがありますので、これを使うだけで高速に処理できるのです。
それならこれを使うだけで十分で、アルゴリズムを学ばなくてもいいと考える人もいるかもしれません。もちろん、仕事としてソートを使うときには私もこう言ったライブラリを使います。その他にも、フレームワークやデザインパターンなど、先人が作った知恵がありますので、これはできるだけ活用しましょう。
ただし、その考え方を知っておかないと、ソート以外の場合はライブラリが用意されていないわけです。もし似たような場面が出てきたときに、ソートのアルゴリズムを知らないと応用できません。
最後に
アルゴリズムは学ぶだけでなく、とにかく自分で作ってみることが大事です。一から作るのは大変ですが、自分で身体を使って体験しないと、その効果がわかりません。野球でも料理でも、音楽でも、本を読んだらプロのようにできるかというと、そんなことはなく、自分で体を動かして、やってみないとできるようにはなりません。
本を読むだけだったり、コピー&ペーストするだけだったりするのではなく、実際に本に書かれているソースコードを入力し、試行錯誤することでその効果を体験できるのです。ぜひ試してみてください。
