本書について
本書は理解しやすいように工夫されています。思考が大きく飛躍するようなことは避けています。新しい概念を紹介するときには、常に、その場ですぐに説明するか、どこで説明するかを予告しています。基本的な概念を練習問題と多角的な説明で補強することで、どれくらい理解できているかを確認できるようにし、話についていけるようにしています。
本書では、例を使って説明します。記号を並べ立てるのではなく、それらの概念を簡単にイメージできるようにすることを目指しています。また、すでに知っていることを思い出せるようにすることが最も効果的な学習法であるとも考えており、例を見れば思い出すのが容易になります。たとえば、第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 サイトからダウンロードできます。
- https://www.manning.com/books/grokking-algorithms
- https://github.com/egonschiele/grokking_algorithms
本当に楽しく学ぶことが最も効果的な学習法であると筆者は考えています。本書を楽しみ、サンプルコードを実行してください。
第1章 アルゴリズムの紹介
本章の内容
- 本書で説明する内容の基礎固めをする。
- 最初のアルゴリズム（二分探索）を書く。
- アルゴリズムの計算時間を説明する方法（ビッグオー記法）を学ぶ。
1.1 はじめに
アルゴリズム（algorithm）は、タスクを遂行するための命令の集まりです。すべてのコードを「アルゴリズム」と呼ぶこともできますが、本書では、もう少し興味深いものを取り上げます。本書のために選んだアルゴリズムは、高速であるか、興味深い問題を解決するか、その両方です。本書のハイライトをまとめておきます。
- 第1章では、二分探索を取り上げ、アルゴリズムによってコードをどのように高速化できるかを示します。ある例では、必要なステップの個数が40億個から32個にまで減少します。
- GPSデバイスは、グラフアルゴリズムを使って目的地までの最短経路を計算します。グラフアルゴリズムについては、第6章～第8章で説明します。
- チェッカーをするAIアルゴリズムの作成には、動的計画法を利用できます。動的計画法については、第9章で説明します。
どの場合も、アルゴリズムを説明し、例を示します。続いて、アルゴリズムの計算時間をビッグオー記法で表現します。最後に、同じアルゴリズムを使って他にどのような種類の問題を解決できるかについて見ていきます。
1.1.1 パフォーマンスについて学ぶこと
まずはよい知らせから。本書で取り上げるアルゴリズムはどれも、おそらくあなたが普段使っている言語で実装されているため、自分で書く必要はありません。しかし、トレードオフを理解していなければ、せっかくの実装も役に立ちません。本書では、さまざまなアルゴリズムのトレードオフを比較することを学びます。マージソートとクイックソートのどちらを使うべきでしょうか。配列とリストのどちらを使うべきでしょうか。データ構造を別のものに変えるだけで、大きな違いを生むことがあります。
1.1.2 問題の解決について学ぶこと
次に示すように、これまでは手に負えなかったような問題を解決する方法について学びます。
- テレビゲームを作成するのが好きな場合は、グラフアルゴリズムを使って近くにいるユーザーを観察するAIシステムを作成できます。
- k近傍法を使って、レコメンデーションシステムを作成する方法を学びます。
- 問題によっては、タイミングよく解決できないことがあります。NP完全問題の説明では、それらの問題を特定し、近似的な解を得るアルゴリズムを考え出す方法を示します。
本書を読み終える頃には、最も応用範囲の広いアルゴリズムの一部を理解しているはずです。新たに得た知識をもとに、AIやデータベースを対象とした、より具体的なアルゴリズムについて学ぶことができます。あるいは、職場でより大きな課題に挑んでみるのもよいでしょう。
知っておく必要があること
本書を読み始める前に、代数の基礎を理解しておく必要があります。たとえば、f(x)=x×2という関数がある場合、f(5)は何になるでしょうか。10と答えられたら、準備はできています。
さらに、プログラミング言語をどれか1つマスターしていると、本章（および本書）を読み進めるのが楽になるでしょう。本書の例はすべてPythonで書かれています。プログラミング言語は知らないので覚えたい、という場合は、Pythonがお勧めです。Rubyなど、別の言語を知っている場合は、申し分ありません。
1.2 二分探索
電話帳で、ある人を探しているとしましょう（なんて古くさい！）。その人の名前は「K」で始まります。「K」のページにたどり着くまで、最初からページをめくっていくこともできます。ですが、「K」が電話帳の真ん中あたりにあることはわかっているので、真ん中のページから調べ始めるほうが得策です。
あるいは、辞書で単語を調べていて、その単語が「O」で始まるとしましょう。この場合も、辞書の真ん中あたりから調べることになるでしょう。
さて、今度はFacebookにログインするとしましょう。その際、Facebookはあなたがアカウントを持っていることを確認しなければなりません。そこで、データベースであなたのユーザー名を調べる必要があります。あなたのユーザー名が「karlmageddon」であるとしましょう。Facebook は「A」から順番に名前を検索できますが、真ん中あたりから始めるほうが合理的です。
これは探索問題です。そして、これらすべてのケースにおいて、問題の解決に二分探索（binary search）というアルゴリズムが使われます。
二分探索はアルゴリズムであり、その入力はソート済みの要素のリストです。ソート済みでなければならない理由については、後ほど説明します。探している要素がそのリストに含まれている場合、二分探索はその位置を返します。探している要素がリストに含まれていない場合は、nullを返します。
例を見てみましょう。
二分探索の仕組みを示す例として、筆者が1から100までの間にある数字を1つ思い浮かべるとしましょう。
あなたは筆者が思い浮かべた数字をできるだけ少ない回数で言い当てなければなりません。あなたが数字を答えるたびに、その数字が小さすぎる（too low）、大きすぎる（too high）、または正解であることを伝えます。1、2、3、4...といった具合に推測を始めると、次のようになります。
これは単純探索（simple search）です。「のろまな探索」と呼ぶほうがしっくりくるかもしれません。数字を推測するたびに、数字を1つだけ消していきます。筆者が思い浮かべた数字が99 だった場合は、正解にたどり着くまでに99回も推測することになってしまいます。
1.2.1 より効果的な探索法
もっとよい方法があります。50から始めるのです。
50は小さすぎますが、数字の半分が除外されます。この時点で1から50までの数字はすべて小さすぎることがわかります。次に、75と推測します。
75は大きすぎますが、この場合も、残りの数字の半分が除外されます。二分探索では、毎回中央の数字を推測し、残りの数字の半分を除外するからです。次に、（50と75の中間である）63と推測します。
これが二分探索です。あなたはこれで1つ目のアルゴリズムを学びました。毎回どれだけの数字を除外できるか見てみましょう。
筆者がどの数字を思い浮かべたとしても、数字を1つ推測するたびに多くの数字が除外されるため、最大7回で言い当てることができます。
次に、ある単語を辞書で探しているとしましょう。その辞書には、240,000語が収録されています。最悪のケースでは、単純探索と二分探索に必要なステップ数はどれくらいになるでしょうか。
単純探索では、探している単語が辞書の最後の最後にある場合は、240,000ステップが必要になります。二分探索では、単語が1つだけになるまで、ステップごとに残りの単語の個数を半分にしていきます。
したがって、二分探索に必要なステップ数は18になります。これは大きな差です。一般的には、n個の要素からなるリストでは、最悪の場合、二分探索ではlog2nステップが必要になります。単純探索では、nステップが必要になります。
対数
対数が何であるかは忘れてしまったかもしれませんが、おそらく指数は覚えているのではないでしょうか。log10100 は、「10を何回掛けると100になるか」と質問するようなものです。そう、答えは2（10×10=100）です。よって、log10100=2となります。対数は指数をひっくり返したものです。
本書において、（後ほど説明する）ビッグオー記法を用いて計算時間を表すときには、logは常にlog2を意味します。単純探索を使って要素を検索すると、最悪の場合、要素を1つ残らず調べるはめになります。したがって、要素が8個のリストでは、最大で8個の数字を調べることになります。二分探索では、最悪の場合、log8個の要素を調べる必要があります。要素が8個のリストでは、23==8であるため、log8==3となります。したがって、要素が8個のリストでは、最大で3個の数字を調べることになります。要素が1,024個のリストでは、210==1024であるため、log1024==10となります。したがって、要素が1,024 個のリストでは、最大で10個の数字を調べることになります。
本書では、対数時間に繰り返し言及するため、対数の概念を理解しておくようにしてください。対数がよくわからない場合は、対数をわかりやすく説明する動画がKhan Academyにあります。
http://khanacademy.org
二分探索がうまくいくのは、リストがソート済みである場合だけです。たとえば、電話帳の名前はアルファベット順にソートされているため、二分探索を使って名前を調べることができます。名前がソート済みではなかったとしたら、どうなるのでしょうか。
二分探索をPythonで記述する方法を見ていきましょう。このサンプルコードでは、配列を使います。配列の仕組みがわからなくても心配はいりません。配列については次章で説明します。配列と呼ばれる連続したバケットに一連の要素を格納できることだけ知っておいてください。これらのバケットには、0から始まる番号が振られています。1つ目のバケットは0の位置にあり、2つ目のバケットは1の位置、3つ目のバケットは2の位置にある、といった具合になります。
binary_search関数は、ソート済みの配列とアイテムを1つずつ受け取ります。そのアイテムが配列に含まれている場合、この関数はその位置を返します。ここでは、配列のどの部分を検索するのかを追っていきます。最初は、配列全体を検索します。
low = 0 high = len(list) - 1
検索のたびに、真ん中の要素を調べます。
mid = (low + high) / 2 # (low + high) が偶数ではない場合、 guess = list[mid] # mid はPython によって自動的に丸められる
推測した数字が小さすぎる場合は、それに応じてlowを更新します。
if guess < item: low = mid + 1
推測した数字が大きすぎる場合は、highを更新します。完全なコードは次のようになります。
def binary_search(list, item):
low = 0 # lowとhighを使ってリストの検索部分を追跡
high = len(list) - 1
while low <= high: # 1つの要素に絞り込まれるまでの間は...
mid = (low + high) // 2
guess = list[mid] # 真ん中の要素を調べる
if guess == item: # アイテムを検出
return mid
if guess > item: # 推測した数字が大きすぎた
high = mid - 1
else: # 推測した数字が小さすぎた
low = mid + 1
return None # アイテムが存在しない
my_list = [1, 3, 5, 7, 9] # テストしてみる
print binary_search(my_list, 3) # 結果は1：リストは0始まりなので、
# 2つ目のスロットのインデックスは1
print binary_search(my_list, -1) # 結果はNone:Pyhonにおいて「nil」を意味し、
# アイテムが検出されなかったことを示す
練習問題
1.1 128個の名前が含まれたソート済みのリストがあり、二分探索を使って名前を探しているとしよう。ステップ数は最大でいくつになるか。
1.2 このリストのサイズを2倍にした場合、ステップ数は最大でいくつになるか。
