アルゴリズムを評価する計算量について

アルゴリズムを評価できるように、計算量(ランダウの記号)について調べた。

アルゴリズムは、実行に必要な資源の量で評価される。

資源とは、実行にかかる時間と使用するメモリ領域を指す。一般的には資源が少ない方が評価が高いが、計算量を優先すると可読性が下がり、保守がしづらくなる。ライブラリや言語などの閲覧頻度が低く、処理速度を求められるものは計算量を優先する。アルゴリズムの用途によって決める。

計算量を優先したアルゴリズムの例(消費メモリは少ないが、理解に時間がかかる)

計算量の種類

計算量は2種類ある。

時間計算量(Time Complexity)は、アルゴリズムが処理を終えるまでに実行する命令数(ステップ数)を表す。

領域(空間)計算量(Space Complexity)は、アルゴリズムが処理を終えるのに必要なメモリ領域を表す。

計算量の評価にはランダウの記号(Landau Symbol)を用いる。アルゴリズムの入力値のサイズが変化したとき、使われる資源の変化率を表す。

ランダウの記号は $O$ (オー)記法(Big $O$ Notation)とも呼ばれる。記号 $O$ はOrder(程度)の $O$ 。

一般的に $O$ 記法は、関数の変数(この場合は入力値のサイズ)が無限に近づいたときの資源の増加率を提示する。そのため、ハードウェア依存の定数項と増加率が低い低次数の項は考慮しない。

例) あるアルゴリズムが、与えられたサイズ $n$ のデータを処理をするのにかかる時間が次の多項式で表現できる場合、計算量は $O(n^2)$ である。

$f(n) = 4n^2 - 2n + 2$

$f(n) = O(n^2)$

やってみよう

実際にアルゴリズムの計算量を考えてみよう。

isUniqueChar(String word)は、ある文字列がすべてユニークであるかどうか(重複する文字がないか)を判定する。

時間計算量を考える時は、ステップ数をカウントする。そこから入力サイズ(引数wordの大きさ)に関係のあるfor文の実行回数のみ取り出す。wordの文字数分、for文が回るので時間計算量は $O(n)$ となる。

空間計算量を考えるときは入力値の大きさは考慮しない。アルゴリズムの評価をするために、アルゴリズムが問題を解決するために必要なメモリ領域のみ考える。

isUniqueChar(String word)ではboolean[] char_set と int i とint len と int val がメモリを使用する、これらはマシンの性能や言語の型の設計に依存するため、入力値の大きさにかかわらず一定である。

よって空間計算量は $O(1)$ となる。

実際にかかる時間を想像してみよう

CPUは私たちが書いたアルゴリズムをどのくらいのスピードで処理するのだろうか。

代表的なCPUは1つの命令を4つのステージに分けて実行する。1ステージを実行するのに1クロックかかるので、1命令を実行するのに4クロックかかる。

(1)　命令フェッチ　；　命令コードをメモリから読み込む

(2)　命令デコード　；　読み込んだ命令コードを解析し、実行の準備を行う

(3)　実行　　　　　；　CPU内部の演算ユニットで命令を実行する

(4)　ライトバック　；　実行結果をレジスタやメモリに書き込む

iPhone7が使用しているCPUを例にアルゴリズムが処理を終えるまでにかかる時間を想像してみる。iPhone7のCPUはARMアーキテクチャのApple A10を使用している。

ARMはRISC(Reduced Instruction Set Computer)プロセッサの１つである。RISCは1つの命令を実行するステージ数とパイプラインの数を揃えることで、見かけ上1クロックあたり1命令を実行する。

f:id:bambinya:20170126171057p:plain

上の画像は、1つの命令を { IF = 命令フェッチ、ID = 命令デコード、EX = 実行、MEM = メモリアクセス、WB = レジスタ・ライトバック } の5つのステージに分けて、5つのパイプラインで5つの命令を同時実行する。実質1クロックで1命令完了することになる。

1命令をいくつのステージで実行するかは、CPUによって異なる。(Apple A10のステージ数とパイプライン数は調べたけど分からなかった)

Apple A10の動作周波数は最大で2.34GHzなので、1秒間に2,340,000,000回のクロックを刻む。ARMアーキテクチャは1クロックあたり1命令を実行するため、1秒間に2,340,000,000命令実行する。またコア数は4つなので、理論上は1秒間に9.36G回の命令を実行する。

ものすごくシンプルに考えると10,000ステップのアルゴリズムをCPUが処理する時間は、 $1000 \times \frac{10000}{2.34 \times 10^9} = 0.0042..$ ミリ秒となる。

ただし、実際プログラムの実行には、CPUがメインメモリ、ブリッジ、ハードディスク等と情報のやり取りを行う時間(データバス)、キャッシュメモリにキャッシュがあるかどうか、命令セットの最適化、などが時間に関係し、もっと時間がかかる。この辺りは知識が全くないので、いつか検証したい。

参考

f:id:bambinya:20170126213048g:plain