第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倍にした場合、ステップ数は最大でいくつになるか。
