Pythonで学ぶアルゴリズム（04/18） - 「大人の教養・知識・気付き」を伸ばすブログ

　アルゴリズムを学ぶのにPythonの学習も兼ねて

Ｐｙｔｈｏｎで学ぶアルゴリズムとデータ構造 (データサイエンス入門シリーズ)

作者:辻真吾
講談社

Amazon

を参照していく。

前回

power-of-awareness.com

前回
3.　アルゴリズムの威力
次回

3.　アルゴリズムの威力

3.1　アルゴリズムと実装

　「何らかの目的を達成するための一連の計算手続き」をアルゴリズムという。アルゴリズムは計算の方法を示したものであるから、実際に計算させるにはプログラムを書く必要がある。これをアルゴリズムの実装(implementation)という。

3.2　事例：最大公約数

　アルゴリズムを検討すべく、簡単な例として2つの自然数の最大公約数を求めるアルゴリズムを考える。

3.2.1　素朴なアルゴリズム

　まずは素朴なアルゴリズムを考える。

入力：自然数 $a,b$
出力：最大公約数
手順：

変数 $x$ に $b$ を代入する

$a,b$ が両方とも $x$ で割り切れたら $x$ を出力して終了する

$x=x-1$ とし2.へ戻る

import math

# まずはパッケージを利用
print(math.gcd(18915,14938))

# 自前で実装
def simple_gcd(a, b):
    if a< b:
        a,b = b,a
    x = b
    while True:
        if a % x == 0 and b % x ==0:
            return x
        x -= 1
print(simple_gcd(18915,14938))

　この方法の計算量を考える。入力サイズとして入力値のうち小さい方を $n$ とする。
まず $a,b$ をそれぞれ $x$ で割った余りが $0$ か否かを比較する計算について、割り算1階を1ステップと捉え、最悪の場合の計算量を見積もる。
　最悪の場合は $a,b$ が互いに素、すなわち最大公約数が $1$ の場合である。このとき両者を $n$ 回ずつ割るのだから、計算ステップは全部で $2n$ 回繰り返される。したがって $\mathcal{O}(n)$ がこのアルゴリズムの計算量である。

3.2.2　素因数分解

　素因数分解を用いて行う方法も考えられるが、実装が簡単でない。
　より簡単なのは $\mathrm{Euclid}$ の互除法である。

入力：自然数 $a,b$
出力：最大公約数
手順：

$a$ を $b$ で割った余りを $r$ とする

$r=0$ ならば $b$ を出力して終了する

$a=b,b=r$ として1.に戻る

　これまでのアルゴリズムも含めたすべてをまとめて書くと以下のとおりである。

import math
import time

a, b = 18915,14938

# まずはパッケージを利用
start = time.time()
print(math.gcd(a, b))
print(time.time() - start) # 出力までの時間計測

# 自前で実装
def simple_gcd(a, b):
    if a< b:
        a,b = b,a
    x = b
    while True:
        if a % x == 0 and b % x ==0:
            return x
        x -= 1

start = time.time()
print(simple_gcd(a, b))
print(time.time() - start)

## Euclidの互除法
# 愚直に書く場合
def euclidian_algo(a,b):
    while True:
        r = a % b
        if r==0:
            return b
        a,b = b,r

# 再帰を用いる
def euclidian_recursion(a,b):
    r = a % b  
    if r==0:
        return b
    return euclidian_recursion(b,r)

start = time.time()
print(euclidian_algo(a, b))
print(time.time() - start)

start = time.time()
print(euclidian_recursion(a, b))
print(time.time() - start)

$\mathrm{Euclid}$ の互除法の計算量を考える。 $\mathrm{Euclid}$ の互除法では1階の計算ステップが終了すると、次のステップに贈られる数は最悪の場合でも処理前の数の約半分になる*1。

3.3　事例：ソート

　まとまった複数個の数値や文字列を順番に並び替える作業をソートと呼ぶ。ここでは簡単なソートのアルゴリズムを扱う。

3.3.1　選択ソート

　簡単なソート・アルゴリズムとして選択ソートがある。配列の要素から最も小さいものを探し出して、その要素を配列の前へ持って行くものである。なお文字列の場合、辞書順で前にあるものを値が小さいと読み替える。

　選択ソートの計算量を見積もる。入力のサイズは配列の長さ $n$ とする。最悪の場合、このとき $i$ 回目のループでは配列の全要素を走査するため、配列サイズと同じ $n-i+1$ 回の計算が必要になる。それが $i=1,2,\cdots,n$ に対して行われるから、全ステップ数は

$\begin{aligned} n+(n-1)+(n-2)+\cdots+2+1=\displaystyle{\frac{n(n+1)}{2}} \end{aligned}$

である。したがってこのアルゴリズムの計算量は漸近記法で $\mathcal{O}\left(n^2\right)$ である。

入力：長さ $n$ の配列
出力：ソートされた配列
手順：

$i=0$ とする

$i=n$ ならば終了

番号 $i\lt j\leq n$ のうち最も小さい要素の番号を $j$ とする

3. で値が見つかったら $i,j=j,i$ とする

$i=i+1$ として2.に戻る

import random
import time

random.seed(1)

my_array = [random.randint(0,99) for i in range(10000)]
my_array

# 内蔵関数
start = time.time()
sorted(my_array)
print(time.time() - start)

my_array.sort()

start = time.time()
my_array
print(time.time() - start)

# 選択ソート
def selection_sort(array):
    x = array.copy()
    n = len(x)
    for i in range(n):
        min_idx = 1
        for j in range(i,n):
            if x[j] < x[min_idx]:
                min_idx = j
        x[i],  x[min_idx] = x[min_idx], x[i]
    return x

random.shuffle(my_array) # 並びをシャッフルする

start = time.time()
selection_sort(my_array)
print(time.time() - start)

　ただし $\mathrm{Python}$ の内蔵関数による計算時間とシンプルな選択アルゴリズムによる計算時間には雲泥の差がある。とはいえ $\mathrm{Python}$ では組込関数は $\mathrm{C}$ 言語で予めコンパイルしたライブラリを参照して非常に高速で計算できることや、組込関数自体がアルゴリズム以外にもさまざまな工夫を内蔵していることなどが理由にある。