Lesson 13
計算量
Lesson 13
Chapter 1
オーダー記法
機械学習を含む情報系の分野では、よく計算量という概念が登場します。 これは何かというと、あるプログラムを実行したときに行われる処理の回数を指します。 処理の回数が増えるほど実行時間は増えることになるので、なるべく計算量の少ないプログラムを書くというのが重要なことになってきます。
しかし、実際には処理にかかる時間が処理ごとに異なるので、実際の処理の回数を考えるのはあまり意味がありません。 そこで、「プログラムへの入力のサイズが大きくなるにつれてどれだけ処理の回数が増えるのか」という指標を計算量として用いることが多いです。 さらに、その計算量を分かりやすく表現する（比較などの観点から）ために用いられるのがオーダー記法と呼ばれるものです。 直観的には、関数$f(n)$（$n$は自然数）に対し、$n$を限りなく大きくしたときの$f(n)$中の支配的な項のみを取り出し、さらに係数を無視したもの$g(n)$を$f(n)$のオーダーといい、 $O(g(n))$と書きます。これがオーダー記法です。
いくつか例を見てみましょう。 関数$f(n)=2n^3+4n^2$のオーダーを求めてみます。 $n$を限りなく大きくしたときには、$2n^3 >> 4n^2$となるので、$f(n)$内では$2n^3$の項が支配的です。 またその係数$2$はオーダーを考える際には無視します。よって$f(n)=O(n^3)$ということになります。
次に関数$g(n)=4n+3\log n$を考えてみます。$n$を限りなく大きくすると、$4n >> 3\log n$になります。 再び係数を無視することで、$g(n)=O(n)$ということになります。
計算量の分野では、オーダーを考える対象となる関数が複数の入力を受け取り、さらにそれらのサイズが独立に変化することがあります。 そのような場合、それぞれの入力サイズの変化に対する計算量の変化を表現する必要があります。 例えば2つの入力を持つ関数$h(n, k)=3n^2+n+4k\log n$を考えてみます。 $n$を限りなく大きくしたとき、$3n^2 >> n$となるのは確かですが、$3n^2 >> 4k\log n$になるとは限りません。 なぜなら入力によっては$k > n^2$になるかもしれないからです。 したがって、支配的な項としては$3n^2$と$4k\log n$の2つがあることになり、$h(k, n)=O(n^2+k\log n)$になります。
計算量は情報科学において非常に重要な概念であり、それを理解してオーダー記法によって表現することが必要になってきます。 この Lesson を通してしっかり身に着けていきましょう。
オーダー記法の定義
数学的には、関数$f(x)$に対し、以下のことが成り立つとき、$f(x)=O(g(x))$と表します。
ある$x_0$と定数$M$が存在して、すべての$x$に対し$x>x_0\Rightarrow |f(x)| \leq M|g(x)|$
また$x$を限りなく大きくするときだけでなく、ある点に限りなく近づけるときの関数の挙動を調べる際にもオーダー記法は用いられます。
例えばテーラー展開の剰余項の評価に用いられます。
時間計算量と空間計算量
実は計算量と呼ばれるものは2つあり、それぞれ時間計算量、空間計算量と呼ばれます。
時間計算量はこれまで述べてきたような、入力のサイズが大きくなるにつれてどれだけ処理の回数が増えるかを表すものです。
一方、空間計算量は、入力のサイズが大きくなるにつれてどれだけ使用する記憶領域が増えるかを表します。
時間計算量と空間計算量はいずれも小さくすることが望ましいですが、トレードオフの関係にあることもあります。
この教材では、単に計算量といったら時間計算量のことを指すこととします。
Lesson 13
Chapter 2
計算量の求め方
ここでは、いくつかの Python プログラムの計算量を実際に求めることで、計算量をどのようにして求めればよいかを理解しましょう。
Python
n = int(input())
sum_n = 0
for i in range(n):
sum_n += i
print(sum_n)このプログラムは、nを入力として受け取り、0からn-1までの整数の合計を求め、その結果を最後に出力しています。
for文によるn回の繰り返しが生じているので、このプログラムの計算量は$O(n)$ということになります。
なお、for文の内部に処理が追加された次のプログラムも、計算量は$O(n)$のままです。
Python
n = int(input())
sum_n = 0
for i in range(n):
sum_n += i
print(sum_n)
print(sum_n)なぜならオーダーを考える際には定数係数は無視してしまうからです。
またfor文の外側のprint(sum)などについても、
オーダーには寄与しないということに注意しましょう。
続いては以下のプログラムを見てみましょう（これ以降プログラム例には特に意味のあるものを使いませんが、計算量を求めるための簡単なサンプルと捉えてください）。
Python
n = int(input())
for i in range(n):
for j in range(n-i):
print(i * j)for文が2重になっていることに注意しましょう。
外側のfor文はn回繰り返すのに対し、内側のfor文は(n-i)回繰り返します。
では結局のところ、最も内側の処理であるprint(i * j)は何回実行されるのでしょうか。
それは以下のようになります。
iが0からn-1まで変化しながら(n-i)回の繰り返しが行われることに注意すると、上記のようになります。 ではオーダーはというと、$\dfrac{1}{2}n(n+1)$はnの2次式なので、$O(n^2)$ということになります。
3つ目の例は下のプログラムです。
Python
n = int(input())
while n > 0:
n = n // 2
print(n)これは、入力nを2で割っていき（ここでは整数の割り算を行っています）、nが正の間（つまりnが0になるまで）nを出力するような、
while文を用いたプログラムです。
では計算量はどのようになるでしょうか。
1回の繰り返しでnは半分になるので、もちろん$O(n)$ではありません。
繰り返しごとに$\dfrac{n}{2}$、$\dfrac{n}{2^2}$、$\dfrac{n}{2^3}$...のようにnが減少していくことを考えると、
$n \geq 2^{k-1}$となるような最大のkが繰り返しの数になることがわかります。
$n \geq 2^{k-1}$を変形すると$\log_2 n - 1 \geq k$になるので、計算量は（定数の差や定数係数を無視して）$O(\log n)$ということになります。
なお計算量を考える際、対数は自然対数のこともあれば2進対数のこともありますが、$\log n = \dfrac{\log_2 n}{\log_2 e}$であることから、定数係数を無視して
考えるオーダーの世界ではどちらを用いても問題ありません。
入力が2つあるような場合も見てみましょう。次のプログラムです。
Python
n = int(input())
k = int(input())
m = n
while m > 0:
for i in range(k):
print(m + k)
m = m // 2
for j in range(n):
print(i)このプログラムは、while文とfor文が重ねられた部分と、
単純なfor文が使われた部分とに分けられています。
このようなときは部分ごとに計算量を求め、それらの和を全体のプログラムの計算量を求めればよいです。
まず1つ目の部分ですが、$m$のみに着目するとこれは1つ前の例と同じく$O(\log m)$になることがわかります。
しかし実際には、while文の内側でfor文によるk回の繰り返しが行われています。
このようにループが入れ子になっているときは、掛け算によって計算量を求めることができます。つまり$O(k\log m)$です。
m=nとしていることに注意すると、$O(k\log n)$となります。
そして2つ目の部分についてですが、これは単純なn回の繰り返しなので、計算量は$O(n)$です。
したがってこのプログラム全体の計算量は$O(k\log n + n)$ということになります。
では最後に、やや特殊な例を紹介しておきます。
Python
n = int(input())
for i in range(10):
print(n)これは入力nの値を10回繰り返して出力するプログラムです。 計算量は「入力のサイズが大きくなるにつれて処理の回数がどのように増えるか」を表すためのものであることを思い出してください。 このプログラムは入力nの値が何であろうと（エラーが起こらない限り）処理の回数は変わらないことがわかるでしょうか。 したがってこのプログラムの計算量は入力nに依存しない定数ということになります。 このようなときは計算量は$O(1)$と表すことが多いので、覚えておきましょう。
Lesson 13
Chapter 3
計算量の大小
計算量を求めることは、さまざまなプログラム（あるいはアルゴリズム）について計算量を比較してどれを使うのが良いかを考える上で重要なことです。 ここでは、頻繁に登場する計算量（オーダー）について、それらの大小を述べておきます。
次の表は、nを大きくしていくにつれてさまざまなnの式がどのように大きくなるかを表したものです。 $\log n$など整数にならないものは小数第1位で四捨五入してあり、また値が大きくなりすぎるものはスペースの都合上、そして計算量の都合上省略しています。
| $n$ | $\log n$ | $\sqrt{n}$ | $n^2$ | $n^3$ | $2^n$ | $n!$ |
|---|---|---|---|---|---|---|
| 2 | 2 | 1 | 4 | 8 | 4 | 2 |
| 5 | 2 | 2 | 25 | 125 | 32 | 120 |
| 10 | 2 | 3 | 100 | 1000 | 1024 | 3628800 |
| 20 | 3 | 4 | 400 | 8000 | 1048576 | 2432902008176640000 |
| 30 | 3 | 5 | 900 | 27000 | 1073741824 | |
| 50 | 4 | 7 | 2500 | 125000 | 1125899906842624 | |
| 100 | 5 | 10 | 10000 | 1000000 | ||
| 1000 | 7 | 32 | 1000000 | 1000000000 | ||
| 100000 | 12 | 316 | 10000000000 | |||
| 10000000 | 16 | 3162 | 100000000000000 |
これを見ると、いかに$\log n$がオーダーとして小さいか、そしていかに$2^n$や$n!$がオーダーとして大きいかがわかるでしょう。 以下に、$n$を十分大きくするときのいくつかの頻繁に登場する$n$の式の大小を提示しておきます。 \[ \log n \lt \cdots \lt n^{\frac{1}{3} } \lt \sqrt{n} \lt n \lt n\log n \lt n^2 \lt n^3 \lt \cdots 2^n \lt 3^n \lt \cdots \lt n! \] 結果的には同じことをするプログラムでも、計算量の観点からは全く異なっていることもあり、プログラムに用いるアルゴリズムの選択が 最終的なパフォーマンスに大きな影響を与えることがあります。 計算量を元にしていくつかのプログラムを比較する際の参考にしてみてください。
Lesson 13
Chapter 4
Pythonを高速化するテクニック
Pythonは処理速度が遅い言語であることを理解する
機械学習や深層学習を行う際に用いるプログラミング言語としては、現在多くの場面において Python が選ばれています。 理由としては、機械学習やデータサイエンスの分野で便利なライブラリやパッケージが豊富にあることが大きいです。
そんな Python の欠点として、動作が遅いというのがあります。 実際にどのくらい遅いかというのは、プログラムがどのようなことを実行するのかによりますが、一般的に、 他のさまざまな代表的なプログラミング言語（C、C++、JavaScript、Javaなど）よりも動作が遅いとされています。 その理由はいくつか考えられ、例えば Python がインタプリタ言語であることや、動的型付け言語であることなどです。 なおインタプリタ言語とはプログラム中の命令を逐次（1行ずつ）実行していくようなプログラミング言語のことで、 その対照的な存在としてコンパイラ言語があります。 また動的型付け言語とは、簡単に言えば変数の型と呼ばれるものをプログラムの実行時に決めるようなプログラミング言語で、 実行前に型を決める静的型付け言語とは対極にあります。
とにかく、Python を使う場合には 「Python は処理速度が遅い」ということを理解しておく必要があります。 その上で、どのようにすれば高速に動作させることができるのか次の項で学びましょう。
高速化テクニック
Python の処理速度を高速化するのにはいくつかの方法があります。
まずは、Python に限った話ではないですが、計算量が少なくなるようなプログラムを書くという手法です。 例えばChapter2で登場した次のコードを見てみましょう。
Python
n = int(input())
sum_n = 0
for i in range(n):
sum_n += i
print(sum_n)このプログラムの計算量は$O(n)$です。 しかし、このプログラムは結果的に0からn-1までの整数の総和を出力するだけなので、これは \[ 0 + 1 + \cdots + (n-2) + (n-1) = \dfrac{1}{2}n(n-1) \] という式を用いれば以下のようなプログラムで総和を出力できます。
Python
n = int(input())
sum_n = 0.5 * n * (n - 1)
print(sum_n)このプログラムの計算量は$O(1)$であり、かなり高速化できています。
このように計算量が少なくなるようなプログラムを書くには、ある程度知識が必要になります（上の例では先ほどの総和を求める式が知識にあたります）。 特に必要なのはアルゴリズムの知識です。 世の中にはさまざまな問題を解くためのさまざまなアルゴリズムがあり、それらをここに列挙するのは難しいですが、 それぞれに時間計算量や空間計算量だけでなく実装コストなどに関するメリット・デメリットがあります。 高速化という観点からは、時間計算量の少ないアルゴリズムを選び、それを用いたプログラムを書くことが重要になってきます。
続いては、ライブラリを利用するという手法を説明します。 Python の処理速度を高速化するためのライブラリの代表例として、NumPy があります。 NumPy は数値計算用のライブラリです（Lesson 14でも再び紹介します）。 例えば行列を2次元のリストとして表現したものの掛け算を計算する際に、次のようなプログラムを書いたとします。
Python
n = int(input())
a = [[i + j for i in range(n)] for j in range(n)]
b = [[i - j for i in range(n)] for j in range(n)]
c = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
c[i][j] = a[i][k] + b[k][j]
print(c)2次元のリストaおよびbを行列とみなして
それらの積を2次元のリストcとして表現し出力しています。
Python ではfor文などによる繰り返しが特に遅いとされます。
よってこのプログラムのように、3重になったループを書くのはできる限り避けたいです。
一方 NumPy のnp.dotを使えば、以下のように簡単に行列の積を計算でき、しかも高速に動作します。
Python
import numpy as np
n = int(input())
a = np.array([[i + j for i in range(n)] for j in range(n)])
b = np.array([[i - j for in range(n)] for j in range(n)])
c = np.dot(a, b)
print(c)NumPy のようなライブラリを使えそうなところは惜しみなく使うことで処理を高速化しましょう。
Python の高速化には他にもさまざまな手法があります。 例えば、 Python に似たような構文を使って高速に動くC言語のコードを生成したり、C言語で書かれた関数を Python から呼び出したりするための Cython や、 JIT（Just-In-Time）コンパイラによってプログラムの実行を効率化できる PyPy、 あるいはキャッシュを利用するための functools モジュールの lru_cache など、 多岐にわたります。
機械学習や深層学習で Python を利用する際には、これらの高速化手法があることも頭に入れておくと良いでしょう。
