実務の現場では、伝統的なアルゴリズムを実装することはほぼありません。しかし、大学などでプログラミングを学ぶとき、資格試験を目指すときなど、必ずといっていいほどアルゴリズムが登場します。その理由は、アルゴリズムや計算量についての考え方を知ることで、効率良いプログラムを開発することにつながるからです。
ポイントは「高速なプログラムを作成する」のではなく、「効率よく処理できる場合があることを知る」こと。今回は最近注目を集めているプログラミング言語Pythonと合わせて、アルゴリズムを学ぶときの考え方について紹介します。
Pythonが注目されている理由
最近、書店に行くと圧倒的に増えているのがPythonについての書籍です。プログラミング言語の人気ランキングなどを紹介しているTIOBEによると、2020年2月のランキングでPythonは第3位にランクインしています。
しかし、ソフトウェアを開発するときに使われる言語として、実行環境別に考えてみると、Pythonはいずれも一番手とは言えません。例えば、WebアプリであればPHPやJavaなどが主流ですし、デスクトップアプリではC#やVB.NETを使う、という人は多いでしょう。iPhoneアプリではObjective-CやSwift、AndroidアプリではJavaやKotlinが標準的です。また、組み込みではC言語やC++などが多く使われています。
そんななか、Pythonが注目されている理由として機械学習やディープラーニングといったAI(人工知能)関連が挙げられます。統計についての豊富なライブラリがあり、結果を可視化するのも簡単。多くの研究者が発表した論文に関連するソースコードがPythonで公開されているものが多いこともその理由として挙げられます。
また、基本情報技術者試験で2020年春期試験からCOBOLに替えてPythonが採用されたことや、Python 2系のサポート終了などの話題も重なったことも、注目を集めている理由でしょう。ここでは、Pythonを使って伝統的なアルゴリズムを少し紹介します。
計算量の考え方
アルゴリズムが求められる理由として、プログラムの処理効率が挙げられます。同じ問題を解く方法は複数存在しますが、その中でどのように処理すれば効率がよいのか、ということを考えてみます。
例えば、1から100までの和を求める場面を想像してみましょう。誰でも思いつくのは、1から順に足し合わせていく方法です。1から10くらいであれば暗算でも計算できますし、100くらいであればコンピュータでも一瞬です。しかし、上限が1万、1億、のように大きくなると処理に時間がかかります。このとき、等差数列の和の公式を知っていると、次の式のnに上限を当てはめるだけです。
この方法では、上限の値がいくつになっても一瞬で処理できます。このように、データ数が増えてもあまり処理時間が増えないアルゴリズムを「良いアルゴリズム」と考えます。
しかし、同じ処理でもコンピュータのCPUを変えると処理にかかる時間は変わりますし、プログラミング言語を変えても処理にかかる時間は変わります。そこで、アルゴリズムの処理にかかる時間を考える指標として計算量を考えます。
厳密な定義をすると説明が長くなってしまうので、ここではざっくりと計算量について紹介します。基本的には「ループの深さ」だと考えるとわかりやすいでしょう。例えば、次の3つのパターンを考えてみましょう。
それぞれ、forループが1重、2重、3重になっており、それぞれO(n)、O(n2)、O(n3)と書きます。これをオーダーと言い、O(n)をオーダーn、O(n2)をオーダーnの二乗、のように読みます。
オーダーを考えるときは、forループの中でどのような処理をするかを気にしないことがポイントです。上記では合計を出力しているだけですが、複雑な処理をしていても、ループの深さが同じであれば同じ計算量と考えます。これは、データ量が大幅に増えたときに、ループ内の処理がそれだけ繰り返されるだけであるため、定数倍だと考えられるからです。
また、二重ループと一重ループの両方の処理を行う場合、二重ループの方が処理に圧倒的な時間がかかるため、一重ループの部分は全体から考えると無視できます。そのため、ループが一番深いものだけを考えます。
このように、オーダーは数学における関数の形だと考えると良いでしょう。例えば、y=x、y=x2、y=logxのようなグラフを考えると、次のような形になります。ここでx軸がデータ量、y軸が処理時間だと考えると、その処理時間の増え方の違いがよくわかります。
探索（線形探索、二分探索）
リストに格納されているデータの中から目的の値を探すとき、リストの前から順に探すアルゴリズムを線形探索と言います。非常に単純なアルゴリズムですが、目的の値がリストの中に存在すれば確実に見つけられますし、リストの最後まで探索して見つからなければ「存在しない」ということもわかります。
線形探索をPythonで実装すると、次のように書けます。ここでは、リストに格納された値の中から「40」という値の位置を探しています。リストに見つからなかった場合は「-1」という値が求められます。
for i in range(len(data)):
if data[i] == value:
return i
return -1
data = [50, 30, 90, 10, 20, 70, 60, 40, 80]
print(linear_search(data, 40))
これは一重のループのため、O(n) のアルゴリズムです。
線形探索は実装が簡単なアルゴリズムですが、データ量が多くなると処理に時間がかかります。そこで、もっと効率よく探索する方法を考えます。1つの方法として、探索範囲を絞り込みながら探索する二分探索があります。二分探索では、データを事前に並べ替えておく必要はありますが、効率よく求められます。
left = 0
right = len(data) - 1
while left <= right:
mid = (left + right) // 2
if data[mid] == value:
return mid ←中央の値と一致した場合は位置を返す
left = mid + 1 ←中央の値より大きい場合は探索範囲の左を変える
right = mid - 1 ←中央の値より小さい場合は探索範囲の右を変える
data = [10, 20, 30, 40, 50, 60, 70, 80, 90]
print(binary_search(data, 90))
これは1度比較する度に探索範囲が半分になるため、O(logn)のアルゴリズムです。上記のグラフを見てわかるように、線形探索と比べるとデータ数が増えたときに圧倒的に高速に求められます。
ソート（並べ替え）の比較
二分探索をするには、データを並べ替えておく必要がありました。つまり、二分探索がいくら高速でも、並べ替えに時間がかかるのであれば意味がありません。そこで、並べ替えを高速に行なう方法を考えます。このような並べ替えのことをソートと言います。
直感的にわかりやすいソート方法として、選択ソートがあります。これは、リストの中から最も小さいデータを選んで先頭に移動させることを繰り返す方法です。これをリストの最後の要素まで繰り返すと、並べ替えが完了します。
これは「先頭から最後の要素まで繰り返す」処理と、「最小値の位置を探す」処理の2つに分けて考えられます。それぞれについてループすると、次のような2重のループで実装できます（外側のループが「先頭から最後の要素まで繰り返す」処理、内側のループが「最小値の位置を探す」処理）。
for i in range(len(data)):
min = i ←最小値の位置をセット
for j in range(i + 1, len(data)):
if data[min] > data[j]:
min = j ←最小値が更新されたらその位置をセット
data[i], data[min] = data[min], data[i]
print(data)
このように単純な2重ループなので、計算量はO(n2)です。これは、データ量が増えたときに処理時間が大幅に増加することを意味しています。
次に、高速に処理できる例としてクイックソートを紹介します。クイックソートは基準となる要素で分割することを繰り返して並べ替える方法です。ここでは、分割するリスト内の先頭の要素を基準として使うことにします。
例えば、下の図の場合、最初は全体のリストに対して先頭の「6」よりも小さな要素と大きな要素に分割します。さらに、分割したそれぞれのリストについて、先頭の要素「4」と「15」で分割する、ということを繰り返します。
上記を見ると、ただ分割していくだけで、一番下のようにソートされた状態になっていることがわかります。この処理は、次のように再帰的なプログラムで実装できます。
def quick_sort(data):
if len(data) <= 1:
return data
pivot = data[0]
left = [i for i in data[1:] if i <= pivot]
right = [i for i in data[1:] if i > pivot]
left = quick_sort(left) ←左側をソート
right = quick_sort(right) ←右側をソート
return left + [pivot] + right
print(quick_sort(data))
これはO(nlogn)のアルゴリズムとして知られています。他にもさまざまなソートアルゴリズムがありますが、実際に処理してみると、次の表のような結果になりました。
これをみると、選択ソートなどと比較し、クイックソートは圧倒的に高速に処理できていることがわかります。また、上記で解説した方法よりも、Pythonで用意されているソート(リストに対するsortメソッド)が圧倒的に高速なことがわかります。
これは、Pythonがインタプリタで動作するのに対し、Pythonで用意されているソートは事前にコンパイルされたものが実行されることによるものです。このため、普段仕事で使う場合は用意されたものを使うようにしましょう。
その他のアルゴリズムについて知りたい方は、『Pythonではじめるアルゴリズム入門』で詳しく紹介していますので、合わせて読んでみてください。
アルゴリズムは「考え方」が重要
上記のクイックソートのようなアルゴリズムは思いつかない、という人が多いでしょう。しかし、これらを思いつく必要はありません。選択ソートのように前から順に処理するのではなく、基準となる値を使って分割することで効率よく処理する方法があるのだ、ということを「知っておく」ことが大切なのです。
実際の業務においても、高度なアルゴリズムが求められる場面はあまりありません。しかし、線形探索と二分探索、選択ソートとクイックソートのように解き方は複数存在し、その背景にある考え方を知っておくと、処理にかかる時間がある程度予測できたり、既存の処理を改善できたりします。
普段の業務では既存のライブラリを使いますが、一度くらいは伝統的なアルゴリズムを実装してみて、その処理時間の違いを体験してみてください。
