Boost」など、さまざまなカンファレンスを企画・運営しています。BOOKS(コードジン・ブックス)は、CodeZineの連載からカットアップした、開発現場の課題解決に役立つ書籍シリーズです。07:00Pythonアルゴリズムポストプログラムを軽く効率的にするために不可欠なアルゴリズム。翔泳社から発売中の『Pythonではじめるアルゴリズム入門』では、人気が高くユーザーも増えているPythonを用い、探索やソートなど基本的なアルゴリズムを解説しています。CodeZineでは以前、線形探索と選択ソートを紹介しましたが、今回は新たに二分探索とバブルソートを紹介します。伝統的なアルゴリズムで学ぶ定石と計算量』から「二分探索」と「バブルソート」を抜粋したものです。比べて処理時間が大幅に短くなることを体感する。事前にソートが必要なことを理解する。探索範囲を半分に分けるデータ数が増えても高速に処理する方法を考えると、私たちが辞書や電話帳から探すときに似た方法が考えられます。ある値を見たときに、目的の値がそれよりも前か後ろかを判断する方法です。この方法を使うには、データが五十音順など規則的に並んでいる必要があります。ここでは、次のようなリストにデータが昇順で格納されているとします。90]ここから40という値を探してみます(図4.2)。最初に中央の値50と比較すると、40はこれより小さいため、前半を探せばよくなります。次は10、20、30、40の中央にある20と比較します。すると、今度は20よりも大きいため、後半を探します。次は30と比較し、後半を探します。その後40と比較して一致すると、ここで探索は終了となります。このように、探索範囲を前か後ろの半分に区切って探索することを繰り返します。今回は比較した回数が4回でした。二分探索このように、データが昇順に並んでいる中から、目的のデータが真ん中より右にあるか左にあるかを調べる作業を繰り返します。実際にPythonのプログラムで実装してみましょう(リスト4.3)。リストの左端と右端から、探す位置を半分に絞り込みながら順に探索します。binary_search.py8C:¥>ここでは、leftとrightという2つの変数を使って、範囲を絞り込んでいます。一致したときにはその位置を返し、一致しなかったときにはleftとrightの値を再設定しています。データが増えたときの比較回数を考える一見すると複雑な処理を行なっているように見えますが、図4.2を見ると探索範囲がどんどん絞られていくことがわかります。この効果は、データの数が増えたときの比較回数に現れます。一度比較すると探索範囲が半分になる、ということは、リストに含まれるデータ数が2倍になっても最大の比較回数は1回増えるだけです。これは、数学の対数の考え方が使えます。対数は指数の逆の考え方で、たとえばy=2xからxを求める式はx=log2yと定義されています。指数は第3章でも登場したように、右肩の値が増加すると急激に大きくなります。21=2、22=4、23=8と増えていき、210=1,024、216=65,536となります。一方の対数はlog22=1、log24=2、log28=3となり、log21,024=10、log265,536=16のようにlogの中が増えても大きく変わりません。実際、y=xのグラフとy=log2xのグラフを描いてみると、図4.3のようになります。y=log2xはy=2xのグラフと、y=xで線対称であり、xの値が増えてもyの値はあまり増えないことがわかります。二分探索の場合、比較回数の増え方は対数のペースであるため、データ数が1,000個程度に増えても比較回数は10回程度、100万個に増えても比較回数は20回程度です。線形探索だと1,000個になると1,000回、100万個になると100万回かかっていたものと比べると図4.3のように圧倒的な差が生まれることがわかります。O(n)やO(n2)で定数倍を無視するのと同じように、対数の底の違いは無視できます。このため、オーダーを書くときは底を省略することが一般的で、二分探索はO(logn)と表現できます。対数関数のグラフ一般的には、線形探索よりも二分探索のほうが高速に処理できますが、データが昇順か降順に並んでいる必要があるため、事前にデータの並べ替えが必要です(線形探索の場合には並び順は関係ない)。データの個数が少ない場合には処理速度に大きな差が出ないことから、線形探索が使われることも少なくありません。扱うデータの量やデータの更新頻度なども検討した上で、探索方法を決めることが必要です。人が使うのにも役立つ二分探索プログラミングでコンピュータの処理を効率化することに限らず、二分探索の考え方が役に立つことは少なくありません。プログラムの出力が正しくないとき、その原因となる場所を探す必要があります。このような場合、ソースコードを前から順番に探していってもよいですが、二分探索を使うと、調べる範囲を少しずつ絞り込むことができます。ある関数の上半分を削除してみて結果を確認、次に下半分を削除してみて結果を確認する、ということを繰り返すと、問題点が見えてくることがあります。これはプログラミングに限らず、ネットワークの調査などでも同じです。多くのサーバーを管理している場合は、問題が発生しているサーバーがどこにあるか調べるのに、半分ずつ調べる方法なども考えられます。スキップリストこの節ではリスト(配列)に対する二分探索を紹介しましたが、実際にはソートされた連結リストに対して高速に探索したい場合もあります。連結リストは前から順にたどる構造のため、単純には二分探索はできません。そこで、連結リストのデータ構造を工夫したものに「スキップリスト」があります。電車で各駅停車以外に急行や特急があるように、順にたどるのではなく、一部を読み飛ばせるデータ構造です(図4.4)。スキップリストを使うと、連結リストでも効率よく探索できます。挿入や削除なども余分に実装しなければなりませんが、便利なデータ構造として知っておきましょう。スキップリストバブルソートバブルソートの処理手順を理解し、実装できるようになる。バブルソートの計算量を理解する。隣同士で交換する選択ソートも挿入ソートも、リストの要素を交換しながら処理しています。このため、「交換ソート」と呼べなくもありませんが、一般的に「交換ソート」というときは「バブルソート」のことを指します。バブルソートは、リストの隣り合ったデータを比較して、大小の順序が違っているときは並べ替えていく方法です(図5.5)。データが移動していく様子を、水中で泡が浮かんでいく様子に例えて、バブルソートという名前が付けられています。リストの先頭と次のデータからはじめて、左のほうが大きければ右と交換することを、1つずつずらしながら繰り返します。リストの最後尾まで到達すると、1回目の比較は終了です。バブルソートこのとき、リストの最後尾にはデータの最大値が入ります。2回目は一番右端を除いて同様の比較を行なうと、最後から2番目が決まります。これを繰り返すと、すべてが並べ替えられ、ソートは終了です。バブルソートの実装これをPythonで実装すると、リスト5.4のように書けます。15]C:¥>バブルソートは、1回目にn‒1回の比較・交換を行ないます。2回目には、n‒2回の比較・交換を行ないます。このため、比較・交換の回数は、(n‒1)+(n‒2)+...+1=n(n‒1)/2と計算できます(これは選択ソート、挿入ソートと同様)。この回数は、入力データがどのような並び順であっても同じです。入力されたデータが事前に並んでいると交換は発生しませんが、比較は同じだけの回数を行なわなければなりません。上記のように実装すると、計算時間はデータの並び順にかかわらず常にO(n2)です。バブルソートの改良バブルソートで変更が発生しなかった場合に処理を打ち切り、高速化することを考えます。処理中に交換が起こったかどうかを記録し、交換が起こらなかった場合はそれ以降の処理を行なわないものとします。リスト5.5では、交換が発生したかどうかを保存するchangeという変数を用意しています。交換が発生しているとchangeにTrueという値を、発生していない場合はFalseという値をセットしています。交換が発生しなかった場合は、ループを抜けて処理を終了しています。交換が発生したprint(data)このように改良すると、ソート済みのデータが与えられた場合は外側のループを一度だけ処理して終了するため、計算時間がO(n)となります。一般的にはソート済みのデータが与えられることは少なく、最悪時間計算量がO(n2)であることは変わりません。本書について本書は、初心者にも扱いやすいプログラミング言語「Python」を使用して、アルゴリズムの基礎・考え方を学ぶ入門書です。Pythonがはじめてという方のために、第1章ではPythonの基本とデータ構造について解説しています。