はじめに
昨今、スマートフォンのスペックが以前と比べてより良くなっています。
おかげで少し重たい処理を端末にやらせても問題なく動作し、アプリの表現の幅が広がったと思います。
しかし便利な半面、「アルゴリズム」という概念から目を背ける癖がつきやすい環境になったとも思います。
そこで本記事は、不定期、数回に分けて、「より良いアプリ開発のためにアルゴリズムを理解する」ことについてまとめていきます。
まず、１回目の今回は、【その０】として、アプリを処理の観点から見るための理論導入編になります。
どうしても情報工学の分野については数学が絡み、内容も高度なものになりがちです。
数学は極力避けてまとめていますが、ある程度のプログラミング経験者を対象読者と考えています。
アルゴリズムについて
よくインターネットや本を通じて「アルゴリズム」について調べると
「問題Pを解くための計算手順」、「機械的に実行可能な有限個の命令からなるプログラム」や
「問題Pに属する入力に対して必ず有限の時間内にて正しい解を出力し、停止するプログラム」など
複数の複雑な意味が出てくると思います。
アルゴリズムの意味を正しく理解するには「クラスPとクラスNP」や「チューリングマシン」などと言った概念を正しく理解する必要があります。
そこで慣れないうちはアルゴリズムを「問題を解くための計算手段」というイメージでふんわり覚えておくことをオススメします。
アルゴリズムの計算量
問題Pを解くアルゴリズムは複数あるのが普通です。
例えば、「ばらばらに並べられた数字を数の小さい順から並べる」という問題に対してのアルゴリズムの一例をあげると
“5 3 4 2 1″のような数字の列の最初から順に見ていき一番小さい数字を見つけたら一番左に置き、次に２番目から順に同様な手順で一番小さい数字を探し、見つけたら２番目に置くのを数字の個数の合計数回行うと問題を解くことができます。
入力: “5 3 4 2 1”
1回目: “1 5 3 4 2”
2回目: “1 2 5 3 4”
3回目: “1 2 3 5 4”
4回目: “1 2 3 4 5”
5回目: “1 2 3 4 5”
このように綺麗に並べることができました。
他にも数字のグループから適当な数字をひとつ選び、その数字未満を左のグループ、他を右のグループとグループを分割して行き、分割できなくなったら今度は結合していくと綺麗に並べることができます。
入力: “5 3 4 2 1”
1回目(分割): “2 1”, “4 5 3″ 選んだ数字: 4
2回目(分割): “1”, “2”, “4 3”, “5” 選んだ数字: 2と5
3回目(分割): “1”, “2”, “3”, “4”, “5” 選んだ数字: 3
4回目(結合): “1”, “2”, “3 4”, “5”
5回目(結合): “1 2”, “3 4 5”
6回目(結合): “1 2 3 4 5”
例のような並び替え問題に対するアルゴリズムも複数あります。
このようなとき、それらアルゴリズムを評価するときの評価基準はいくつか考えられますが、たいていの場合は「計算時間」で評価されることが多いです。
そして、計算時間の少ないアルゴリズムの方が良いアルゴリズムであると考えられます。
この計算時間を単純抽象化した概念こそが「アルゴリズムの計算量」です。
漸近計算量
アルゴリズムの計算量は一般的に関数\(T(n)\)と表記することが多く、最悪（一番時間のかかるパターン）の場合を想定しているため「最悪計算量」と呼ぶときもあります。
一般的にアルゴリズムの評価をするときは「漸近計算量」をつかいます。
漸近計算量と計算量\(T(n)\)の関係は「オーダー」と呼ばれる記号\(O\)と単純な\(n\)の関数\(f(n)\)を用いて
\(T(n) = O(f(n))\)という形式で表現されます。
すなわち、漸近計算量は「増加率」に注目したものになります。
\(O\)記法の定義は高校数学レベルの範囲を超えるため本記事では触りませんが、計算量からの簡単な変換は「一番大きそうな項の変数だけを抽出するイメージ」です。
例えば、\(T(n) = 5n^3 + 2n^2 + 4n + 2\)という多項式の漸近計算量は\(n\)が\(1000\)の時、
\(1000^3\)と一番数が大きくなりそうな項の変数である\(n^3\)を使い\(O(n^3)\)と表すことができます。
他にも\(T(n) = 2log n + 3\)なら\(O(log n)\)です。
これは\(n=10^{20}\)のような大きい数字を\(T(n) = 5n^3 + 2n^2 + 4n + 2\)に入れた時、\(5*10^{60}\)と\(2*10^{40}\)では数の差が大きく、後者は十分に無視できる小さな数になるためです。
商品価格\(1000000000000000001\)円と\(1000000000000000000\)円では、多くの人が同じ値段と認識するのと同じ理屈です。
大抵はここ(Rustドキュメント)のように参考にするアルゴリズムは漸近計算量で書かれています。
従って、プログラマ目線では「漸近計算量は増加率」であると覚え、\(O(n^3)\)より\(O(n)\)の方が増加率が低いから計算量は少なく、計算機的に「早く計算を処理できる」という感覚を身に付ければ良いと考えています。
問題に対するアプローチ方法
漸近計算量から解きたい問題を２つのグループに分けることが出来ます。
アルゴリズム\(A\)の計算量\(T_A\), アルゴリズム\(B\)の計算量\(T_B\)が
\begin{equation}
T_A = O(nlog n), T_B = O(n!) \notag
\end{equation}
と表されているとします。
基本演算が\(10^{-8}\)秒で実行できる計算機で２つのアルゴリズムを１年かけて動かしたとすると、解ける問題サイズはアルゴリズム\(A\)では大体\(8*10^{13}\)、アルゴリズム\(B\)では大体\(17\)となります。
このようにかなり大きな差があり、アルゴリズム\(B\)は時間をかけたら問題を解くことが出来るというレベルではないことが分かると思います。
アルゴリズム\(A\)のような計算量で解ける問題を「優しい問題」と呼び、逆にアルゴリズム\(B\)のような計算量でしか現在解けない問題は「難しい問題」と呼びます。
難しい問題を何も考えず総当たりで処理させると端末に大きな負荷をかけることが起こるため、アルゴリズム選定の際には計算量も視野に入れることをオススメします。
並び替え問題
ここまでに紹介した２つの概念、「計算量」と「問題の分類法」を実際に使う例をひとつご紹介します。
アプリ開発をする上でまず使われないことがないsort関数についての知識を深めるためにも「アルゴリズム」という概念は非常に有効です。
sort関数内のアルゴリズムは「並び替え問題」を解く手段でもありますので、並び替え問題はどちらの問題に属するかチェックしてみましょう。
並び替え問題は分割統合・比較という観点からアプローチすると二分木から考えることが出来ます。
すなわち、木の深さ\(k\)とすると葉の数は\(n!\)必要となるため、
\begin{equation}
(n-1)! < 2^k < n!
\end{equation}
スターリングの公式 \( n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}\) から
\begin{equation}
\sqrt{2\pi(n-1)}\left(\frac{n-1}{e}\right)^{n-1} < 2^k < \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n} \notag
\end{equation}
更に対数を取り、対数の性質から式を整理すると
\begin{equation}
\frac{1}{2}log{2\pi(n-1)} + (n-1)log{\frac{n-1}{e}} < k < \frac{1}{2}log{2\pi n} + nlog{\frac{n}{e}} \notag \\
O(nlogn) < k < O(nlogn)
\end{equation}
挟み撃ちの原理から\(O(nlogn)\)であることが分かります。
\(O(nlogn)\)で解ける問題は優しい問題に属するため「並び替え問題」は優しい問題になることが分かりました。
実際にRustやPythonなどの組み込みソート関数のアルゴリズムはTimSortを使っていますが、漸近計算量ではマージソートなどの分割統治法に基づくアルゴリズムと同様の\(O(nlogn)\)です。
ただし、最悪計算量の観点から考察するとTimSortの方が優れていることが分かります。
並び替え問題は優しい問題に属することが分かりましたのでプログラミング時に神経質に考えなくても良さそうであるということが分かりました。
最後に
本編ではアルゴリズムの入口をご紹介しましたが、複雑であまり面白くないと感じた人もいると思います。
完全に理解するのがもちろん一番良いことですが、プログラマ的にはふんわり理解しているだけでも価値が高く、ライブラリの選定やビジネスロジックのコーディングなどで助けになってくれると思います。
次回以降は実際のコードを交えながら、もっと実用的なアルゴリズムや難しい問題に対するアプローチについてご紹介したいと思っています。
