アルゴリズムを勉強するなら二分探索から始めよう! 『なっとく!アルゴリズム』より (1/2)|翔泳社の本

アルゴリズムを勉強するなら二分探索から始めよう! 『なっとく!アルゴリズム』より

2017/02/08 07:00

 新しいサービスやプロダクトを開発するなら、アルゴリズムの理解はもはや欠かせなくなってきました。まだ理解が浅い、勉強したいと思っている、そんな方には翔泳社が1月31日に刊行した『なっとく!アルゴリズム』をおすすめします。今回は本書の読み方と、アルゴリズムの例として二分探索について紹介します。

※いずれも『なっとく!アルゴリズム』より抜粋(記事掲載に合わせ一部改変)。

本書について

 本書は理解しやすいように工夫されています。思考が大きく飛躍するようなことは避けています。新しい概念を紹介するときには、常に、その場ですぐに説明するか、どこで説明するかを予告しています。基本的な概念を練習問題と多角的な説明で補強することで、どれくらい理解できているかを確認できるようにし、話についていけるようにしています。

 本書では、例を使って説明します。記号を並べ立てるのではなく、それらの概念を簡単にイメージできるようにすることを目指しています。また、すでに知っていることを思い出せるようにすることが最も効果的な学習法であるとも考えており、例を見れば思い出すのが容易になります。たとえば、第2章で説明する配列とリンクリストの違いを覚えるときに、「映画を観るために座席に座る」と考えるだけで済むようになります。また、くどいようですが、筆者は見て覚えるたちなので、本書はイラストだらけです。

 本書の内容は選び抜かれたものです。ソートアルゴリズムを1つ残らず取り上げる本を書く必要はありません。それなら、WikipediaやKhan Academyがあります。本書に含まれているアルゴリズムはどれも実用的なものです。ソフトウェアエンジニアとして仕事をしていて役立つことは確認済みであり、さらに複雑なテーマに取り組むためのしっかりとした基盤が築かれるはずです。楽しみながら読んでください。

本書の構成

 本書の最初の3つの章では、基盤を築きます。

第1章

 最初の実用的なアルゴリズムとして、二分探索を取り上げます。また、ビッグオー記法を使ってアルゴリズムの速度を分析することについても説明します。本書では、アルゴリズムがどれだけ低速か、高速かを分析するために、ビッグオー記法をあちこちで使います。

第2章

 配列とリンクリストという2つの基本的なデータ構造を取り上げます。本書では、これらのデータ構造をあちこちで使います。これらは、第5章で説明するハッシュテーブルなど、より高度なデータ構造の作成に使われます。

第3章

 再帰を取り上げます。再帰は、第4章で説明するクイックソートなど、多くのアルゴリズムで使われる便利な手法です。

 筆者の経験では、ビッグオー記法と再帰は初心者にとって難易度の高いテーマです。このため、以降の章ではペースを落として、少し時間をかけて説明します。

 第4章以降は、幅広い用途を持つアルゴリズムを取り上げます。

問題解決手法

 第4章、第8章、第9章で取り上げます。問題にぶつかり、効率よく解決する方法がわからない場合は、分割統治(第4章)か動的計画法(第9章)を試してみてください。効率的な解決法がないことに気づいた場合は、貪欲法(第8章)を使って近似解を求めることができます。

ハッシュテーブル

 第5章で取り上げるハッシュテーブルは、非常に便利なデータ構造です。ハッシュテーブルには、人の名前とメールアドレスや、ユーザー名とパスワードなど、一連のキーと値のペアが含まれています。ハッシュテーブルの有用性はいくら強調しても足りないくらいです。問題を解くとき、筆者は「ハッシュテーブルを使えるか」と「これをグラフとしてモデル化できるか」の2つを最初に考えるようにしています。

グラフアルゴリズム

 第6章と第7章で取り上げます。グラフは、ソーシャルネットワーク、道路網、ニューロンなど、何らかの接続の集まりであるネットワークをモデル化するための手法です。幅優先探索(第6章)とダイクストラ法(第7章)は、ネットワーク内の2点間の最短距離を求めるための手法です。これらの手法を使って、2人の間の距離や目的地までの最短距離を割り出すことができます。

k近傍法

 第10章で取り上げます。k近傍法はシンプルな機械学習アルゴリズムです。k近傍法を利用すれば、レコメンデーションシステム、OCRエンジン、株価を予測するシステムなどを構築できます。つまり、「Aditはこの映画を星4つと評価するだろう」といった値の予測や、「その文字はQである」といったオブジェクトの分類を必要とするあらゆるシステムを構築できます。

次なるステップ

 第11章では、10個のアルゴリズムを取り上げます。それにより、次に何を読めばよいかがわかるでしょう。

本書の使い方

 本書の順序と内容は注意深く設計されたものです。興味のあるテーマを見つけた場合は、それを先に読んでもかまいません。そうでなければ、各章を順番に読んでください。各章の内容は1つ前の章の内容に基づいています。

 サンプルコードはぜひ自分で試してみてください。この部分はいくら強調しても足りないくらいです。サンプルコードを入力(またはダウンロード)し、実行してみてください。実際に試してみれば、はるかによく理解できるはずです。

 また、本書の練習問題を解いてみることもお勧めします。練習問題は短く、通常は1、2分で終わりますが、5~10分かかることもあります。練習問題は、あなたが理解していることを確認するのに役立ちます。このため、正しく理解できていなかったとしても、手遅れになる前にわかります。

本書の対象読者

 本書では、コーディングの基礎知識があり、アルゴリズムを理解したいと考えている読者を対象としています。もしかすると、すでにコーディングで問題を抱えていて、アルゴリズムによる解決法を探っているところかもしれません。あるいは、アルゴリズムが何の役に立つのかを知りたいのかもしれません。本書が役立つと思われる読者を簡単にまとめておきます(もちろん、これだけではありません)。

  • 趣味でプログラムを書いている
  • コーディングブートキャンプを受講している
  • 大学でコンピュータサイエンスを学んだが、記憶がさびついている
  • 大学時代に物理学や数学などを専攻しており、プログラミングに興味がある

コードの表記とダウンロード

 本書では、すべてのサンプルコードでPython 2.7を使っています。本書のコードはすべて、本文と区別するために「等幅フォント」で書かれています。コードのコメントは、重要な概念を示しています。

 本書のサンプルコードは以下のWeb サイトからダウンロードできます。

 本当に楽しく学ぶことが最も効果的な学習法であると筆者は考えています。本書を楽しみ、サンプルコードを実行してください。