Photo by VFS Digital Design
皆さんはアルゴリズムやデータ構造について知っているでしょうか。情報系の学部出身の人は学校の授業でやったかもしれません。一方で学校で情報系の勉強をせずにITエンジニアになったという方は、アルゴリズムやデータ構造について一度は「勉強したほうが良いんだろうな」と思いつつも、実際の業務であんまり必要なさそうだし、難しそうだし、DevOpsやオブジェクト指向やフレームワークについて学ぶので手一杯で未着手、という人も多いのではないでしょうか。
今回はそんな方に向けて、アルゴリズム、データ構造を学ぶ意義と、それらを学ぶときに役立つ本とサイトについてまとめました。
■アルゴリズム、データ構造を学ぶ意味
アルゴリズムやデータ構造について語られるときに、非常に良く言われる事として「そんなものは実務に役立たたないので必要ない」という意見があります。本当にアルゴリズムやデータ構造は実務に役立たないのでしょうか？
実務に役立たないのか？というと、もちろん役立たない仕事も中にはあるでしょう。パンチャーに近いコーダーであれば、仕様書に書かれている日本語をコードに落としていく事が業務範囲なのでアルゴリズムやデータ構造の理解を必要とする事は無いかもしれません。
しかしそういった完全分業でない状態でプログラムを書く仕事をしているのであれば、アルゴリズム、データ構造について知っていて損な事はないでしょう。
例えばソートについてですが、通常すでにソート関数はあるので自分で再度作る必要な無いと思います。しかしソート自体がどのような種類のソートがあり、それぞれのソートアルゴリズムの動作の仕組みと、それによる長所短所を知らなければ最適なソートアルゴリズムを使い分ける事は出来ません。
データ構造についても、例えば配列と連結リストについて、それぞれの構造とメリットデメリットを知らなければ使い分ける事は出来ません。
またこれはプログラミング全般に言える事ですが、動作の仕組みを理解していないと、問題が起きた時に動作の仕組から考えて問題の切り分けが出来ないため、解決法のあたりがつけられないという事も起きがちです。
アルゴリズムやデータ構造は丸暗記する事が重要なのではなく、仕組みを理解する事で、最適な選択ができるようになり、また問題が起きた時に対処がしやすくなります。特に高速化が必要な際などにはアルゴリズムやデータ構造の知識は必要になります。
アルゴリズムを知らずに使う事（ブラックボックスがあるという事）をビジネス的な方面で例えてみると、外注で仕事を依頼するとき、外注先がどのような体制で業務をこなしているかや、何を得意としているのかを知らなければ最適な外注先に依頼する事は出来ないし、少人数の外注に巨大な案件を依頼して炎上してしまうという事も起こってしまう、というような感じでしょうか。
自分が利用しているものの仕組みや中身を知らなければブラックボックスと化してしまい、リスクのコントロールが出来なくなってしまいます。勿論これは程度の問題なので、有限の時間の中ですべてを知る事は不可能ですが、知っておいて損はない事項と言えます。
◆アルゴリズムを現実世界で応用すると
アルゴリズムはプログラミングの中だけで閉じた概念ではありません。実世界で応用できる例もあります。
例えば大きなデータ読みこんで途中で処理が上手くいかないような際に、1行目からデータをチェックするのではなく、まずデータの前半に問題があるのか、後半に問題があるのかを調べ、後半に問題があるのであれば後半をまた半分に分割してみてその前半に問題があるのか後半に問題があるのか、、というように問題個所を狭めていって特定する、ということが有ると思います。このやり方はアルゴリズムで言うと二分探索(バイナリーサーチ)と言います。
遺伝的アルゴリズムでゲームの面白さを上げる、というやり方もあります。
有名なのはZyngaのやり方だ。
彼らは1000人いたら、10人ずつ100チームの小チームを作り、全員で同じゲームを並行して開発する。会員数が100万人いたら、それを100分割して1万人が実は細部の異なるゲームを遊んでいる。
その中で、性能を評価する。チーム12のゲームは継続率が高いが課金率は低い、チーム72は課金率は高いがARPU(一人当たり課金単価)は低い・・・などなど。
性能評価の結果、生き残ったチームの「作品」が、あるタイミングで100万人全プレイヤーに対して提供される。
ソーシャルゲームの向こう側: 単なるWebサービスには飽きてきた。じゃあなんだろう。｜UEI shi3zの日記
http://d.hatena.ne.jp/shi3z/20111217/1324090325
このように実世界でもアルゴリズムを応用し効率を上げる事が出来たりもします。
■アルゴリズム、データ構造を学ぶ時期
ある程度プログラミングに慣れて書けるようになってくると、コードを書いているときに「凄い人だったらもっと良い書き方するんだろうな」と思う瞬間があると思います。
- より効率の良いやり方がありそうだけど…
- より高速なやり方がありそうだけど…
- よりスマートな書き方がありそうだけど…
などなど。こういう事を考えるようになったらアルゴリズムやデータ構造について学ぶのにちょうどよい時期かもしれません。速攻で役立つTipsは少ないかもしれませんが、書き方に迷った時の引き出しが増え、また計算量や効率という判断基準が増えるので、なんとなくコードを書くのではなく、なぜそう書いたかという裏付けを持つことが出来、より良い選択が出来るようになります。
勿論可読性と計算量を天秤にかけて、場合によっては可読性を優先するという事があっても良いのですが、計算量について全く知らなければ天秤にかける事すらできません。
もっと良い書き方ないかな？と思ったり、プログラムが裏でどういう動きをしているのか知りたい、と思ったらアルゴリズムやデータ構造を学ぶのに良いタイミングだと思います。ここからは、アルゴリズムとデータ構造を学ぶのにオススメの本とサイトを紹介していきます。
■初心者にお勧めのアルゴリズムに親しむ本、サイト
まずはアルゴリズムやデータ構造に親しむための読み物系入門書と入門サイトです。具体的なアルゴリズムやデータ構造の解説等ではなく、まだアルゴリズム、データ構造に敷居が高いという方が、利用シーンのイメージを付けるために下記のサイト見たり、本を読んでみると良いかもしれません。
◆VisuAlgo
http://www.comp.nus.edu.sg/~stevenha/visualization/index.html
アルゴリズムをビジュアルで見せてくれるサイトです。概念だけだと解りにくいアルゴリズムもビジュアルで動作の様子を見ていく事で直感的に理解する事が出来るサイトです。
◆世界でもっとも強力な9のアルゴリズム
- 作者: ジョンマコーミック
- 出版社/メーカー: 日経BP社
- 発売日: 2013/10/10
- メディア: Kindle版
- この商品を含むブログ (5件) を見る
◆人間に勝つコンピュータ将棋の作り方
◆数学ガール 乱択アルゴリズム (数学ガールシリーズ 4)
- 作者: 結城浩
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/02
- メディア: ペーパーバック
- 購入: 19人 クリック: 779回
- この商品を含むブログ (101件) を見る
■アルゴリズム、データ構造の入門本
アルゴリズム、データ構造について具体的に学んでみたいと思った方は下記の本を読んでみると良いでしょう。
◆珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造
珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造
- 作者: ジョンベントリー,Jon Bentley,小林健一郎
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/10
- メディア: 単行本
- 購入: 30人 クリック: 551回
- この商品を含むブログ (161件) を見る
◆アルゴリズムクイックリファレンス
- 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/04/26
- メディア: 単行本（ソフトカバー）
- 購入: 11人 クリック: 656回
- この商品を含むブログ (65件) を見る
■アルゴリズム、データ構造の練習系の本、サイト
座学で学ぶだけでなく実際に手を動かして、練習して頭に定着させたい、自分のレベルを知りたいという場合は、下記のサイトや本がオススメです。
◆paiza
http://paiza.jp
プログラミングスキルチェックで出題された問題を解くとプログラミングスキルを6段階に評価してくれるサービスです。最上位のランクS、次のレベルのランクAの問題ではアルゴリズム力が試される問題が出されています。
◆POH
https://paiza.jp/poh/kirishima
とっつきやすい物語形式でアルゴリズム力が試される問題が出題されています。特にアルゴリズムを知らなくても問題自体は解け、各言語の最速実行時間ランキングなども出ており、アルゴリズム別の解答コードや解説も用意されているため、練習やアルゴリズムを学ぶ切っ掛けとして最適です。
◆AOJ
http://judge.u-aizu.ac.jp/onlinejudge/index.jsp?lang=ja
会津大学が提供しているオンラインプログラミングチャレンジのサイトです。高等学校パソコンコンクール・プログラミング部門の過去問題や、日本情報オリンピックの過去問題など100問以上の問題にチャレンジ可能です。
◆入門 データ構造とアルゴリズム
- 作者: Narasimha Karumanchi,黒川利明,木下哲也
- 出版社/メーカー: オライリージャパン
- 発売日: 2013/08/24
- メディア: 大型本
- この商品を含むブログ (9件) を見る
http://www.oreilly.co.jp/books/9784873116341/
競技プログラミング系の本
アルゴリズム力を高める為に競技プログラミングに参加したい、という人向けのサイトと本です。
◆TopCoder
http://www.topcoder.com/
世界のツワモノがそろう競技系プログラミングサイトです。世界レベルで自分の実力を知りたい場合はこちらで腕試しをしてみると良いでしょう。
◆最強最速アルゴリズマー養成講座 プログラミング
最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド
- 作者: 高橋直大
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2012/09/29
- メディア: 大型本
- 購入: 9人 クリック: 319回
- この商品を含むブログ (7件) を見る
◆プログラミングコンテストチャレンジブック
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本（ソフトカバー）
- 購入: 25人 クリック: 473回
- この商品を含むブログ (32件) を見る
■じっくり学びたい人向けの本
◆アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)
アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)
- 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
- 出版社/メーカー: 近代科学社
- 発売日: 2013/12/17
- メディア: 大型本
- この商品を含むブログ (5件) を見る
まとめ
いかがだったでしょうか。アルゴリズム、データ構造の勉強は最初は敷居が高くて先延ばしにしがちなので、なるべく取っ付きやすい本、サイトから紹介をしてみました。アルゴリズム、データ構造は、最初のさわりを学ぶだけでも大分視界が開け、より深く広くプログラミングについて考えられる用になると思いますので、勉強してみる事をオススメします！
paizaではITエンジニアとしてのスキルレベル測定(9言語に対応)や、プログラミング問題による学習コンテンツ(paiza Learning)を提供(こちらは21言語に対応)しています。テストの結果によりS,A,B,C,D,Eの６段階でランクが分かります。自分のプログラミングスキルを客観的に知りたいという方は是非チャレンジしてみてください。