年末なので、世の中を良くすることについて考える。
現代の日本で 「社会を変える」「世の中を良くする」などと言うと、 頭のおかしい人と思われるのがオチであるが…
関数 perm(a, n) を、以下のように定義する:
a の左から n 要素を、1回ローテーションする:
perm(a, n-1) を呼び出す。
n == 0 のときは何もせず a の値を表示。
def perm(a, n):
if n == 0:
print(a)
return
else:
for i in range(n):
左から n 要素をローテーションする。
perm(a, n-1)
return
計算量の理論の応用例のひとつが、より効率のよい計算方法 (プログラム) の開発である。 ここでは簡単な例として、逐次探索 (線形探索) と二分探索をとりあげる。
0番目の要素からひとつひとつ調べていく、これが 逐次探索 (sequential search) である。
a = [5,9,4,0,7,3, ... ] # n個の要素 x = 1729 # 探す数 for i in range(n): if a[i] == x: print(f"found {i}")
上のコードの n に対する計算量はいくらか。Big-O 記法で答えよ。
逐次探索は、検索対象のリストが長くなればなるほど、 それに比例して実行時間も長くなる。リストの要素数が 1万倍になれば、 実行時間も1万倍になる (実際には、実行時間の期待値が 1万倍になる)。 そのため、逐次探索はときに線形探索 (linear search) とも呼ばれる。
いっぽうで、これとは別の計算方法である二分探索 (binary search) というものがある。 これは次のように動作する:
これは、(紙の) 辞書を引くときの動作に似ている。 ある単語を見つけるのに、辞書の先頭から 1ページずつ見ていく人はいない。 ほとんどの人は辞書の単語がすべてアルファベット順に並んでいることを利用して、 アタリをつけていくのだ。二分探索はこれを一般化したものである。
たとえば a = [0, 1, 3, 4, 8, 9, 13] というリストで、
x = 3 のケースを考えてみる。
まず、リスト a の中央の要素は 4 である。
この時点で、リスト a の右側の要素はすべて「捜査対象外」であるとわかる。 なぜなら、リスト a の要素は昇順に並んでいるからだ。 ついでに中央の要素も対象外となるので、捜査範囲は 3つの要素となる:
捜査対象をこの3要素に絞ったときの中央の値は 1 である。
xはこれより大きいので、捜査範囲はこれよりは右側
(しかし最初の中心よりは左側) にあることがわかる。
するともはや対象は 1つしか残っていない。
したがって、これが x だ、ということになる:
二分探索を使うと、(リストの要素があらかじめ昇順に並んでいなければならない、 という制限はあるものの) n個の要素のリストに対して 平均 log2(n) 回のくり返しで発見できることになる。 これは nの値が大きければ大きいほど、スピードアップにつながる。 たとえばリストの要素数が 1万倍になったとしても、 実行回数はたかだか 14回増えるだけである (214 = 16384)。
a = [0, 1, 3, 4, 8, 9, 13] の場合について
x = 13 のケースを考えてみよ。何回のくり返しで x を発見できるか?
a = [-6, 2, 5, 7, 10, 14, 25, 37, 63, 92, 108] の場合について
x = 2 および x = 63 のケースを考えてみよ。
何回のくり返しで x を発見できるか?
(範囲が偶数個のときは、どちらの値を中央としてもよい)
では、二分探索を実際に Python で実装することを考えてみる。 二分探索は、再帰的な関数として実装するとわかりやすい。
# a: 探索する対象のリスト。 # x: 見つける値。 # i0: 探索範囲の開始位置。 # i1: 探索範囲の終了位置。 def bsearch(a, x, i0, i1): #print(f"a={a}, x={x}, i0={i0}, i1={i1}") i = (i0+i1) // 2 if a[i] == x: print(f"found {i}") elif a[i] < x: bsearch(a, x, i+1, i1) else: # x < a[i] bsearch(a, x, i0, i) return # a の中から 13 を発見する。 a = [0, 1, 3, 4, 8, 9, 13] bsearch(a, 13, 0, len(a)) # a の中から 63 を発見する。 a = [-6, 2, 5, 7, 10, 14, 25, 37, 63, 92, 108] bsearch(a, 63, 0, len(a))
関数 bsearch() は、以下のように動作する。
まず開始位置 i0 と終了位置 i1 は、以下のように
リストの各要素と要素の間を指すことに決めておく。
最初は i0 = 0 および i1 = len(a) として呼び出す。
つまり、i0 から i1 で囲まれた要素の間に
値 x が存在すると仮定している。
次に i0 と i1 の中間位置 i を計算し、
その要素 a[i] と x の値を比較する。
同じであればここで探索は終了する。
i = (i0+i1) // 2
if a[i] == x:
print(f"found {i}")
リスト a の各要素は昇順に並んでおり、
しかもすでに a[i] == x でないことが判明している。
したがって、もし a[i] < x であれば、
探索範囲は i+1 〜 i1 までの間に狭めることができる。
これが次の i0 および i1 となる。
elif a[i] < x:
bsearch(a, x, i+1, i1)
一方、もし x < a[i] であれば、
探索範囲は i0 〜 i までの間に狭めることができる。
これが次の i0 および i1 となる。
else: # x < a[i]
bsearch(a, x, i0, i)
プログラムから明らかなように、二分探索は再帰的な処理である。
ある範囲における bsearch() は、
そのどちらかの半分に対して再帰的に bsearch() を呼び出す。
以後、これは範囲がただ 1つの要素に絞られるまで続く。
上のプログラム bsearch.py を実際に実行せよ。
print()関数のコメントをはずし、内部の動きを観察せよ。
さて、これまでリスト a の中には x が必ず含まれていると
仮定してきたが、x が含まれていなかったらどうなるだろうか?
実は探索範囲 i0 〜 i1 の間はだんだん縮まっていくので、
最後には i0 == i1 となる。こうなったら、
もはや間に要素はひとつもないので、x は存在しなかったということになる。
bsearch() の計算量
この関数 bsearch() の計算量を考える。
実際には、プログラムの動き方は入力によって変わるため、
厳密な計算量をいう場合には「最悪計算量」「平均計算量」などという用語を使う。
「最悪計算量」とは、文字どおりプログラムが
「もっとも運の悪い動き方をした場合」にかかる計算量のことである。
以後、この授業では計算量といえば最悪計算量のことをさす。
ここでの最悪計算量は、x が存在し、
それが最後に発見されると仮定した場合である。
関数 bsearch() が探索する範囲の大きさを
n = |i1 - i0| とすると、
n に対する計算量 Bn は以下のような漸化式で求められる:
⌊n/2⌋ は床関数をあらわす。 ここで f(p) = B2n とおくと、 f(p) = p であり、Bn は事実上 2n の 逆関数 log2(n) であるので、 このプログラムの最悪計算量は O(log(n)) であるということができる。
コンピュータサイエンスの中でもっとも重要な問題のひとつが
「このプログラムはいつか必ず停止するのか?」という問題である
(停止性問題)。幸運にも、
関数 bsearch() の場合は、
必ず停止することが証明できる。
def bsearch(a, x, i0, i1):
i = (i0+i1) // 2
...
elif a[i] < x:
bsearch(a, x, i+1, i1)
else: # x < a[i]
bsearch(a, x, i0, i)
具体的には、上の各ケースにおいて、探索範囲の大きさ (i1 - i0) が
つねに減少する (単調減少) であることを証明すればよい。
Python における (i0+i1) // 2 は床関数
⌊(i0+i1)/2⌋ であるので、以下が成り立つ:
i0 ≤ (i0+i1) // 2 = i < i1
したがって、以下のことがいえる:
a[i] < x の場合 …
i1 - (i+1) < (i1 - i0) であるので、
範囲は単調減少する。
x < a[i] の場合 …
i - i0 < (i1 - i0) であるので、
範囲は単調減少する。
これを繰り返していくと、最終的にこの関数は以下のどちらかの状態に到達する。
i0 == i1 となり、x が存在しないことがわかる。
a[i] == x となり、x が発見される。
bsearch() は、必ず停止する。
プログラムが停止するかどうかを判断するのは、実は非常に難しい。
たとえば以下の関数 col() は
何の変哲もない Python の関数である:
def col(n):
while 1 < n:
print(n)
if (n % 2) == 0: # n が偶数の場合
n = n // 2
else: # n が奇数の場合
n = n*3 + 1
return
col(10) や col(27) を実行してみるとよい。
この関数が、すべての正の整数 n に対して停止するかどうかは
数学の未解決問題とされている
(コラッツの問題)。
一般的には、プログラムの停止性問題は難しいのである。
二分探索では、リストのすべての要素はあらかじめ昇順に並んでいる必要があった。 ソーティング (sorting) あるいはソート (sort, 並べ替え) とは、 文字通りランダムに並んだ要素を昇順 (あるいは降順) に並べ替える 処理である。ソーティングは二分探索だけでなく多くのデータの集計処理で使われる、 コンピュータの基本的な処理のひとつである。
[5, 9, 4, 0, 7, 3, 1, 8]
[0, 1, 3, 4, 5, 7, 8, 9]
結論からいうと、ソーティング処理はけっこう複雑である。 要素が 10個程度のものであれば目視で容易に並べ替えが可能だが、 数万〜数億要素のデータを効率よくソートするために、 これまでいくつもの方式が提案されてきており、それぞれに一長一短がある。 本授業では中でもわかりやすい 2つの方法 (挿入法とマージソート) を紹介する。
挿入法のアイデアは単純で、これは人間が数字を並べ替えるときの方法に近い。 まずリストの最初から、隣り合った要素が昇順に並んでいるかどうかをチェックしていく。
昇順になっていない (a[i+1] < a[i] であるような)
箇所を見つけたら、その数字を適切な場所に挿入する。
すでに a[i] までの数列はソートされていると仮定しているので、
この数字は左側のどこかの位置に入るはずである。(これを p としよう)
挿入後、a[0] 〜 a[i] までの数列が昇順に並んでおり、
a[i+1] より右側の要素はまだ変化していない。
したがって i は次の値から続行する。
i がリストの終わりに到達するまでこれを続ければ、
すべての要素が正しく並んだことになる。
挿入法を使って、リスト [7, 3, 1, 8, 6, 2] を昇順にソートせよ。
i = 0 とする。)
a[i], a[i+1] があったら...
a[i+1] の要素が入る位置 p を見つける。
a[i+1] を削除し、位置 p に挿入する。
i を 1 増やす。
以上の方法をプログラムにすると、以下のようになる:
# リスト a の要素を破壊的にソートする。 def insort(a): for i in range(len(a)-1): # 隣り合った要素 a[i] と a[i+1] を比べる。 if a[i+1] < a[i]: # a[i+1] のほうが a[i] よりも小さい。 x = a[i+1] # したがって、x の値を、a[0]〜a[i-1] までのどこかに挿入する。return a = [5,9,4,0,7,3,1,8] insort(a) print(a)...
# 適切な位置 p を発見する。 # これは現在の i より左にある要素を見ていく。 p = i while (0 < p) and (x <= a[p-1]): p = p - 1 # この時点で a[p] = x となるべきであるから # a[p]〜a[i] の要素をひとつずつ右にずらす。 q = i while p <= q: a[q+1] = a[q] q = q - 1 # 最後に a[p] を x とする。 a[p] = x
上のプログラムを実行し、結果を確認せよ。
print() 関数を随所に入れ、何が起きているか観察せよ。
挿入法の最悪計算量は、たとえば [5,4,3,2,1,0] などのリストを
ソートしようとしたときを想定してみるとよい。これは以下のように考える:
一方、マージソートはまったく異なる方法で並べ替えをおこなう。
まず、すでにソートされている (昇順に並んでいる) 2つのリスト
p と q を一本の昇順な列に統合する関数
merge(p, q) を考える。
このような関数は以下のようにして作ることができる。
まず目印となる変数 i と j を用意し、
これを右へ右へと動かしていく。
p[i] の値と q[j] の値を比較し、
小さいほうを結果となるリストに足していけばよい。
def merge(p, q):
i = 0
j = 0
r = []
while i < len(p) and j < len(q):
# p[i] と q[j] を比較し、
# 小さいほうを r に加える。
# その後、i または j をひとつ進める。
...
return r
リスト p と q がともに n要素あったとすると、
関数 merge() 内のループ繰り返しはたかだか 2n回である。
つまり計算量は O(n) である。
merge() ができたら、それを使ってマージソートをおこなう。
これは再帰的なプログラムとして定義される。
merge() して一本に統一すればよい。
merge() され、
4要素ずつのソートされたリストとなる。
merge() され、マージソートが完成する。
以上の処理を実際の関数 mergesort() として実装すると、
おおむね以下のようになる。
(注意:
挿入法の関数 insort() は与えられたリストを破壊的に
変更してソートしたのに対して、mergesort() は
新しいリストを作成して返す、いわゆる「普通の関数」になっている。)
def mergesort(a):
n = len(a)
if n == 1:
# 長さ 1 のリストはすでにソートされている。
return a
else:
# 最初の半分を切り取ってソートする。
p = mergesort(a[:n//2])
# 残りの半分を切り取ってソートする。
q = mergesort(a[n//2:])
# 結果を統合し、一本のソートされたリストを返す。
return merge(p, q)
関数 mergesort() に与えられる要素の数は、
呼び出しごとに半分ずつになっていくため、もともとのリストの各要素に対して
mergesort() は約 O(log(n)) 回呼び出されることになる。
この中で O(n) の計算量をもつ関数 merge() を実行するので、
したがって、全体の計算量をあわせると O(n・log(n)) ということになる。
これは、挿入法の計算量よりもオーダーが少なく、n の値が大きいときに
より効率的であるといえる。
挿入法と違い、マージソートはどのようなリストに対しても同じ回数で処理するので
必ず O(n・log(n)) の時間がかかり、最悪計算量と平均計算量の差が存在しない。
いっぽう関数 merge() は毎回、新しいリストを作成しなければならないため、
これは n要素の入力に対して O(n) 要素分の追加メモリ容量を必要とする。
挿入法では、追加のメモリ容量は必要とされない。
まとめると、どちらの方式も一長一短があることがわかる:
ブレイクアウトルーム演習の方法:
bsearch.py における
bsearch() 関数は、x がリスト中に
含まれていない場合を想定していないため、以下のようなコードではエラーが発生する:
def bsearch(a, x, i0, i1):
...
# a の中から 5 を発見する。
a = [0, 1, 3, 4, 8, 9, 13]
bsearch(a, 5, 0, len(a))
要素が存在しない場合の説明を参考に、
bsearch() 関数に if 文を追加し、
要素が存在しなかった場合には
"not found" と表示して終了するようにせよ。
insort.py で、
リスト [5, 4, 3, 2, 1, 0] をソートしたときに、
内側の a[q+1] = a[q] は合計何回実行されるか?
これを数えるようにプログラムを改良し、その値を表示せよ。
$ python insort.py 15 [0, 1, 2, 3, 4, 5]
insort.py
以下は 3.1. で説明した挿入法のソートプログラムの再掲である:
# insort.py def insort(a): for i in range(len(a)-1): # 隣り合った要素 a[i] と a[i+1] を比べる。 if a[i+1] < a[i]: # a[i+1] のほうが a[i] よりも小さい。 x = a[i+1] # したがって、x の値を、a[0]〜a[i-1] までのどこかに挿入する。 # 適切な位置 p を発見する。 # これは現在の i より左にある要素を見ていく。 p = i while (0 < p) and (x <= a[p-1]): p = p - 1 # この時点で a[p] = x となるべきであるから # a[p]〜a[i] の要素をひとつずつ右にずらす。 q = i while p <= q: a[q+1] = a[q] q = q - 1 # 最後に a[p] を x とする。 a[p] = x return # コマンド引数をすべて整数のリストにする。 import sys a = [] for i in range(len(sys.argv)-1): v = int(sys.argv[i+1]) a = a + [v] # ソートを実行し、結果を表示する。 insort(a) print(a)
このプログラムには実は無駄な部分がある。途中に 2つの while文があるが、
本来、「適切な挿入位置 p の発見」と「要素をずらす処理」は、
ひとつの while文中で同時におこなうことができるはずである。
このプログラムを while文をひとつだけ使ったバージョンに
改良して提出せよ。(外側の for文はそのままでよい。)
ソートする数をコマンド引数から指定できるようにすること。
実行例:
$ python insort.py 5 9 4 0 7 3 [0, 3, 4, 5, 7, 9]
mergesort.py
授業中に説明したマージソートをおこなうプログラムを完成させ、提出せよ。
insort.py と同じく、このプログラムもリストの内容を
コマンド引数で指定できるようにすること。
さらに、各関数の適切な場所にコメントを入れ、
以下のことを説明すること。
merge(p, q) を書くとき、
リスト p と q が同じ長さとは限らないので注意すること
(例: [0,2,4] と [1]) など。
実行例:
$ python mergesort.py 5 9 4 0 7 3 1 8 6 2 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
提出するプログラムは以下のような構成になっていることが望ましい:
# mergesort.py import sys # merge(p, q): あらかじめソートされたリスト p と q をまとめる。 def merge(p, q): ... # mergesort(a): リスト a をマージソートしたものを返す。 def mergesort(a): ... # コマンド引数をすべてリストにする。 a = [] for i in range(len(sys.argv)-1): v = int(sys.argv[i+1]) a = a + [v] # ソートを実行し、結果を表示する。 print(mergesort(a))