はじめに
アルゴリズムと言えば、どうしても堅苦しいイメージが。
Pythonでアルゴリズムを楽しむ、が本連載の趣旨です。
正解を見つける、がゴールでなく、
考える力を身につける、をゴールとしたいです。
- 3つ以上解き方を見つける
- そこからベスト解を選ぶ
改めて、アルゴリズムとは
アルゴリズムの定義
JIS X 0001:1994による定義
- 問題を解くためのもので
- 明確に定義され
- 順序付けられた有限個の規則からなる集合
アルゴリズム良し悪しの評価基準
- 機能性
- 目的に対する適合性、正確さ
- 使用性
- 理解しやすさ、目的/意図のわかりやすさ
- 効率性
- 実行性能、時間効率/資源効率
- 保守性
- 仕様変更と追加など保守のしやすさ
- 移植性
- 別環境への移植のしやすさ
アルゴリズムの分類
- ソート
- 文字列
- 探索
- マージ
- 数値
- グラフ
- 計算幾何
- 組合せ
- 機械学習
- 暗号化
- データ圧縮
- 構文解析
改めて、Pythonとは
WikipediaからPythonとは
- インタープリタ型の高水準汎用プログラミング言語
- 明確で論理的なコーディング支援が目的で、コードの可読性を重視
- 動的型付けで、値やオブジェクトの型安全性を実行時に検証
- ガベージコレクションされている
- 複数のプログラミングパラダイムをサポート
- 構造化(特に手続き型)
- オブジェクト指向
- 関数型プログラミング
Pythonの特徴から、アルゴリズムとの相性よさそうです。
では、早速Pythonを駆使し、アルゴリズムのモヤモヤを解消してみましょう。
進め方
以下の3ステップ構成で、各種アルゴリズムを解いてみます。
-
問題の提示 -
解決案を見つける -
コードを書く
初回ですので、ソートアルゴリズムを例に
問題
以下8つの数字を昇順で整列せよ。
8 4 3 7 6 5 2 1
解決案
バブルソートを使用し解決してみます。
-
Wikipediaからバブルソート(bubble sort)
- 隣り合う要素の大小を比較しながら整列させるソートアルゴリズム
- 最悪時間計算量はO(n2)と遅いので普段は使いません
-
ソートの手順
- ①1番目と2番目を比較し、順番が逆であれば入れ換える
- ②次に2番目と3番目を比較し、入れ換える
- ③最後まで行うと、最後の数だけが最大の数として確定する
- 確定していない部分に対し、上記①から③を繰り返す。
-
アルゴリズムの動作例
※ 結果確定したものは太字で表す
8 4 3 7 6 5 2 1 (初期データ)
4 3 7 6 5 2 1 8 (1回目の外側ループ終了時 交換回数:7)
3 4 6 5 2 1 7 8 (2回目の外側ループ終了時 交換回数:5)
3 4 5 2 1 6 7 8 (3回目の外側ループ終了時 交換回数:3)
3 4 2 1 5 6 7 8 (4回目の外側ループ終了時 交換回数:2)
3 2 1 4 5 6 7 8 (5回目の外側ループ終了時 交換回数:2)
2 1 3 4 5 6 7 8 (6回目の外側ループ終了時 交換回数:2)
1 2 3 4 5 6 7 8 (7回目の外側ループ終了時 交換回数:1)
コード
bubble_sort.py
import matplotlib.pyplot as plt
import matplotlib.animation as ani
import matplotlib.cm as cm
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def bubble_sort(arr):
if len(arr) == 1:
return
yield arr
for i in range(len(arr) - 1):
for j in range(len(arr) - 1 - i):
yield arr
if arr[j] > arr[j + 1]:
swap(arr, j, j + 1)
yield arr
def plot(arr, rec, epochs):
for rec, val in zip(rec, arr):
rec.set_height(val)
rec.set_color(cm.tab20(val % 15))
text.set_text("count: {}".format(epochs[0]))
epochs[0] += 1
if __name__ == '__main__':
title = "bubble sort"
arr = [8, 4, 3, 7, 6, 5, 2, 1]
nums = len(arr)
algo = bubble_sort(arr)
fig, ax = plt.subplots()
ax.set_title(title)
bar = ax.bar(range(len(arr)), arr, align='edge')
ax.set_xlim(0, nums)
ax.set_ylim(0, int(nums * 1.1))
text = ax.text(0.01, 0.9, "", transform=ax.transAxes)
epochs = [0]
anim = ani.FuncAnimation(fig, func=plot, fargs=(bar, epochs), frames=algo, interval=1000, repeat=False)
mng = plt.get_current_fig_manager()
mng.full_screen_toggle()
plt.show()
- matplotlibがインストールされていない場合
$ pip install matplotlib
- 実行
$ python bubble_sort.py
- 結果
- ソート過程が可視化されます
おわりに
サンプルとしてバブルソートを解いてみました。
次回から、Pythonを使って各種アルゴリズムを解いていきます。
お楽しみに。