Photo by PROdougwoods
皆さんはアルゴリズムやデータ構造について勉強したことはありますか？そして、基本的なアルゴリズムについて、どのようなものがあって、どのようなときに使うとよいかといったことを説明することができますか？
仕事をしていると、プログラミング言語等の勉強や業務に忙しくて、正直アルゴリズムどころではないという場合がほとんどでしょう。しかし、いつか勉強しようと思っていたけど、基本的なアルゴリズムにどんなものがあるのかなんて今更聞けないな……ということもあるかと思います。
今回はそんな方に向けて、基本的なアルゴリズムの一部の概要に加え、アルゴリズムの勉強に役立つサイト、書籍をご紹介したいと思います。
■アルゴリズムを学ぶ意味
Photo by Steve Welburn
例えば、ソート等については、通常はすでにソート関数があるので、自分で作らなくても済む＝アルゴリズムも勉強しなくていいと思ってしまうかもしれません。しかし、ソート一つとっても様々なアルゴリズムがあるので、それぞれどのような方法で、どのようなデータのソートに向いているかを知らないと、システムによって最適なソート方法を選ぶことはできません。また、問題が起きた時にも、中でどのような処理がされているかを理解していなければ、解決方法を考えることはできません。
数列を昇順に並び替えたいと思ったときに、先頭からデータを全て順番に見ていく……という方法しか知らなければ、データの種類にかかわらず、同じ方法でソートしていくしかありません。しかし、ある程度プログラミングの経験を積むと、「もっと効率のよいやり方があるのでは？」という指摘を受けたり、自分でも思うようになったりします。
学び始めの頃は思いつかなかったけど、もっと効率のよいやり方、処理が高速になるやり方があるのでは……と気付いたとき、またそういったよりよい方法でシステムを作る必要が発生したときは、アルゴリズムについて勉強する必要があります。
下記、基本的なアルゴリズムから、最近注目されている機会学習関連のアルゴリズムまで、簡単に種類と概要をご紹介していきます。
ごく簡単な概要のご紹介になりますので、興味がわいたり詳しく知りたいと思うアルゴリズムがありましたら、各項目にございます解説サイトのリンクを辿ってみたり、書籍等で詳細を調べてみるのもよいかと思います。
■ソートアルゴリズム
例えば、3 1 2……というふうにランダムに数字の値があったとします。これを、1 2 3……等といった順番に並べ替えるためのアルゴリズムがソートアルゴリズムです。
ソートには色々な手法があり、それぞれの手法の評価軸には、平均計算時間、最悪計算時間、安定ソートか否か、また、実行時のメモリ使用量などがあります。（安定ソートとは、同じ値に関して、ソート前の順序がソート後も維持されているソート方法のことです。）
計算時間を解説する関数に関しては、こちらに解説があります。（ランダウの記号 - Wikipedia）
また、こちらのサイトにも個々のアルゴリズムについて詳しい解説があります。
◆マージソート
分割統治法の一種。
計算量時間（平均、最悪ともに）n log n
安定ソート：〇
バブルソートは処理が遅くなるため、実行時間の早いクイックソートやマージソートなどがよく使われます。
クイックソートとマージソートでどちらが適しているかは、入力データ次第というところがあります。完全にランダムな数字が入力される場合はクイックソートのほうが一般的に早く、一部がソートされいてるなど完全にランダムではないようなデータの場合は、マージソートの方が有利になる場合があります。
ソートに関しては、n log nより早く処理出来るアルゴリズムは、特定の条件などを除き、存在しないということが証明されています。
上記の他にも、ある特定の条件を満たしている場合には早くなるソート、鳩ノ巣ソートやバケットソートなどもあります。
■探索アルゴリズム
複数のデータの中から、目的のデータがどこにあるかを探すアルゴリズムです。
こちらに一部図解つきの解説も載っています。
アルゴリズム : アルゴリズムとデータ構造
◆リスト探索
例えば、1 2 3 4 5……のような数字の列に対し、「3はどこにあるか？」というように目的のデータの場所をを探すアルゴリズムになります。
◇二分探索
データのリストを半分ずつに分けて探索することで、計算量を削減できる方法です。対象のリストがソートされていなくては使用できませんが、高速に探索することができます。
◆木探索、グラフ探索
木のノードやグラフの探索で、共通で使われるアルゴリズムです。種類としては以下のようなものがあります。
◆グラフ探索固有
◇巡回セールスマン問題
都市の集合と各2都市間の移動コストが与えられたとき、全ての都市を一度ずつ巡り、出発地に戻る巡回路の総移動コストが最小のものを求める組合せ最適化問題です。
■計算幾何学の分野に関するアルゴリズム
◆レイトレーシング
空間内の物体の集合に、半直線にどの物体が最初に交わるかを求める方法で、例えば、3Dゲームなどで光がどの物体に当たるか等を求めるために使われています。
■その他
◆暗号のアルゴリズム
■アルゴリズムの勉強に適したサイトと書籍
アルゴリズムは研究の域まで達すると非常に多くの種類があり、上記でご紹介したものははほんの一部になります。
「もっと具体的に知りたい！」という方のために、アルゴリズムの学習に最適なサイトと書籍もご紹介いたします。
◆1.VisuAlgo
http://www.comp.nus.edu.sg/~stevenha/visualization/index.html
アルゴリズムをビジュアルで見せてくれるサイトです。アルゴリズムは文章だけで概念を解説されてもなかなか分かりにくいことが多いですが、こちらはビジュアルで動作の様子を見ることができます。「文字で読んで何となく分かったような気がする」アルゴリズムについても、ビジュアルの動きで直感的に理解することができます。
◆2.アルゴリズムを、はじめよう
- 作者: 伊藤静香
- 出版社/メーカー: インプレスジャパン
- 発売日: 2012/05/14
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
◆3.「アルゴリズム」のキホン
「アルゴリズム」のキホン (イチバンやさしい理工系シリーズ)
- 作者: 杉浦賢
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/18
- メディア: 単行本
- 購入: 3人 クリック: 32回
- この商品を含むブログ (15件) を見る
◆4.アルゴリズムの絵本
- 作者: (株)アンク
- 出版社/メーカー: 翔泳社
- 発売日: 2003/08/05
- メディア: 単行本（ソフトカバー）
- 購入: 1人 クリック: 77回
- この商品を含むブログ (7件) を見る
◆5.基本情報技術者 大滝みや子先生のかんたんアルゴリズム解法
基本情報技術者 大滝みや子先生のかんたんアルゴリズム解法 ~流れ図と擬似言語~ 第3版
- 作者: 大滝みや子
- 出版社/メーカー: リックテレコム
- 発売日: 2015/01/28
- メディア: 単行本
- この商品を含むブログを見る
◆6.図解でかんたんアルゴリズム
図解でかんたんアルゴリズム 情報処理のかなめとなる考え方が手に取るようにわかる! (サイエンス・アイ新書)
- 作者: 杉浦賢
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2012/12/18
- メディア: 新書
- この商品を含むブログを見る
◆7.アルゴリズムパズル ―プログラマのための数学パズル入門
- 作者: Anany Levitin,Maria Levitin,黒川洋,松崎公紀
- 出版社/メーカー: オライリージャパン
- 発売日: 2014/04/26
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (8件) を見る
◆8.paizaオンラインハッカソンVol.1「新人女子プログラマの書いたコードを直すだけの簡単なお仕事です！」
https://paiza.jp/poh/ec-campaign
paizaオンラインハッカソンVol.1は、実際のプログラミング問題を通してアルゴリズムに触れることができます。
こちらの問題は、探索のアルゴリズムを使って解くことができます。全探索でも解くことはできますが、二分探索の方がより速くなります。さらに、テストケースを全てクリアしたい場合は、尺取り法（与えられた配列の中から、ある条件を満たす最大の範囲を見つけるアルゴリズム）で解く必要があります。
・模範解答
paizaオンラインハッカソン模範解答
・解説記事
paiza.hatenablog.com
■まとめ
プログラミングの勉強を始めると、言語の勉強が主体となり、アルゴリズムの勉強というのはなかなか後回しになってしまいがちです。また、初心者の方や数学が苦手だった方には敷居が高いと感じてしまうかもしれません。
しかし、今後もエンジニアとしてシステムを作り続けていくのであれば、早めに学んでおいて損はありません。
まずはよく使われる基本的な方法を押さえて、それから興味のわいたアルゴリズムを勉強してみるとよいかと思います。
paizaではITエンジニアとしてのスキルレベル測定(9言語に対応)や、プログラミング問題による学習コンテンツ(paiza Learning)を提供(こちらは21言語に対応)しています。テストの結果によりS,A,B,C,D,Eの６段階でランクが分かります。自分のプログラミングスキルを客観的に知りたいという方は是非チャレンジしてみてください。