プログラム作成時のアルゴリズムと計算量について考えてみた

2020年3月29日

アルゴリズムとは

問題を解く手順のことです。

簡単に言うと、はじめにAして、そのつぎBして・・・という手順のこと。

一般的には解き方の数だけアルゴリズムが存在します。

また、問題がはやく解けるアルゴリズム = 良いアルゴリズムとされています。

なぜなら、処理速度(作業の効率化)はコストに直結するからです。

時間はお金です「Time is money(タイム イズ マネー)」

データ量が多ければそれだけ計算に時間がかかります。

良いアルゴリズムなら大幅に計算時間が短縮できます。

アルゴリズムの評価

アルゴリズムの良し悪しを判断する一番簡単な方法は、プログラムを作って実行することです。

でもこの方法には問題があります。

問題点1:使う言語によって結果が異なる

C/C++だとメッチャはやい!

Pythonだとメッチャおそい!

なんてことがあります。

問題点2:開発環境によって結果が異なる

最新のCPUと大量のメモリを積んだパソコンではバリバリ動いた。

旧型のCPUで少量のメモリしか積んでないパソコンでは死ぬほど遅い。

どんな環境でもその環境において最速であることが望ましいです。

言語や環境に依らない評価方法は何か?

それは「計算量」という考え方です。

計算量とは

計算の複雑さを表現する言葉です。

英語で「Computational Complexity」といいます。

計算量にはいくつかの種類があります。

  • 時間計算量
  • 空間計算量
  • 通信計算量
  • 回路計算量

一般に「計算量」と言えば、時間計算量を意味します。

以下、特に大事な時間計算量と通信計算量について述べます。

時間計算量とは

アルゴリズムの処理にどれくらいの時間がかかるかを示す量で、CPUの処理速度によって決まります。

空間計算量とは

記憶容量(メモリ)をどれくらい必要とするかを示す量で、メモリの量によって決まります。

時間計算量の調べ方

CPUが命令を実行した回数を調べることで求められますが、正確な回数は数えられません。

そこで、処理を終了するまでに命令の基本単位を何回実行したかを調べて計算時間とします。

例えば、Python で以下のプログラムを実行した場合を考えます。

# test_1.py

for i in range(10):
    i += 1
    print("答え:", i)
>
答え: 1
答え: 2
答え: 3
答え: 4
答え: 5
答え: 6
答え: 7
答え: 8
答え: 9
答え: 10

for ループを1回まわすたびにprint 文で計算結果を1回出力します。

これを10回繰り返します。

print 文を1回実行するのにΑ時間かかるとします。

10回繰り返した時の時間は、(A×10)時間です。

次に、for ループ内に if 文による条件判定がある場合を考えます。

# test_2.py

for i in range(10):
    i += 1
    if i % 2 == 0:
        print("偶数:", i)
    else:
        print("奇数:", i)
>
奇数: 1
偶数: 2
奇数: 3
偶数: 4
奇数: 5
偶数: 6
奇数: 7
偶数: 8
奇数: 9
偶数: 10

先ほどと同じように、print 文を1回実行するのにA時間かかります。

if 文で条件判定するのにB時間かかるとします。

全体の処理時間は、((A+B)×10)時間です。

さらに、for の2重ループの場合を考えます。

# test_3.py

for i in range(10):
    for j in range(10):
        k = i + j
        print("答え:" + str(i) + "+" + str(j) + "=", k)
>
答え:0+0= 0
答え:0+1= 1
答え:0+2= 2
答え:0+3= 3
答え:0+4= 4
答え:0+5= 5
・・・
答え:9+5= 14
答え:9+6= 15
答え:9+7= 16
答え:9+8= 17
答え:9+9= 18

print 文を1回実行するのにA時間かかります。

内側のforループが10回、外側のforループが10回まわります。

全体の処理時間は、(A×10×10)時間です。

forループが重なるほど、また、実行回数(今の例では10)が大きくほど、処理時間が長くなることが分かります。

計算量の比較

プログラムを実行した際、各命令に以下の処理時間がかかるとします。

  • print 文の実行 :A時間
  • if 文の実行   :B時間
  • for ループの実行:n時間

AやBは1つの命令の実行に掛かる時間はデータ量とは関係ありません。

データ量が大きくなった際に一番影響を受けるのはnです。

for ループを重ねるとnは乗数(nを何回掛け合わせるか)で効いてきます。

処理時間を短くするためには、如何にnを小さくするかが重要です。

なお、計算量を記述する記号として「O」(オー)という記号(ランダウの記号)があります。

これは、全体の計算量に大きな影響がない部分(A、B)を無視してO(n)のように記述するものです。

以下にオーダー比較表を示します。

処理時間オーダー
短いO(1)print 文実行
O(n)for ループ1重test_1.py
test_2.py
O(n^2)for ループ2重test_3.py
長いO(n^3)for ループ3重

この表から for ループはなるべく重ねない方が良いことが分かります。

処理時間を短くするテクニックがあります。

それは、リスト内包表記を使う方法です。

リスト内包表記について

繰り返し処理には forループを使うのが一般的ですが、Python にはリスト内包表記という便利なものがあります。

例1:リスト内容表記を使った場合

print([i+j for i in range(10) for j in range(10)])

例2:for ループを使った場合

for i in range(10):
    for j in range(10):
        print(i+j)

例1と例2は等価です。

リスト内包表記の最大のメリットは処理時間の短縮です。

処理速度を比較してみます。

import time

t0 = time.time()
print([i+j for i in range(10) for j in range(10)])
t1 = time.time() - t0
print("時間:", float(t1))

>
時間: 0.000997066497802734
import time

t0 = time.time()
for i in range(10):
    for j in range(10):
        k = i + j
        print("答え:" + str(i) + "+" + str(j) + "=", k)
t1 = time.time() - t0
print("時間:", float(t1))

>
時間: 0.016955137252807617

処理時間の比較結果

例1:0.000997066497802734

例2:0.016955137252807617

約17倍も処理時間が短くなる!

リスト内包表記は慣れが必要ですが、かなりおすすめです。

まとめ

  • アルゴリズムとは問題を解く手順のこと
  • アルゴリズムを評価するには「計算量」を考える。
  • 一般に「計算量」と言えば、時間計算量を意味する。
  • 時間計算量の調査は、命令の基本単位を何回実行したかで調べる。
  • 計算量は「O」(オー:ランダウの記号)を使って表す。
  • for ループを重ねるほど処理時間が長くなる。
  • 処理時間を短くしたいならリスト内包表記を使うべし!

参考にした書籍