〇 これなしでITは成り立たない、アルゴリズムの基礎「探索」を学ぶ。
実用的なソフトウエアを開発するにはアルゴリズムの知識は欠かせない。基礎から機械学習まで、厳選した10個のアルゴリズムをPythonによる実装とともに解説する。
デジタル時代に生きる私たちは、様々な「アルゴリズム」に囲まれています。スマートフォンの中でも、ECサイトの裏側でも、いろいろなアルゴリズムが活躍しています。
そこでこの特集では、改めてアルゴリズムを解説します。取り上げるアルゴリズムは厳選した10個です。たった10個ですが、この10個を通して、アルゴリズムの重要性と多様性、そして面白さがわかるようになると思います。
アルゴリズムの実装例のプログラムは、Pythonで記述します。ここでは「Anaconda Distribution」に付属するプログラミングツールの「Jupyter Notebook」を使って、Pythonのプログラムの記述と実行を行うことにします。Anaconda Distributionのインストーラーは、次のURLから無償で入手できます。Windows版、macOS版、Linux版があります。
それでは、二分探索のアルゴリズムから始めましょう！
［1 基礎］ 二分探索。
最も基本的なアルゴリズムと言える「探索」の説明から始めましょう。
線形探索。
探索とは、複数のデータの中から特定のデータを探し出すことです。例えば、次のリストdataの中から「5」を探し出す方法を考えてみましょう。
すぐに思い付くのは、最初から順番に総当たりで探し出す方法です（図1）。このような探索のアルゴリズムは「線形探索」と呼ばれます。
線形探索はループとif文を使って簡単に実装できます。リスト1は線形探索のプログラム例です。実行すると、「4番目に発見」と表示されます。リストの添え字は0番目から始まるので、「5」の位置は4番目です。
リスト1では線形探索を行うlinear_search関数を定義しています。探索したいデータは変数keyで扱います。linear_search関数の中では、forループを使って、リストの先頭から末尾までの全データとkeyを順番にif文で比較しています。データの中にkeyと同じものが見つかれば、そのデータの添え字の値を返して関数を終了します。データの中にkeyが見つからなければ、-1を返して関数を終了します。
線形探索は単純なアルゴリズムなので、簡単に実装できます。半面、探索したいデータが末尾にある場合や、全データの中に探索したいデータがない場合は、データをすべてチェックしなければならないという効率の悪さがあります。リストdataには5個しかデータがないので、多くても5回のチェックで済みますが、例えばデータが100万個ある場合は、100万回のチェックが必要になる可能性があります。このように線形探索では、探索にかかる“最悪の時間”がデータの個数に正比例します。
二分探索。
探索にかかる最悪の時間を大幅に圧縮する探索のアルゴリズムが「二分探索」です。
たとえ話で二分探索の動きを説明してみます。ある人の誕生月を知りたいとしましょう。その時、「1月生まれですか？」「違います」「2月生まれですか？」「違います」「3月生まれですか？」…のように、1月から順番に尋ねる方法が考えられます。この方法はシンプルですが、最悪、11回も質問しなければなりません。これは、先ほどの線形探索的な方法と言えます。
一方で、二分探索的な方法があります。この方法では、初めに真ん中辺りの6月から「6月生まれですか？」と尋ねます。「それより後です」と言われたら、今度は「（7月から12月の真ん中辺りの）9月生まれですか？」と尋ねます。再び「それより後です」と言われたら、「（10月から12月の真ん中の）11月生まれですか？」と尋ねます。「それより前です」と言われたら、10月生まれであると判明します。この二分探索的な方法であれば、質問の回数は最悪3回で済みます。
先ほどのリストdataの中から、二分探索で「5」を探すことを考えましょう。二分探索ではデータがあらかじめ“ソート”されている必要があります。ソートとは、データを小さい順または大きい順に並び替えることです。ここでは小さい順にソートします。
5個のデータがあるので、探索は真ん中の6から始め、図2のように進みます。二分探索だと、データのチェックが最悪3回で済みます。
二分探索のプログラム例をリスト2に示します。基本的には、誕生月を尋ねる二分探索的な方法や図2で示した内容と同じことをPythonで記述しているだけです。実行すると、「1番目に発見」と表示されます。
二分探索を行っているのはbinary_search関数です。ポイントとなるのは、変数left、変数right、変数centerの3つで探索する範囲を管理している部分です。centerの値は次の計算で求めます。
そして、if文の「data[center] == key」がTrueになれば探索は完了なので、centerの値を返して関数を終了します。Falseの場合は、探索の範囲を狭めるために、leftまたはrightの値を変更して、centerの値も再計算し、再びif文の「data[center] == key」を評価します。
線形探索と二分探索を比較する。
線形探索と二分探索の性能の差を、100万個のデータを使って比較してみましょう。
まず、リスト3を実行して、ソートされた100万個のデータを持つリストdataを作ります。データは乱数で作成しています。
その後、Jupyter Notebookの「%%timeit」コマンドを利用して、線形探索のlinear_search関数と、二分探索のbinary_search関数の処理にかかる時間を計測し、比較しましょう。ただし、線形探索はデータがソートされていなくても使えますが、二分探索はデータがソートされていることが前提です。今回は、あらかじめソートされたデータを使うので、完全に公平な比較ではありません。
では、linear_search関数から計測します。次のコードを実行しましょう。最悪の時間を計測したいので、探索するデータはリストdataに存在しない、99999999にしておきます。
実行すると、筆者の環境では次のように表示されます（表示される数値は、環境によって異なります）。
linear_search関数の実行の完了には、約280ms（ミリ秒）かかることがわかりました。
続いて、binary_search関数の実行を計測します。
こちらは次の表示になりました。
binary_search関数の実行にかかる時間は約12.2μs（マイクロ秒）でした。1μs＝0.001msなので、12.2μs＝0.0122msです。約280msかかったlinear_search関数よりも桁違いに速いことがわかりました。
前述しましたが、線形探索では探索にかかる最悪の時間はデータの個数Nに正比例します。一方、二分探索では最悪の時間がlog2Nに沿ってしか増えません。よって、二分探索の方が圧倒的に高速なのです。
…といってもわかりにくいので、グラフを描いてみましょう。図3を見てください。赤が線形探索（y = N）のグラフで、青が二分探索（y = log2N）のグラフです。また、横軸はデータの個数で、縦軸は最悪の時間です。
図3を見ると、二分探索はデータの個数が増えたとしても、探索にかかる最悪の時間はあまり増えない、ということがわかります。
ここでlinear_search関数とbinary_search関数のソースコードを見比べてみましょう。前者は5行で、後者は空行を除くと12行です。binary_search関数はlinear_search関数の2.4倍の長さに過ぎません。しかし、図3のようにbinary_search関数の方が圧倒的に高速（効率的）です。つまり、binary_search関数は実装に費やした労力の割には性能が極めて良いのです。
このように、優れたアルゴリズムは、単純なアルゴリズムと比べて、圧倒的な性能を生み出すことが少なくありません。これが、アルゴリズムが重要である理由なのです。
