こんにちは。倉内です。
プログラミング学習をしていると「アルゴリズム」という単語を聞くことがあると思いますが、いつかしっかり勉強しようと思いつつ手を出せていない方も多いのではないでしょうか。
アルゴリズムは独学では少々とっつきにくい分野ですが、アルゴリズムの知識があれば、よりパフォーマンスが高い処理を実現することができます。
特に大量のデータを扱う場合は、ループを何重にも回すなどの単純処理では途方もない処理時間がかかるため、効率のよい方法を採用する必要があります。
そこで今回は「アルゴリズムとはなにか？」から始まり、データ探索を例にアルゴリズムの基本を説明していきます。Pythonで実際のコードも書いてみますので、ぜひご自分でも実行して試してみてください。
なぜアルゴリズムを学ぶのか
アルゴリズムとは、広い意味では「なんらかの問題を解くための決められた手順や法則のこと」と定義されています。たとえば、「Google検索のアルゴリズム」を単純に言い表すと「ある条件に基づいて検索結果の表示順を決める仕組み」ということになります。
また、冒頭でも書いたとおりアルゴリズムは効率のよい処理を実現する方法とも言えます。
同じ結果を出すプログラムでもさまざまな書き方があり、アルゴリズムを知らなくてもループ処理を繰り返して求めたい結果を得られることもあります。
しかし、大量のデータを処理するWebサービスや処理速度を重視する業務システムの開発などは、アルゴリズムを知らないと実現が困難です。実際の開発業務では、ただコードを書くだけではなく効率的な処理になるよう考慮しなければいけません。
自分でアルゴリズムをいちから考え出すのはとても難しいですが、ありがたいことに先人たちが生み出した多くのアルゴリズムを利用することができます。
これからアルゴリズムを学ぶ上で前提となる基本知識から説明していきますので一緒に学んでいきましょう。
アルゴリズムの基本
データ構造を知ろう
アルゴリズムを学ぶ前にプログラムに与えられるデータについて知る必要があります。データが管理されている形式のことを「データ構造」といいます。
どのようなデータ構造を用いるかはアルゴリズムの効率に大きく影響するため、よく考えて選択する必要があります。ここからはデータ構造とその特徴について説明していきます。
配列
配列は複数のデータを並べたデータ構造のことです。
配列には、一直線上にデータを並べた一次元配列（単に配列という場合が多いと思いますが）、縦横に並べた二次元配列、さらに縦横に奥行きを加えた三次元配列などがあります。Pythonではリストといいます。
Pythonでリストを使ってみましょう。環境構築なしにブラウザ上でコードの実行ができるpaiza.IOで動かしてみると分かりやすいと思います。
num_list = [1,2,3,4,5] for i in num_list: print(i)
出力結果
1
2
3
4
5
リストには以下のように文字列も数値も混在させることができます。
num_list = [1,"Hello",3,"paiza",5.5] for i in num_list: print(i)
出力結果
1
Hello
3
paiza
5.5
ちなみにPythonのリストをもっと詳しく知りたい方は、paizaラーニングの「Python入門編」をごらんください。
スタックとキュー
スタックとキューは以下のような特徴があるデータの持ち方のことで、データを追加することをプッシュ（push）、取り出すことを（pop）といいます。
スタック：
配列やリストに最後に追加（push）したデータを最初に取り出す（pop）。後入れ先出し方式（LIFO：Last In First Out）
日常生活で例えると…積み上げた本を取るときは最後に置いた本から取る
キュー：
配列やリストに最初に追加（push）したデータを最初に取り出す（pop）。先入れ先出し方式（FIFO：First In First Out）
日常生活で例えると…人気のラーメン屋さんの行列に最初に並んだ人が最初にラーメンを食べられる
スタックの例としてよく取り上げられるのが「逆ポーランド記法」です。情報処理技術者試験でもたびたび出題されているので気になる方は調べてみてください。
木構造（ツリー構造）
配列は横並びの要素を管理するにはいいのですが、階層を持つデータを表すことが苦手なためここで登場するのが木構造です。
木構造では頂点にある木の根っこにあたるものを「ルート（root）」、枝分かれした部分を「ノード（node）」、ノードとノードを結んでいる枝のような部分を「ブランチ（branch）」といいます。
ノードは親子関係があり、ルートに近いほうを「親ノード」、遠いほうを「子ノード」と呼びます。あるノードの下の部分だけ見ても木構造になっているため、それを「部分木」と呼びます。
木構造のひとつである「二分木」は、子ノードが最大2つという構造を持っています。
さらに「左の子ノードの値 < 親ノードの値 < 右の子ノードの値」という制約を持ったものを二分探索木（Binary Search Tree）といいます。
探索アルゴリズム
探索とは、目的のデータがどこにあるかを探すという意味です。
ここでは「線形探索」「二分探索」「幅優先探索」「深さ優先探索」の4つを紹介します。
線形探索（Linear Search）
リストの要素に対して、探している値が見つかるまで先頭から順に比較します。
Pythonでは、以下のように書くことができます。
# 以下のリストからターゲットとなる値が何番目にあるか探す num_list_1 = [1,17,4,14,7,5,9,3,5] num_list_2 = [1,3,9,14,7,12,4,17,5] target_num = 4 # 線形探索する def linear_search(list, target): result = -1 for i in range(len(list)): print("for文を通った回数：{}".format(i + 1)) # リストの要素とターゲットの値が一致したら if list[i] == target: result = i break return result # ターゲットとなる値の位置を出力 print(linear_search(num_list_1,target_num)) print(linear_search(num_list_2,target_num))
出力結果
for文を通った回数：1
for文を通った回数：2
for文を通った回数：3
2
for文を通った回数：1
for文を通った回数：2
for文を通った回数：3
for文を通った回数：4
for文を通った回数：5
for文を通った回数：6
for文を通った回数：7
6
図でも示したとおり、1つ目のリストであれば4という値はリストのインデックス「2」の位置、つまり先頭から3番目にあるのでfor文を3回通ることで目的の4を見つけました。
2つ目のリストの場合、リストのインデックス「6」の位置、つまり先頭から7番目にあるのでfor文を7回通ったということになります。
この例ではデータの個数が9個しかないので大したことない気もしますが、膨大なデータ数のときはう少し効率よく探索したいですよね。
二分探索（Binary Search）
ソートされたリストを探索する
ソート済のリストに対し探索をおこなう場合、まず中央の値と探したい値との大小関係から、探したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索を進めていきます。探している値がそのリストに含まれていれば、二分探索はその位置を返します。
上の図のとおり、二分探索では、中央の位置を見ることでデータの半分程度を探索対象から外すことができます。
Pythonでは、以下のように書くことができます。
# 以下のリストからターゲットとなる値が何番目にあるか探す num_list = [1,3,4,5,7,9,12,14,17] target = 12 # 二分探索する def binary_search(list,target): result = -1 left = 0 # リストの左端の位置 right = len(list) - 1 # リストの右端の位置 i = 0 # while文を通った回数をカウント while left <= right: print("while文を通った回数：{}".format(i + 1)) mid = (left + right) // 2 # 中央の位置を決める if list[mid] == target: result = mid break elif list[mid] < target: left = mid + 1 elif list[mid] > target: right = mid - 1 # while文を通った回数をカウントアップ i += 1 return result # ターゲットとなる値の位置を出力 print(binary_search(num_list,target))
出力結果
while文を通った回数：1
while文を通った回数：2
6
最初に中央の位置を決めるときに探索対象の値12が中央の位置（この場合は位置は「4」で値は7）より右側だと分かり、2回の探索で目的の値の位置を特定できました。
リストのインデックスは先頭が「0」なので、12という値が入っているのはインデックス「6」、つまり7番目となり正しい結果が返ってきたことが分かります。
（補足）二分探索をサポートするライブラリ：bisect
実はPythonには二分探索をサポートする標準ライブラリ bisect が用意されています。ソート済のリストに対して、指定した値の位置を知りたいとき、さきほどループと条件分岐を駆使して書いた処理がこんなに簡単に書けます。
import bisect # ソート済のリスト num_list = [1,3,4,5,7,9,12,14,17] # リストに「12」があったらその位置を左側から見て何番目かを示す result_position = bisect.bisect_left(num_list,12) print(result_position)
出力結果
6
リストのインデックスは先頭が「0」なので、「6」つまり7番目に存在するという正しい結果が返ってきました。
二分探索木を探索する
二分探索木の探索はルートからスタートし、探索対象がルートより小さければ左へ、大きければ右へ…と探索を進めます。
この例では、探索対象「4」はルートの「9」より小さいため左のノードへ、そのノードの値は「3」で「4」より小さいため右のノードへ、そのノードの値は「5」で「4」より大きいため左のノードへと探索を進めていき「4」を見つけて終了となります。
幅優先探索（BFS：Breadth First Search）
木構造に対してノードをすべて巡回して探索する方法には、幅優先探索と深さ優先探索があります。
ルートから探索を開始し、同じ深さにある節を横方向に探索していく方法です。下図の二分木の例では、9-3-14-1-5-12-17-4-7の順に探索します。
深さ優先探索（DFS：Depth First Search）
深さ優先探索は、先行順（行きがけ順）・中間順（通りがけ順）・後行順（帰りがけ順）という3種類の方法があります。先行順は親から左部分木→右部分木の順に、中間順は左部分木から親→右部分木の順に、後行順は左部分木から右部分木→親の順にそれぞれ探索します。
（例）先行順探索の探索順を二分木で示す
下図では、9-3-1-5-4-7-14-12-17の順に探索します。
ここでは深さ優先探索の先行順探索をPythonで実装してみましょう。
なお、クラスやメソッドを使っているので「Pythonのクラスってどうやって使うんだっけ…」という方は、「Python入門編」のレッスン7・8を受講してから取り組んでみてください。
# 木構造の中のノードを定義（ノードは値・左に子ノード、右に子ノードを持つ） class Node: def __init__(self, value): self.value = value self.left = None self.right = None # 二分木クラスを定義 class BinaryTree(object): def __init__(self, root): self.root = Node(root) # 行きがけ順（preorder）を二分木クラスのメソッドとして生成 def preorder_print(self, start, traversal): """Root -> Left -> Right""" if start: traversal += (str(start.value) + "-") traversal = self.preorder_print(start.left, traversal) traversal = self.preorder_print(start.right, traversal) return traversal # 二分木を作る tree = BinaryTree(9) tree.root.left = Node(3) tree.root.right = Node(14) tree.root.left.left = Node(1) tree.root.left.right = Node(5) tree.root.left.right.left = Node(4) tree.root.left.right.right = Node(7) tree.root.right.left = Node(12) tree.root.right.right = Node(17) # 定義した二分木を行きがけ順で出力 print(tree.preorder_print(tree.root, ''))
出力結果
9-3-1-5-4-7-14-12-17-
作成した二分木に対して、きちんと先行順で出力できていますね！
もっとアルゴリズムを勉強したいなら
これまでアルゴリズムの基礎を学んできましたが、実際にプログラミング問題を解きながら理解を深めたい方は、paizaラーニングの「アルゴリズム入門編」を受講してみてください。
エンジニアの技術面接でもよく出題されるFizzBuzz、再帰アルゴリズムを使って考えるフィボナッチ数やハノイの塔などの学習講座を公開しています。
また、他にもアルゴリズムが学べるサイトや本は以下の記事でご紹介しています。
まとめ
「アルゴリズムとは何か」から始まり、データ構造や探索のアルゴリズムについて学んできました。
アルゴリズムを用いた処理の実装には、配列、クラスやメソッド、関数といったPythonの基本を習得しておくとスムーズに取り組めると思います。
動画と演習課題で学べる「Python入門編」は全レッスン無料公開中なので、ぜひ基礎固めにご利用ください。
また、今回は初心者でも比較的コードが書きやすいPythonで解説しましたが、大学で情報学科を専攻している方はアルゴリズムの授業はC言語を使うことが多いと思います。
paizaラーニングでは、「C言語入門編」をはじめ、さまざまな言語の基礎を学べるレッスンを公開しています。基本文法や配列、ポインタ、関数の基礎などを学びたい方はぜひチェックしてみてください。
詳しくはこちら
＜参考サイト＞
- 一週間で身につくアルゴリズムとデータ構造|トップページ～プログラマーなら身につけておきたい、アルゴリズムの基本。
- Pythonで二分探索木の生成と探索 - Qiita
- 木構造 - 階層を持ったデータ構造
paizaでは、paizaラーニングだけでなく、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
