「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。

MENU

Pythonで学ぶアルゴリズム(04/X)

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

を参照していく。

3. アルゴリズムの威力

3.1 アルゴリズムと実装

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

3.2 事例:最大公約数

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

3.2.1 素朴なアルゴリズム

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

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

  1. 変数xbを代入する
  2. a,bが両方ともxで割り切れたらxを出力して終了する
  3. 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
出力:最大公約数
手順:

  1. abで割った余りをrとする
  2. r=0ならばbを出力して終了する
  3. 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の配列
出力:ソートされた配列
手順:

  1. i=0とする
  2. i=nならば終了
  3. 番号i\lt j\leq nのうち最も小さい要素の番号をjとする
  4. 3. で値が見つかったらi,j=j,iとする
  5. 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}言語で予めコンパイルしたライブラリを参照して非常に高速で計算できることや、組込関数自体がアルゴリズム以外にもさまざまな工夫を内蔵していることなどが理由にある。

3.4 アルゴリズムと実装

 アルゴリズムが正しく実行され、必ず停止するか否かを確認することは重要である。ここで注意すべきなのは、アルゴリズムには実行のための前提条件が含まれがちなことである。
 最初に触れた最大公約数のアルゴリズムであれば、関数の引数に2つの自然数が入力されることが前提視されている。

*1:処理すべきデータサイズが計算の各ステップで半分になると計算時間が\log nになる。

プライバシーポリシー お問い合わせ