【Python/CS】Pythonで理解するアルゴリズムとデータ構造
はじめに
本記事では、コンピュータサイエンスを学ぶ方、学びたい方を対象に、アルゴリズムとデータ構造の基本概念から応用までを丁寧に解説します。CS専攻でなくても理解できるよう、基本的な概念の紹介から始め、各種アルゴリズムとデータ構造の実装例をPythonで紹介します。
筆者のスペック
- 2024秋 音大進学したのちプログラミングの道に興味が湧きエンジニアリングを学び始める。
- 同年 11月 長期インターンに合格して大学を休学し、csを本格的に学ぶ、実務経験の開始。
- 現在 大学を中退し、エンジニアとしてのキャリアを開始。
このような感じで元々は全く関係のない西洋音楽専攻でした。
アルゴリズムが音楽理論と同じで楽しくハマってしまったので大体3ヶ月程度で学んだ知識を自分のアップデートとこれから学びたい人に向けてのエールを込めて執筆します。
目次
-
アルゴリズムの基本概念
- 時間計算法と空間計算法
- Big-O記法の説明
-
データ構造とアルゴリズムの関係
- リスト、スタック、キュー、ハッシュテーブルの説明
-
基本的なアルゴリズムと実装例
- 線形探索と二分探索
- ソートアルゴリズム
- バブルソート、クイックソートの比較
- 再帰とループの説明
-
応用アルゴリズムのセクション
- 幅優先探索(BFS)と深さ優先探索(DFS)
- ダイクストラ法(最短経路)
- 応用アルゴリズム問題: 例とPythonコード
- まとめと全体図
アルゴリズムの基本概念
時間計算法と空間計算法
アルゴリズムは、問題を解くための手順や手続きです。アルゴリズムの効率は、以下の二つの観点で評価されます。
- 時間計算法: アルゴリズムが問題を解くのに必要な時間を分析します。入力サイズが大きくなるにつれてアルゴリズムの実行時間がどのように増加するかを考えます。
- 空間計算法: 問題を解くために必要なメモリ量を分析します。アルゴリズムが使用するメモリの量が入力サイズに対してどう変化するかを評価します。
Big-O記法の説明
Big-O記法は、入力サイズに対するアルゴリズムの計算量(時間または空間)を表現するための記法です。具体例を挙げると、
- O(1): 定数時間。入力サイズに関係なく、実行時間が一定。
- O(n): 線形時間。入力サイズnに比例して実行時間が増加。
- O(log n): 対数時間。入力サイズが倍になるごとに実行時間が一定の量だけ増加。
- O(n log n): 線形対数時間。ソートアルゴリズムの多くがこれに該当。
Big-O記法を用いることで、アルゴリズムの効率を大まかに比較することができます。
データ構造とアルゴリズムの関係
アルゴリズムはデータ構造に依存します。適切なデータ構造を選択することが、アルゴリズムの効率性に大きく影響します。以下に、基本的なデータ構造を紹介します。
リスト
リストは、順序付きのデータの集まりです。Pythonの組み込み型であるlist
がこれに該当します。リストは、インデックスによるアクセスが可能で、多くの場合配列として実装されています。
スタック
スタックは、LIFO(Last In First Out)の構造です。最後に追加された要素が最初に取り出されます。Pythonではリストを利用してスタックを実装できます。
stack = []
stack.append(1) # push
stack.append(2)
stack.append(3)
print(stack.pop()) # pop -> 3
キュー
キューは、FIFO(First In First Out)の構造です。最初に追加された要素が最初に取り出されます。Pythonのcollections.deque
を使うと効率的に実装できます。
from collections import deque
queue = deque()
queue.append(1) # enqueue
queue.append(2)
queue.append(3)
print(queue.popleft()) # dequeue -> 1
ハッシュテーブル
ハッシュテーブルは、キーと値のペアを格納し、平均して高速な探索・挿入・削除を可能にするデータ構造です。Pythonのdict
がこれに該当します。
hash_table = {}
hash_table["key"] = "value"
print(hash_table.get("key")) # -> "value"
基本的なアルゴリズムと実装例
線形探索と二分探索
リスト内に特定の値が存在するか調べる基本的なアルゴリズムには、線形探索と二分探索があります。
- 線形探索: リストの最初から最後まで、順番に探します。時間計算量はO(n)です。
def linear_search(lst, target):
for item in lst:
if item == target:
return True
return False
# 使用例
numbers = [1, 3, 5, 7, 9]
print(linear_search(numbers, 5)) # -> True
print(linear_search(numbers, 2)) # -> False
- 二分探索: リストがソートされている場合、中間の要素と比較を繰り返し、探索範囲を半分に絞っていく方法です。時間計算量はO(log n)。
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return True
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return False
# 使用例
numbers = [1, 3, 5, 7, 9]
print(binary_search(numbers, 5)) # -> True
print(binary_search(numbers, 2)) # -> False
ソートアルゴリズム
リストをソートするアルゴリズムには様々な種類があります。ここでは、バブルソートとクイックソートを比較します。
バブルソート vs クイックソート
特徴 | バブルソート | クイックソート |
---|---|---|
平均時間計算量 | O(n²) | O(n log n) |
最悪時間計算量 | O(n²) | O(n²)(最悪の場合) |
メモリ使用量 | O(1) | O(log n)(再帰呼び出しによる) |
安定性 | 安定 | 不安定 (実装次第) |
バブルソートのPython実装
def bubble_sort(lst):
n = len(lst)
for i in range(n):
# 末尾から探索範囲を狭めていく
for j in range(0, n - i - 1):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
# 使用例
numbers = [5, 2, 9, 1, 5, 6]
print(bubble_sort(numbers)) # -> [1, 2, 5, 5, 6, 9]
再帰とループの説明
多くのアルゴリズムは、再帰(自分自身を呼び出す)やループ(反復処理)を使って実装されます。これらは同じ問題を異なる方法で解く手法です。
フィボナッチ数列の再帰実装
def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
# 使用例
print(fibonacci_recursive(10)) # -> 55
フィボナッチ数列のループ実装
def fibonacci_loop(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
# 使用例
print(fibonacci_loop(10)) # -> 55
応用アルゴリズムのセクション
幅優先探索(BFS)と深さ優先探索(DFS)
グラフ探索アルゴリズムとして、幅優先探索(BFS)と深さ優先探索(DFS)があります。これらの違いを以下の表にまとめます。
特徴 | 幅優先探索 (BFS) | 深さ優先探索 (DFS) |
---|---|---|
アプローチ | レベルごとに探索 | 一方の枝を可能な限り探索 |
使用するデータ構造 | キュー | スタック(または再帰呼び出し) |
最短経路の保証 | 有り(無重みグラフの場合) | 保証されない |
メモリ使用量 | 高くなる可能性がある(幅が広い場合) | 再帰深度に依存(深い探索でスタックオーバーフローの可能性) |
ダイクストラ法(最短経路)
ダイクストラ法は、重み付きグラフにおいて、ある始点から全ての頂点への最短経路を求めるアルゴリズムです。以下は、簡単なネットワーク図を用いたダイクストラ法の解説です。
上記のようなグラフで、Aから他の頂点への最短経路を求めます。ダイクストラ法は、以下のように各ステップで「未確定の中で最短距離の頂点」を選び、その周囲の頂点の距離を更新していきます。
ダイクストラ法のPython実装例
import heapq
def dijkstra(graph, start):
# graphは、各頂点の隣接リストと距離の辞書として表現
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
queue = [(0, start)] # 優先度付きキュー
while queue:
current_distance, current_vertex = heapq.heappop(queue)
# キューに入っている距離が、既に最短距離より長ければスキップ
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# 新しい距離が既存の距離より短ければ更新
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# グラフの定義例
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))
# 出力例: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
応用アルゴリズム問題: 最長共通部分列(Longest Common Subsequence, LCS)
問題説明:
2つの文字列が与えられたとき、その最長共通部分列(LCS)を求めるアルゴリズムを実装してください。LCSは、両方の文字列に現れる順序を保った部分列のうち最も長いものです。
例:
文字列1: "AGGTAB"
文字列2: "GXTXAYB"
最長共通部分列: "GTAB"
アルゴリズムの概要:
動的計画法(DP)を使って、2次元の表を埋めることにより解くことができます。表のdp[i][j]
は、文字列1の最初のi
文字と文字列2の最初のj
文字の最長共通部分列の長さを保持します。
Python実装:
def lcs_length(str1, str2):
m, n = len(str1), len(str2)
# dpテーブルの初期化(全て0)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# dpテーブルの更新
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
def lcs(str1, str2):
# 最長共通部分列の実際の文字列を復元する
m, n = len(str1), len(str2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# dpテーブルを構築
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
if dp[i-1][j] > dp[i][j-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i][j-1]
# LCSを復元
lcs_seq = []
i, j = m, n
while i > 0 and j > 0:
if str1[i-1] == str2[j-1]:
lcs_seq.append(str1[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(lcs_seq))
# 使用例
str1 = "AGGTAB"
str2 = "GXTXAYB"
print("LCSの長さ:", lcs_length(str1, str2)) # -> 4
print("LCS:", lcs(str1, str2)) # -> "GTAB"
まとめと全体図
ここまでで、アルゴリズムとデータ構造の基本から応用まで幅広く解説しました。以下に、主要な概念とアルゴリズムの関係性を示す図をまとめます。
図の解説
上の図は、アルゴリズムとデータ構造の全体像を示しています。基本アルゴリズムは探索、ソート、再帰とループなどに分かれ、応用アルゴリズムにはBFS/DFS、ダイクストラ法、LCS問題などがあります。各アルゴリズムには時間計算量の特徴があり、適切なデータ構造を選ぶことで効率的に問題を解くことができます。
以上で、基本的なアルゴリズムから応用アルゴリズムまでの解説を終わります。この知識を基に、さらに高度なアルゴリズムの学習を進めてください。データ構造の選択とアルゴリズムの理解は、効率的なプログラミングの鍵となります。
Discussion