2017-01-27

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

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

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

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

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

ある文字列が、すべてユニークである(重複する文字がない)かどうかを判定するアルゴリズ ...

計算量の種類

計算量は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

パソコンの基礎知識 > CPU > キャッシュメモリの仕組み

RISC - Wikipedia

命令パイプライン - Wikipedia

Q&Aで学ぶマイコン講座（1）：CISCとRISC、何が違う？ (2/3) - EDN Japan

2017-01-24

ニュートン法を使って、平方根を求めるアルゴリズムを書いてみよう

Goのプレイグラウンドで遊んでたら、フロー制御の章でニュートン法を使って平方根を求めましょう( A Tour of Go )と言われたので調べた。

ニュートン法とは？

ニュートン・ラフソン法(Newton-Raphson method)ともいう。

与えられた関数 $f$ について $f(x)=0$ になる $x$ の近似解を求める方法である。

例えば、 $x^2-2=0$ の解である $\sqrt{2}$ は無理数(1.41421356...)である。有効桁数があるコンピューターは、この値を誤差なく持つことは不可能であるが、ニュートン法を用いて計算を繰り返すことで、型が持つ有効桁数の範囲で解に近い値を求めることができる。

やってみよう

Goの問題は、引数として与えられる数( $k$ とする)の平方根( $x$ とする)を求めるアルゴリズム sqrt(k float64)(x float64) を書くというものである。ニュートン法を使って解いてみよう。

引数として与えられた $k$ の平方根 $x$ を求めることから、

$k = x^2$ 　より

$x^2 - k = 0$ という方程式を解けば平方根が求まる。

$k = 2$ のときを例に解法を説明する。以下は $x^2 - 2$ の曲線とその接線のグラフである。接線は解 $x$ ( $= \sqrt{ 2 }$ )よりも大きな値を適当にとり( $\displaystyle x_0$ とする)、引いた。

f:id:bambinya:20170124225900p:plain

上の図から分かるように、接線の $x$ 切片 $\displaystyle x_1$ は、 ${\displaystyle x_0} {\displaystyle \gt} {\displaystyle x_1} {\displaystyle \gt} x(= \sqrt{ 2 } )$ という値をとる。この性質を使い、次は $\displaystyle x_1$ を元に曲線の接線を引き、 $x$ 切片を求める。これを繰り返すことで、真の解に近づけていく。反復回数が多いほど精度が上がっていく。グラフでは下記のようになる。

f:id:bambinya:20170124231411p:plain

この反復処理は、 $\displaystyle x_1$ を $\displaystyle x_0$ で表す漸化式を求めるとfor文で書ける。

$\displaystyle x_1$ を $\displaystyle x_0$ で表す式を求める。

接線の傾きは微分で求められる。

$f(x) = x^2 - k$

$f'(x) = 2x$

$\displaystyle x_0$ の時の接線の傾きは $2\displaystyle x_0$ であり、これはyの変化量をxの変化量で割ったものと等しい。下記を参照のこと。

f:id:bambinya:20170124223222p:plain

式にすると、

$2\displaystyle x_0 = \frac{\displaystyle x_0^2 - k} {\displaystyle x_0 - \displaystyle x_1}$

両辺に $x_0 - \displaystyle x_1$ をかけて整理すると、以下の式が得られる。

$\displaystyle x_1 = \frac{\displaystyle x_0^2 + k}{2\displaystyle x_0}$

( $\displaystyle x_1$ を $\displaystyle x_0$ で表す漸化式。 $k$ is given.)

この漸化式を用いて、Goでfor文を書くと次のようになる。

関数とループを使った簡単な練習として、ニュートン法を使った平方根の計算を実装してみましょう。( ...

おしまい。

2016-10-22

Rubyのオブジェクトモデルを紹介しました。

speakerdeck.com

2016-07-10

zshellを導入したときのメモ

ログインシェルをbashから、zshellに変更した。

brewでzshをインストール。

$ brew install zsh
... 🍺 ...

$ which zsh
/usr/local/bin/zsh

システムで有効なログインシェルの一覧を、/etc/shellsで見ることができる。
ログインシェルとは、ユーザーがシェルにログインしたときに、最初に起動するシェルのこと。
Mac OS Xだと、bash以外に csh ksh sh tcsh zsh が入っている。

$ cat /etc/shells
# List of acceptable shells for chpass(1).
# Ftpd will not allow users to connect who are not using
# one of these shells.

/bin/bash
/bin/csh
/bin/ksh
/bin/sh
/bin/tcsh
/bin/zsh

システムにプリインストールされていたzshと、brewでインストールしたzshのバージョンを比較する。
brewからインストールしたzshの方が新しい。

$ /bin/zsh --version
zsh 5.0.5 (x86_64-apple-darwin14.0)

$ /usr/local/bin/zsh --version
zsh 5.2 (x86_64-apple-darwin14.5.0)

/etc/shellsに、/usr/local/bin/zshを追記する。

$ sudo bash -c 'echo /usr/local/bin/zsh >> /etc/shells'
Password:

catで追加されたことを確認し、change shellコマンドのchshを実行する。

$ cat /etc/shells
# List of acceptable shells for chpass(1).
# Ftpd will not allow users to connect who are not using
# one of these shells.

/bin/bash
/bin/csh
/bin/ksh
/bin/sh
/bin/tcsh
/bin/zsh
/usr/local/bin/zsh

$ chsh -s /usr/local/bin/zsh
Password for Bambi:

設定は、~/.zshrcに書く。なければ作成する。
~/.bashrcと~/.bash_profileから、エイリアスと環境変数を移せば、完了です〜 😋