プログラミングの学習を進めていると、「コードの意味が理解できない」といった状態が起きてしまいます。
しかし、とりあえず先に進まないとプログラミング学習は学ばないといけない内容が非常に多いし、でもある程度知識がないとコードを読んでも理解できないといった「負の連鎖」に陥ることになります。
なんとかプログラミングを理解できる方法はないかとネットで探していると、この動画に目が止まりました。
参照元：「必須教養!?プログラミング“金メダリスト”に学ぶ『アルゴリズム』【橋本幸治の理系通信】（2022年3月30日）」
この動画を見ると、アルゴリズムを理解することで世の中の大抵のことは解決できるのではないかと思ってしまいました。（めっちゃ楽観的な意見ですがご了承ください。。）
このように、アルゴリズムはさまざまな問題を解決するのに非常に役立ちますが、仕組みを理解することはそう簡単ではありません。
以下に調査した内容を自分なりにまとめてみました。
アルゴリズムとは
アルゴリズムを直訳すると「算法」になるかと思います。
先ほど紹介した動画内では問題解決のための「計算手順」で、例えば、スーパーコンピューターでも100年かかる計算を、効率的なアルゴリズムを使えば0.01秒で解決できる場合もあることをお話しされています。
イメージとして、下記のフローチャートがわかりやすかったです。
単なる足し算も数が非常に多くなると処理に時間がかかりますが、繰り返し処理を行うことで処理時間を短縮することができます。
図1：順次構造と繰り返し構造のイメージ図
ChatGPTなどのAI技術も非常に発展していることや、Google検索など日常にもビックデータが溢れていることを考慮しても、アルゴリズムの理解は非常に重要そうです。
ただし、アルゴリズムをちゃんと理解するには高度な数学の知識が必要となることがあるので、まずは基本的なアルゴリズムから理解していき、徐々に難しいアルゴリズムも学習していくのが良さそうです。
アルゴリズムを理解するための前提知識
さっきの図からもわかるかもしれないですが、プログラミングの基本構造である「順次」「分岐」「反復」の3要素は理解しておくことは必須だと思います。
もちろん他にも理解すべきこと（関数式、微分・積分、行列など）はたくさんあります。
例として、「お菓子を友だちに配る」というシチュエーションで考えてみます。
「順次」
上から順にひとつずつ実行していく処理。
下記のように、単に3つのお菓子を配ったこと伝えたいだけなら順次処理で可能です。
# 1つ目のお菓子を準備
お菓子1 = "チョコレート"
# 2つ目のお菓子を準備
お菓子2 = "キャンディー"
# 3つ目のお菓子を準備
お菓子3 = "クッキー"
# お菓子を友だちに配る
print("友だちに3つのお菓子を配りました！")
# 出力結果：友だちに3つのお菓子渡しました！
「分岐」
条件によって実行内容を変える処理。
例えば、友だちが好きなお菓子に配る場面が想像しやすいかもしれません。
友だちの好きなお菓子 = "チョコレート"
# 友だちがチョコレートが好きならそれを配る
if 友だちの好きなお菓子 == "チョコレート":
print("チョコレートを配ります！")
# 友だちがキャンディーが好きならそれを配る
elif 友だちの好きなお菓子 == "キャンディー":
print("キャンディーを配ります！")
# 友だちがクッキーが好きならそれを配る
elif 友だちの好きなお菓子 == "クッキー":
print("クッキーを配ります！")
# それ以外のものが好きなら別のものを配る
else:
print("他のお菓子を配ります！")
# 出力結果：チョコレートを配ります！
「反復」
文字通り同じ動作を繰り返す処理。
例えば、下記のように複数の友だちにお菓子を順番に配る場面が想像しやすいと思います。
友だちのリスト = ["友だち1", "友だち2", "友だち3"]
お菓子のリスト = ["チョコレート", "キャンディー", "クッキー"]
# 全員にそれぞれのお菓子を配る
for 友だち, お菓子 in zip(友だちのリスト, お菓子のリスト):
print(f"{友だち}に{お菓子}を配ります！")
# 出力結果：
# 友だち1にチョコレートを配ります！
# 友だち2にキャンディーを配ります！
# 友だち3にクッキーを配ります！
日常生活でもアルゴリズムは使用されている
普段生活している中でも、アルゴリズムを活用している事例は数多く存在します。
その代表格として、よく挙げられるのはGoogle検索ではないでしょうか。
以下の動画で、Googleアルゴリズムの根幹となった創設者の1人であるラリー・ペイジさんの論文について面白くお話しされています。
参照元：「Googleの根幹になった論文を読む。検索エンジンの解剖。【Google1】#42」実際にGoogle検索はユーザーにとって最適な検索環境を提供するために、定期的に検索アルゴリズムの改良を行っています。
以下は大型アップデートの一部になりますが、興味がある方は調べてみてください。
パンダアップデート
ハミングバード
ベニスアップデート
ペンギンアップデート
モバイルフレンドリーアップデート など
他にも、「Yahoo!路線情報」などの乗り換え案内には、どのように電車を乗り継げば最短で目的地へ辿り着くことができるかを検討するのにアルゴリズムの技術が使われていたり、最近ではAIを活用した自動化にもアルゴリズムの技術が使われていたりします。
図2：乗換案内のイメージ図
基本的なアルゴリズム
これまでは、そもそもアルゴリズムの概念理解から日常生活でどのように使われているかをまとめてみました。
ここでは、基本的なアルゴリズムをPythonを例に紹介します。
1. 線形探索 (Linear Search)
線形探索は、リストや配列の中から目的の値を探すアルゴリズムで、リストの先頭から順番に1つずつ調べていきます。
例: 数字のリストから「5」を探す
def 線形探索(リスト, 探す値):
for 要素 in リスト:
if 要素 == 探す値:
return True
return False
リスト = [3, 8, 2, 7, 5]
探す値 = 5
結果 = 線形探索(リスト, 探す値)
print(結果)
# True
2. 二分探索 (Binary Search)
二分探索は、整列されたリストの中から目的の値を探すアルゴリズムで、線形探索よりも効率よく計算ができます。
例: 整列されたリストから「7」を探す
def 二分探索(リスト, 探す値):
左 = 0
右 = len(リスト) - 1
while 左 <= 右:
中央 = (左 + 右) // 2
if リスト[中央] == 探す値:
return True
elif リスト[中央] < 探す値:
左 = 中央 + 1
else:
右 = 中央 - 1
return False
リスト = [1, 3, 5, 7, 9]
探す値 = 7
結果 = 二分探索(リスト, 探す値)
print(結果)
# 出力結果：True
3. バブルソート (Bubble Sort)
バブルソートは、隣り合う要素を比較して、順番が間違っていれば交換することでリストを整列するアルゴリズムです。最も単純な整列アルゴリズムの1つですが、効率が良くないため大きなリストには向いていません。
例: リストを昇順に整列する
def バブルソート(リスト):
n = len(リスト)
for i in range(n):
for j in range(0, n-i-1):
if リスト[j] > リスト[j+1]:
リスト[j], リスト[j+1] = リスト[j+1], リスト[j]
return リスト
リスト = [5, 3, 8, 2, 1]
結果 = バブルソート(リスト)
print(結果)
# 出力結果：[1, 2, 3, 5, 8]
4. 選択ソート (Selection Sort)
選択ソートは、リストから最小（または最大）の要素を選んで、リストの先頭に移動させることで整列を行います。
例: リストを昇順に整列する
def 選択ソート(リスト):
n = len(リスト)
for i in range(n):
最小インデックス = i
for j in range(i+1, n):
if リスト[j] < リスト[最小インデックス]:
最小インデックス = j
リスト[i], リスト[最小インデックス] = リスト[最小インデックス], リスト[i]
return リスト
リスト = [5, 3, 8, 2, 1]
結果 = 選択ソート(リスト)
print(結果)
# 出力結果：[1, 2, 3, 5, 8]
5. 挿入ソート (Insertion Sort)
挿入ソートは、リストの中で未整列の部分から1つずつ要素を取り出し、それを適切な位置に挿入していく整列アルゴリズムです。少数の要素を整列する場合に効果的です。
例: リストを昇順に整列する
def 挿入ソート(リスト):
for i in range(1, len(リスト)):
key = リスト[i]
j = i - 1
while j >= 0 and key < リスト[j]:
リスト[j + 1] = リスト[j]
j -= 1
リスト[j + 1] = key
return リスト
リスト = [5, 3, 8, 2, 1]
結果 = 挿入ソート(リスト)
print(結果)
# 出力結果：[1, 2, 3, 5, 8]
6. クイックソート (Quick Sort)
クイックソートは、分割統治法（Divide and Conquer）を使ってリストを整列します。リストの要素を基準（ピボット）にして、それより小さい要素と大きい要素に分け、再帰的に処理して整列します。
比較的に大規模なリストの処理に効果的とされています。
例: リストを昇順に整列する
def クイックソート(リスト):
if len(リスト) <= 1:
return リスト
ピボット = リスト[0]
左 = [x for x in リスト[1:] if x < ピボット]
右 = [x for x in リスト[1:] if x >= ピボット]
return クイックソート(左) + [ピボット] + クイックソート(右)
リスト = [5, 3, 8, 2, 1]
結果 = クイックソート(リスト)
print(結果)
# 出力結果：[1, 2, 3, 5, 8]
7. マージソート (Merge Sort)
マージソートも分割統治法を使用した整列アルゴリズムです。リストを半分に分け、それぞれを整列してから結合することで整列を行います。
例: リストを昇順に整列する
def マージソート(リスト):
if len(リスト) <= 1:
return リスト
中央 = len(リスト) // 2
左 = マージソート(リスト[:中央])
右 = マージソート(リスト[中央:])
結果 = []
while 左 and 右:
if 左[0] < 右[0]:
結果.append(左.pop(0))
else:
結果.append(右.pop(0))
結果.extend(左 if 左 else 右)
return 結果
リスト = [5, 3, 8, 2, 1]
結果 = マージソート(リスト)
print(結果)
# 出力結果：[1, 2, 3, 5, 8]
さいごに
まずはアルゴリズムの基礎的な内容についてまとめてみました。
アルゴリズムは、プログラマーに限らず理解を深めることで、さまざまな問題解決の手助けになります。
また、普段使っているWebサービスの仕組みを理解しやすくなる上に、基本情報技術者試験にも出題があるので資格試験の対策にもなります。
私もまだまだ理解が浅いので、Web上だけでなく書籍なども活用しながらより理解を深めていこうと思います。
リンク集
今回の記事を書いていく中で、興味のある記事がいくつかあったので自分用のログとして記載しておきます。
▼プログラミングの基礎理解
▼アルゴリズムについてより詳しく
▼Google検索アルゴリズムについて
▼アルゴリズムの実装方法について