読者です 読者をやめる 読者になる 読者になる

paiza開発日誌

IT/Webエンジニア向け総合求人・学習サービス「paiza」(https://paiza.jp ギノ株式会社)の開発者が開発の事、プログラミングネタ、ITエンジニアの転職などについて書いています。

ITエンジニアなら知っておきたい、今更聞けないアルゴリズムの種類一覧

f:id:paiza:20161205213510j:plain
Photo by Oferico
皆さんはアルゴリズムやデータ構造について勉強したことはありますか?そして、基本的なアルゴリズムについて、どのようなものがあって、どのようなときに使うとよいかといったことを説明することができますか?

仕事をしていると、プログラミング言語等の勉強や業務に忙しくて、正直アルゴリズムどころではないという場合がほとんどでしょう。しかし、いつか勉強しようと思っていたけど、基本的なアルゴリズムにどんなものがあるのかなんて今更聞けないな……ということもあるかと思います。

今回はそんな方に向けて、基本的なアルゴリズムの一部の概要に加え、アルゴリズムの勉強に役立つサイト、書籍をご紹介したいと思います。

アルゴリズムを学ぶ意味

例えば、ソート等については、通常はすでにソート関数があるので、自分で作らなくても済む=アルゴリズムも勉強しなくていいと思ってしまうかもしれません。しかし、ソート一つとっても様々なアルゴリズムがあるので、それぞれどのような方法で、どのようなデータのソートに向いているかを知らないと、システムによって最適なソート方法を選ぶことはできません。また、問題が起きた時にも、中でどのような処理がされているかを理解していなければ、解決方法を考えることはできません

数列を昇順に並び替えたいと思ったときに、先頭からデータを全て順番に見ていく……という方法しか知らなければ、データの種類にかかわらず、同じ方法でソートしていくしかありません。しかし、ある程度プログラミングの経験を積むと、「もっと効率のよいやり方があるのでは?」という指摘を受けたり、自分でも思うようになったりします。

学び始めの頃は思いつかなかったけど、もっと効率のよいやり方、処理が高速になるやり方があるのでは……と気付いたとき、またそういったよりよい方法でシステムを作る必要が発生したときは、アルゴリズムについて勉強する必要があります。

下記、基本的なアルゴリズムから、最近注目されている機会学習関連のアルゴリズムまで、簡単に種類と概要をご紹介していきます。

ごく簡単な概要のご紹介になりますので、興味がわいたり詳しく知りたいと思うアルゴリズムがありましたら、各項目にございます解説サイトのリンクを辿ってみたり、書籍等で詳細を調べてみるのもよいかと思います。

■ソートアルゴリズム

例えば、3 1 2……というふうにランダムに数字の値があったとします。これを、1 2 3……等といった順番に並べ替えるためのアルゴリズムがソートアルゴリズムです。

ソートには色々な手法があり、それぞれの手法の評価軸には、平均計算時間、最悪計算時間、安定ソートか否か、また、実行時のメモリ使用量などがあります。(安定ソートとは、同じ値に関して、ソート前の順序がソート後も維持されているソート方法のことです。)

計算時間を解説する関数に関しては、こちらに解説があります。(ランダウの記号 - Wikipedia

また、こちらのサイトにも個々のアルゴリズムについて詳しい解説があります。

アルゴリズムとデータ構造

ソート - Wikipedia

バブルソート

隣の値と大小比較をし、交換を繰り返していく方法です。
単純ですが実行時間は遅くなります。
最悪計算時間:n^2
安定ソート:〇

バブルソート - Wikipedia

クイックソート

分割統治法の一種で、計算量は入力データにより変わります。
平均計算時間:n log n
最悪計算時間:n^2
安定ソート:×

https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif
クイックソート - Wikipedia

マージソート

分割統治法の一種。
計算量時間(平均、最悪ともに)n log n
安定ソート:〇

マージソート - Wikipedia

バブルソートは処理が遅くなるため、実行時間の早いクイックソートマージソートなどがよく使われます。

クイックソートマージソートでどちらが適しているかは、入力データ次第というところがあります。完全にランダムな数字が入力される場合はクイックソートのほうが一般的に早く、一部がソートされいてるなど完全にランダムではないようなデータの場合は、マージソートの方が有利になる場合があります。

ソートに関しては、n log nより早く処理出来るアルゴリズムは、特定の条件などを除き、存在しないということが証明されています。

上記の他にも、ある特定の条件を満たしている場合には早くなるソート、鳩ノ巣ソートやバケットソートなどもあります。

鳩の巣ソート - Wikipedia

バケットソート - Wikipedia

■探索アルゴリズム

複数のデータの中から、目的のデータがどこにあるかを探すアルゴリズムです。

探索 - Wikipedia

こちらに一部図解つきの解説も載っています。
アルゴリズム : アルゴリズムとデータ構造

◆リスト探索

例えば、1 2 3 4 5……のような数字の列に対し、「3はどこにあるか?」というように目的のデータの場所をを探すアルゴリズムになります。

◇線形探索

単純に、最初から順にデータを見て探していく方法です。

線型探索 - Wikipedia

◇二分探索

データのリストを半分ずつに分けて探索することで、計算量を削減できる方法です。対象のリストがソートされていなくては使用できませんが、高速に探索することができます。

二分探索 - Wikipedia

◆木探索、グラフ探索

木のノードやグラフの探索で、共通で使われるアルゴリズムです。種類としては以下のようなものがあります。

◇幅優先、深さ優先探索

グラフや木構造の探索に使われます。幅優先探索は、隣接ノードを探索を繰り返して解を探索する方法です。深さ優先探索は、ノードの子がなくなるまで深く探索し、解が見つからない場合は探索していないノードまで引き返し、再度ノードの子がなくなるまでを繰り返す探索方法です。

幅優先探索 - Wikipedia

深さ優先探索 - Wikipedia

最強最速アルゴリズマー養成講座:知れば天国、知らねば地獄――「探索」虎の巻 - ITmedia エンタープライズ

◆グラフ探索固有

◇巡回セールスマン問題

都市の集合と各2都市間の移動コストが与えられたとき、全ての都市を一度ずつ巡り、出発地に戻る巡回路の総移動コストが最小のものを求める組合せ最適化問題です。

巡回セールスマン問題 - Wikipedia

・最近傍法

巡回セールスマン問題を解くのに使われた最初のアルゴリズムの1つで、素早く短い経路を求められますが、最短でないことが多い方法です。

最近傍法 - Wikipedia

◇最短経路問題

重み付きグラフの、与えられた2つのノード間を結ぶ経路の中で、重みが最小となる経路を求める最適化問題です。

最短経路問題 - Wikipedia

ダイクストラ

最短経路問題を解くための、最良優先探索によるアルゴリズムです。

ダイクストラ法(最短経路問題)

◆文字列探索

文字列の中に、その文字列より短い任意の文字列が含まれるかを探索するようなアルゴリズムです。

文字列探索 - Wikipedia

◇ボイヤームーアの文字列探索アルゴリズム

検索文字列(パターン)の前処理を行い、検索対象テキストの前処理は行わない方法です。テキストについて何度も検索を行わない場合に適しています。

ボイヤー-ムーア文字列検索アルゴリズム - Wikipedia

計算幾何学の分野に関するアルゴリズム

◆凸包

いくつかの点の集合に対して、それらを含む最小の凸多角形を求めるアルゴリズムです。

凸包 - Wikipedia

点集合の凸包-数学アルゴリズム演習ノート-

レイトレーシング

空間内の物体の集合に、半直線にどの物体が最初に交わるかを求める方法で、例えば、3Dゲームなどで光がどの物体に当たるか等を求めるために使われています。

レイトレーシング - Wikipedia

■その他

◆暗号のアルゴリズム

RSA暗号

大きい合成数素因数分解が難しいのを利用した暗号化アルゴリズムです。

RSA暗号 - Wikipedia

パターン認識機械学習アルゴリズム

サポートベクターマシン

各データの距離が最大になるようなパラメータの線形入力素子を求め、それを利用して2クラスのパターン識別器を構成する手法です。

サポートベクターマシン - Wikipedia

◇K近傍方

あるデータがどのグループに属するかを、距離が近いデータ群の多数決により決定するやり方で、距離が近いデータ群の平均値を、そのデータの値と予想する方法です。

k近傍法 - Wikipedia

◆誤り検出、訂正のアルゴリズム

◇リードソロモン符号

QRコードなどで使われている誤り訂正符号です。難しいですがこちらのブログでかなり詳しく解説されています。

日本中の実装者の中で最も数学能力が低い人間によるQRコードRS符号実装(1)

◇ターボ符号

携帯通信や宇宙船同士の通信において、ノイズがあるような無線通信等で使われている誤り訂正符号です。

ターボ符号 - Wikipedia

アルゴリズムの勉強に適したサイトと書籍

アルゴリズムは研究の域まで達すると非常に多くの種類があり、上記でご紹介したものははほんの一部になります。

「もっと具体的に知りたい!」という方のために、アルゴリズムの学習に最適なサイトと書籍もご紹介いたします。

◆1.VisuAlgo

http://www.comp.nus.edu.sg/~stevenha/visualization/index.html


アルゴリズムをビジュアルで見せてくれるサイトです。アルゴリズムは文章だけで概念を解説されてもなかなか分かりにくいことが多いですが、こちらはビジュアルで動作の様子を見ることができます。「文字で読んで何となく分かったような気がする」アルゴリズムについても、ビジュアルの動きで直感的に理解することができます。

◆2.アルゴリズムを、はじめよう

アルゴリズムを、はじめよう

アルゴリズムを、はじめよう

アルゴリズムの入門書としてかなり分かりやすい書籍だと思います。アルゴリズムを学ぶ以前の、プログラミングにおける基礎的な分岐や繰り返しといった処理についても解説がありますので、「そもそもプログラミングの勉強も始めたばかり」という方にもお勧めです。

◆3.「アルゴリズム」のキホン

「アルゴリズム」のキホン (イチバンやさしい理工系シリーズ)

「アルゴリズム」のキホン (イチバンやさしい理工系シリーズ)

こちらも多くの図を使って、かなり初心者向けにかみくだいた解説がされているアルゴリズム入門書です。「情報系の勉強をしたことはないんだけど、仕事でエンジニアと会話することが多いので勉強したい……でも難しい書籍だと理解できない……」という場合にもよいかもしれません。フルカラーだしキャラクターもかわいいです。

◆4.アルゴリズムの絵本

アルゴリズムの絵本-プログラミングが好きになる9つの扉

アルゴリズムの絵本-プログラミングが好きになる9つの扉

絵本シリーズのアルゴリズム版です。こちらは多少C言語の基礎知識が必要かと思いますが、「アルゴリズムは文章だけで説明されても分かりにくいし、図が多い書籍があればとっつきやすいな……」という方にぴったりだと思います。

◆5.基本情報技術者 大滝みや子先生のかんたんアルゴリズム解法

基本情報技術者の試験対策向けの書籍で、疑似言語等アルゴリズムを考える必要がある問題の解法についてが詳しく解説されています。プログラミング経験が浅い人だと、こういった問題を解くのはなかなか難しいかと思いますが、初めて受験する人でも理解できるようにかなり丁寧に解説されています。もちろん受験しない人でもアルゴリズムの勉強に役立つと思います。

◆6.図解でかんたんアルゴリズム

アルゴリズムについての説明がコンパクトにまとまっている新書です。よく使うアルゴリズムのパターンがが多く収録されています。技術書は大きいものが多い中で、このサイズ感はありがたいです……。「分厚い本は読む気がしない」「通勤中に勉強したい」「いろいろなアルゴリズムの概要が知りたい」という方にとても良い書籍だと思います。

◆7.アルゴリズムパズル ―プログラマのための数学パズル入門

アルゴリズムパズル ―プログラマのための数学パズル入門

アルゴリズムパズル ―プログラマのための数学パズル入門

こちらは「パズルを解くことで、アルゴリズム的思考を鍛える」というコンセプトで、150問のパズル問題が収録されています。ハノイの塔やnクイーン問題など、採用試験等でもよく出される問題についても収録されています。「パズルを解くのが好きだ」「実際に問題を解いて頭を動かしながら勉強したい」という場合にぴったりです。問題解くの楽しいです。難問もたくさんありますが……。

◆8.paizaオンラインハッカソンVol.1「新人女子プログラマの書いたコードを直すだけの簡単なお仕事です!」

https://paiza.jp/poh/ec-campaign

paizaオンラインハッカソンVol.1は、実際のプログラミング問題を通してアルゴリズムに触れることができます。

こちらの問題は、探索のアルゴリズムを使って解くことができます。全探索でも解くことはできますが、二分探索の方がより速くなります。さらに、テストケースを全てクリアしたい場合は、尺取り法(与えられた配列の中から、ある条件を満たす最大の範囲を見つけるアルゴリズム)で解く必要があります。

・模範解答
paizaオンラインハッカソン模範解答

・解説記事
paiza.hatenablog.com

■まとめ

プログラミングの勉強を始めると、言語の勉強が主体となり、アルゴリズムの勉強というのはなかなか後回しになってしまいがちです。また、初心者の方や数学が苦手だった方には敷居が高いと感じてしまうかもしれません。

しかし、今後もエンジニアとしてシステムを作り続けていくのであれば、早めに学んでおいて損はありません。

まずはよく使われる基本的な方法を押さえて、それから興味のわいたアルゴリズムを勉強してみるとよいかと思います。

paiza動画ラーニングについて

f:id:paiza:20160307113923p:plain
paizaには、オンラインでプログラミング学習ができるパイザ・ラーニングという無料学習コンテンツがございます!現在、PHPRubyPythonの入門編を学ぶことができますが、対応言語は今後もどんどん追加される予定となっています。

プログラミング未経験の方でも、「やさしく・楽しく・わかりやすい1本約3分のレッスン動画」 や 「ブラウザ上でコードを書いて実行できるオンライン実行環境」「複数の練習問題」で、未経験者でも無理なく学習を続けることができます。




paizaではITエンジニアとしてのスキルレベル測定(9言語に対応)や、プログラミング問題による学習コンテンツ(paiza Learning)を提供(こちらは21言語に対応)しています。テストの結果によりS,A,B,C,D,Eの6段階でランクが分かります。自分のプログラミングスキルを客観的に知りたいという方は是非チャレンジしてみてください。

http://paiza.jp

プログラミング入門講座|paizaラーニング

PHP入門編Ruby入門編Python入門編Java入門編JavaScript入門編C言語入門編C#入門編アルゴリズム入門編