を参照していく。
前回
3. アルゴリズムの威力
3.1 アルゴリズムと実装
「何らかの目的を達成するための一連の計算手続き」をアルゴリズムという。アルゴリズムは計算の方法を示したものであるから、実際に計算させるにはプログラムを書く必要がある。これをアルゴリズムの実装(implementation)という。
3.2 事例:最大公約数
アルゴリズムを検討すべく、簡単な例として2つの自然数の最大公約数を求めるアルゴリズムを考える。
3.2.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))
この方法の計算量を考える。入力サイズとして入力値のうち小さい方をとする。
まずをそれぞれで割った余りがか否かを比較する計算について、割り算1階を1ステップと捉え、最悪の場合の計算量を見積もる。
最悪の場合はが互いに素、すなわち最大公約数がの場合である。このとき両者を回ずつ割るのだから、計算ステップは全部で回繰り返される。したがってがこのアルゴリズムの計算量である。
3.2.2 素因数分解
素因数分解を用いて行う方法も考えられるが、実装が簡単でない。
より簡単なのはの互除法である。
入力:自然数
出力:最大公約数
手順:
- をで割った余りをとする
- ならばを出力して終了する
- として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)
の互除法の計算量を考える。の互除法では1階の計算ステップが終了すると、次のステップに贈られる数は最悪の場合でも処理前の数の約半分になる*1。
3.3 事例:ソート
まとまった複数個の数値や文字列を順番に並び替える作業をソートと呼ぶ。ここでは簡単なソートのアルゴリズムを扱う。
3.3.1 選択ソート
簡単なソート・アルゴリズムとして選択ソートがある。配列の要素から最も小さいものを探し出して、その要素を配列の前へ持って行くものである。なお文字列の場合、辞書順で前にあるものを値が小さいと読み替える。
選択ソートの計算量を見積もる。入力のサイズは配列の長さとする。最悪の場合、このとき回目のループでは配列の全要素を走査するため、配列サイズと同じ回の計算が必要になる。それがに対して行われるから、全ステップ数は
である。したがってこのアルゴリズムの計算量は漸近記法でである。
入力:長さの配列
出力:ソートされた配列
手順:
- とする
- ならば終了
- 番号のうち最も小さい要素の番号をとする
- 3. で値が見つかったらとする
- として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)
ただしの内蔵関数による計算時間とシンプルな選択アルゴリズムによる計算時間には雲泥の差がある。とはいえでは組込関数は言語で予めコンパイルしたライブラリを参照して非常に高速で計算できることや、組込関数自体がアルゴリズム以外にもさまざまな工夫を内蔵していることなどが理由にある。
*1:処理すべきデータサイズが計算の各ステップで半分になると計算時間がになる。