10. ソートと計算量¶
今回は、ソートアルゴリズムを題材にして、アルゴリズム選択を考えてみます。
10.1. ソートとは？¶
ソート(sort, 整列) とは、順番をそろえて並び替える操作です。 ランキングや大学入試の合格者判定など、ソートは日常のあらゆる場面で活用されているアルゴリズムと言えます。
例えば、 次のような数列を昇順にソートすると:
ソートの順序
日常よく用いる「小さい順」と呼ばず、英語圏の「値が大きくなっていく様子」から昇順と呼 びます。
昇順ソート (ascending sort): \(x < y\) の順序で並べる
降順ソート (descending sort): \(x > y\) の順序で並べる
10.1.1. ソートライブラリ¶
Python は、リストLに対してソートを行う手段を2つ提供しています。
メソッド: リスト L を書き換えてソートする
L.sort()
組込み関数: リスト L を書き換えず、ソートされた新しいリストを返す
L2 = sorted(L)
ソートは、数値だけでなく、\(x < y\) が定義されている集まり、つまり全順序集合 (total ordered set)に対して行うことができます。Python では、文字列もタプルも比較演算子で比較できるため、リストの要素が全て比較できるときはソート可能です。
[ ]:
"A" < "B" # 文字列の比較
[ ]:
(1, 1) < (1, 2) # タプルの比較
日常の Python プログラミングでは、このようなソート・ライブラリを活用すれば充分です。
例題（ソート）
A さん、B さん、C さん、D さん、E さんの成績データが次のとおり与えられています。 成績の良い順に並べて表示するプログラムを書いてください。
S=[
('A', 75), ('B', 66), ('C', 75), ('D', 95), ('E', 83)
]
そのまま、S をソートすると名前順で並べらられるので、(75, ’A’) の順でペアを作り直して、ソートします。
[ ]:
S=[
('A', 75), ('B', 66), ('C', 75), ('D', 95), ('E', 83)
]
I = []
for name , score in S:
I.append((score, name))
I.sort() #ソートする
I.reverse() #逆順に
for score , name in I:
print(name , score)
このようにデータ構造の方を工夫すると、ソートライブラリで活用して解くことができます。
授業でアルゴリズムを学ぶと、アルゴリズムは自分で実装した方がいいと勘違いして、そのまま社会人になったりします。「車輪を再発明しない」は、「ライブラリを使いましょう」という格言です。ただし、学習者の間は、車輪を再発明してみないとわからないこともあります。
10.1.2. 準備: スワップ操作¶
ソートアルゴリズムでは、共通する操作としてスワップ (swap) が登場します。
スワップ
2 つの変数の値を入れ替える操作
Python スワップは、次の2通りの方法で行えます。
一般的な方法: 一時変数(temp)を用います
temp = x
x=y
y = temp
多重代入を用いる:
x, y = y, x
Python は、多重代入が使えるので、本講義では多重代入を用います。ただし、多重代入が使えないプログラミング言語もあるの で、一時変数を用いる方法も覚えておきましょう。
例題（リストを逆順にする）
スワップを用いて、リストを逆順に変換してみよう。
BEFORE
[0,1,2,3,4,5,6,7,8,9]
AFTER
[9,8,7,6,5,4,3,2,1,0]
[1]:
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(len(a)//2):
a[i], a[-(1+i)] = a[-(1+i)], a[i]
print(a)
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
10.2. ソートアルゴリズム¶
ソート・アルゴリズムは、ソートを実現するための手順です。ソートは、コンピュータ科学の題材として研究が行われ、様々な種類のアルゴリズムが考案されてきました。
本講義で扱うアルゴリム
選択ソート
バブルソート
クイックソート
マージソート
10.2.1. 選択ソート¶
選択ソート (selection sort) は、配列 a の中から一番小さな要素を探し、それを先頭の要素とスワッ プすることでソートします。もっとも人間の思考に近いソートアルゴリズムと言えます。
最も小さいソートを先頭にもってくることができたら、先頭をひとつ進め、同じ要領で繰 り返していきます。次は、まず start 以降のリスト a の要素から最小となる位置を探す関数 find_min_index(a, start) を定義しています。
[2]:
def find_min_index(a, start):
mini = start
for i in range(start+1, len(a)):
if a[i] < a[mini]:
mini = i
return mini
def select_sort(a):
for i in range(len(a)-1):
mini = find_min_index(a, i)
a[i], a[mini] = a[mini], a[i]
print(f'@{i}', a) #デバッグ用の途中状態の表示
[4]:
a = [5, 3, 1, 9, 8, 0, 4, 2, 7, 6]
select_sort(a)
print(a)
@0 [0, 3, 1, 9, 8, 5, 4, 2, 7, 6]
@1 [0, 1, 3, 9, 8, 5, 4, 2, 7, 6]
@2 [0, 1, 2, 9, 8, 5, 4, 3, 7, 6]
@3 [0, 1, 2, 3, 8, 5, 4, 9, 7, 6]
@4 [0, 1, 2, 3, 4, 5, 8, 9, 7, 6]
@5 [0, 1, 2, 3, 4, 5, 8, 9, 7, 6]
@6 [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
@7 [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
@8 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
10.2.2. バブルソート¶
バブルソート (bubble sort) は、もっとも実装が簡単(と言われている)ソートアルゴリズムです。
アルゴリズム * 隣り合った 2 つの要素 a[i] と a[i+1] を比較して、a[i] > a[i+1] なら両者をスワップする * 以上をスワップする必要がなくなるまで繰り返す
まず、一巡スワップさせてみましょう。
[5]:
def bubble_sort(a):
for i in range(len(a)-1):
if a[i] > a[i+1]:
a[i], a[i+1] = a[i+1], a[i]
print(f'@{i}', a)
[6]:
a = [5, 3, 1, 9, 8, 0, 4, 2, 7, 6]
bubble_sort(a)
print(a)
@0 [3, 5, 1, 9, 8, 0, 4, 2, 7, 6]
@1 [3, 1, 5, 9, 8, 0, 4, 2, 7, 6]
@3 [3, 1, 5, 8, 9, 0, 4, 2, 7, 6]
@4 [3, 1, 5, 8, 0, 9, 4, 2, 7, 6]
@5 [3, 1, 5, 8, 0, 4, 9, 2, 7, 6]
@6 [3, 1, 5, 8, 0, 4, 2, 9, 7, 6]
@7 [3, 1, 5, 8, 0, 4, 2, 7, 9, 6]
@8 [3, 1, 5, 8, 0, 4, 2, 7, 6, 9]
[3, 1, 5, 8, 0, 4, 2, 7, 6, 9]
まだ、リストのソートは完了していません。ソートが完了するまで、bubble_sort(n) のループを 繰り返すことになります。
考えてみよう
何回、ループを繰り返せばよいでしょうか?
リスト a の中で一番大きな値 (上の例では 9) に注目してみてください。リスト a を先頭から最後 まで a[i] > a[i+1] のとき、スワップ操作をすると、最終的に、必ず一番大きな値が最後尾にきます。
バブルソートの由来
大きな値が最後尾にくる様子が、バブル(泡)が浮き上がってくるのに似ているため
バブルソートの名前とともに、「先頭から最後尾まで1回隣り合う要素を比較してスワップすると、 最後尾は最大値になる」と覚えておきましょう。こう覚えておくと、ループはトータルで何回まわすべきかわかります。
[7]:
def bubble_sort(a):
for j in range(1, len(a)):
for i in range(len(a)-j):
if a[i] > a[i+1]:
a[i], a[i+1] = a[i+1], a[i]
print(f'@{j}', a)
[8]:
a = [5, 3, 1, 9, 8, 0, 4, 2, 7, 6]
bubble_sort(a)
print(a)
@1 [3, 1, 5, 8, 0, 4, 2, 7, 6, 9]
@2 [1, 3, 5, 0, 4, 2, 7, 6, 8, 9]
@3 [1, 3, 0, 4, 2, 5, 6, 7, 8, 9]
@4 [1, 0, 3, 2, 4, 5, 6, 7, 8, 9]
@5 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
@6 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
@7 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
@8 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
@9 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
10.3. クイックソート¶
クイックソート(quick sort)は、1960 年、Antony Hoare が考案した高速かつエレガントなアルゴリズムです。 ソートアルゴリズムの代名詞になっています。
手順 * 適当な数 (ピボット (pivot) と呼ぶ) を選択する * ピボットより小さい要素の集合、大きい要素の集合に分割する * 2 分割された各々の配列を、それぞれ分割できなくなるまで繰り返す
アルゴリズムと言えば..
クイックソートというくらい頻出。原理は絶対に理解して覚えておこう！！
10.3.1. メモリ効率を気にしない実装法¶
クイックソートは、メモリ効率を気にしなければ、実装はそれほど難しくありません。 ピボットでリストをフィルタして、再帰的に分割してゆきます。
[10]:
def quick_sort(a):
if len(a)>1:
# 先頭と最後尾の平均をpivot にする
pivot = (a[0] + a[-1]) / 2
# pivot より大小で二つにわける
b = [x for x in a if x <= pivot]
c = [x for x in a if x > pivot]
print(a, f'={pivot}=>', b, c) # 動 作 確 認 用
# 分割したリストをそれぞれ再帰的にソート
return quick_sort(b) + quick_sort(c)
return a
[12]:
a = [5, 3, 1, 9, 8, 0, 4, 2, 7, 6]
a = quick_sort(a)
print(a)
[5, 3, 1, 9, 8, 0, 4, 2, 7, 6] =5.5=> [5, 3, 1, 0, 4, 2] [9, 8, 7, 6]
[5, 3, 1, 0, 4, 2] =3.5=> [3, 1, 0, 2] [5, 4]
[3, 1, 0, 2] =2.5=> [1, 0, 2] [3]
[1, 0, 2] =1.5=> [1, 0] [2]
[1, 0] =0.5=> [0] [1]
[5, 4] =4.5=> [4] [5]
[9, 8, 7, 6] =7.5=> [7, 6] [9, 8]
[7, 6] =6.5=> [6] [7]
[9, 8] =8.5=> [8] [9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
クイックソートが長らくソートアルゴリズムの代名詞とされてきたのは、単に高速なだけでなく、メモリ効率も優れていたからです。(昔のコンピュータはメモリが高価でした。)
メモリ効率も気にして書いた例です。
[13]:
def quick_sort(a, start , end):
if start < end:
left , right = start , end -1
pivot = (a[start] + a[right]) // 2
while True:
# a[left] >= pivot となる位置を検索
while a[left] < pivot:
left += 1
# a[right] <= pivot となる位置を検索
while pivot < a[right]:
right -= 1
if left >= right:
break
a[left], a[right] = a[right], a[left]
left += 1
right -= 1
# 分割した左を再帰的にソート
quick_sort(a, start , left)
# 分割した右を再帰的にソート
quick_sort(a, right+1, end)
[14]:
a = [5, 3, 1, 9, 8, 0, 4, 2, 7, 6]
quick_sort(a, 0, len(a))
print(a)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
最初のクイックソートは、分割するときに、新しくリストを2つ作っています。少なくとも、この段階でメモリは2倍必要になります。一方、あとのクイックソートは、リスト上の先端 (start) と終端 (end) の位置をもって、分割したとき新しいリストを作りません。その代わり、リストの両端 (left, right) から比較して、( left > right) になったとき分割しています。
なお、クイックソートはかなり難しい実装に分類されます。すんなり書ける人はそんなにいません。 本講義のノートのソースコードも何度も直していますし、まだバグがあるかもしれません。
10.4. アルゴリズム選択¶
ソートアルゴリズムは、同じ問題に対して異なる手順の解法が複数あることを示しています。
すると、「どのアルゴリズムを選んだいいのだろうか?」と考える必要が生じます。
アルゴリズムの評価基準は、アルゴリズムを選択する上でヒントとなります。
アルゴリズムの評価基準
正当性: 正しさの証明があるか
効率: ステップ数，計算量と複雑さ (complexity)，平均ケースと最悪ケース
単純さ，わかりやすさ，プログラムの簡単さ
健全性，完全性，誤差の少なさ
安定性
計算量と複雑さは、アルゴリズムの性能を評価する重要な指標となります。 しかし、性能だけが全てではありません。実装のしやすさも実は重要です。 シンプルなアルゴリズムがバグも少なく、実装しやすいので好まれます。
また、時代とともにアルゴリズムのトレンドが変わることもあります。昔は、ソートアルゴリズムといえば、ほぼクイックソートでした。しかし、最近はメモリの価格が大幅に下がったため、マージソートの方が望ましいアルゴリズムとされることが増えています。
10.4.1. 計算量の見積もり¶
前回、学んだソートアルゴリズムを使って、時間計算量の見積もりをみていきましょう。
ループを見る¶
時間計算量は、入力サイズ \(N\) に依存して繰り返しの回数が決まるループに着目します。
バブルソートでは、長さ \(N\) のリストを \(N\) 回繰り返す2重ループを用いて比較しています。 ループ が 2 重なので、時間計算量は \(O(N^2)\) となります。(外側のループは \(N − 1\) 回などと細かいことを考える必要はありません。)
データ分割に着目¶
入力データを分割する処理があるときは、後述する「分割統治法」の可能性があります。
例えば、クリックソートでは、N 回繰り返すループをまわす度に、入力データを(平均して)\(N/2\) と半分に分割していきます。この場合は、分割する回数は \(O(\log{N})\) となります。最終的には、 \(O(N \log{N})\)となります。
10.4.2. 最悪ケース計算量と平均ケース計算量¶
クイックソートの計算量は、注意が必要です。クイックソートの計算量は、原理的には\(O(N \log{N})\)となりますが、データを分割する方法に依存します。つまり、理想的には\(N\)個のデータが\(N/2, N/2\)に分割されることが望ましいですが、最悪の場合\(N-1, 1\)に分割されることもあります。このような分割が重なると、クイックソートの計算量は\(O(N^2)\)となります。このような場合の計算量を、文字通り、最悪ケース計算量といいます。極めて特殊なケースを仮定しない場合の計算量を平均ケース計算量と呼びます。
10.4.3. お気楽なマージソート¶
次は、効率を気にせずにアルゴリズム通りに、お気楽に書かれたマージソートの実装です。
[1]:
def merge_sort(a):
if len(a) <= 1:
return a
sep = len(a) // 2
b = merge_sort(a[:sep])
c = merge_sort(a[sep:])
a = []
while len(b) > 0 and len(c) > 0:
# b, c の先頭をみて
b0 = b[0]
c0 = c[0]
# 小さい方を追加する
if b0 < c0:
a.append(b0)
b.pop(0)
else:
a.append(c0)
c.pop(0)
a.extend(b)
a.extend(c)
return a
a = [5, 3, 1, 9, 8, 0, 4, 2, 7, 6]
merge_sort(a)
[1]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Let’s try
ソースコードを読んで、マージソートの原理を理解しよう。 さらに、コードを分析して、平均ケース計算量と最悪ケース計算量を求めてみよう
ちなみに、マージソートの教科書的な計算量は、\(O(N \log{N})\)です。しかし、上のお気楽なマージソートは少しヤバいところがあります。多分、\(O(N^2 \log{N})\)です。どうしてなのか、考えてみましょう。
10.4.4. 帰着¶
最後に、同等な計算量のアルゴリズムに帰着して考える方法をみてみましょう。
例題（中央値）
大きさ N の数列 a の中央値を求める計算量は?
中央値とは、順に並んでいるときのちょうど中央の値です。 数列 a の中央値は、a がソートされているのなら a[len(a)//2] となります。
しかし、数列 a が常にソートされていると仮定できないので、まずソートしなければなりません。 したがって、中央値を求めるアルゴリズムは、一般にソートアルゴリズムの計算量\(O(N \log{N})\)に帰着されます。
ちょっと疑問
本当にソートは、\(O(N \log{N})\)より、効率のよいアルゴリズムはないのか?
アルゴリズム論の本質的な問いですが、「もっと計算量の優れたアルゴリズムはない」ことは証明できません。
なお、中央値は、ソートを用いず、「\(n\) 個の要素をもつ集合の \(i\) 番目に小さい要素を計算量 \(O(n)\) で 計算するアルゴリズム」に帰着させれば、線形最悪時間で解くこともできるようです。
10.5. 分割統治法¶
計算量は、入力データのサイズ \(N\) に依存することがわかってきた思います。効率のよいアルゴリズ ムのコツは、入力データのサイズを分割して、\(N\)の要因を下げることです。このようなアルゴリズム・デザインの戦略を分割統治法 (divide-and-conquer) と呼びます。
分割倒置法の例
二分探索 二分法
クイックソート
マージソート
分割統治法のコツは、並列アルゴリズムのように単に入力データを分割するだけでなく、分割を再帰的に繰り返し、N/2, N/4, N/8 と細かくしていくことです。
例題（分割統治法）
\(3^{16}\)を分割統治法で効率よく計算してみよう。
まずは、紙とえんぴつを用意して解いてみましょう。
普通に計算すると、3を15回、掛け算することになります。
半分に分割します。
さらに分割していきます。
この考え方は、実は繰り返し二乗法です。
繰り返し二乗法