[プログラム演習]アルゴリズムの性能評価について

アルゴリズムの性能評価

この記事を読んでいる読者の方でアルゴリズムがなんたるかについてはっきりとした回答を持ち合わせていない者はいないと思うが、一般的にアルゴリズムの性能評価についての理解が十分とは言えないだろう。

アルゴリズムの性能評価とは、与えられた入力に対して正しい答え(問題の難易度によっては十分近いことが保証されている近似値でも構わない)を得るのに必要なコストを評価することである。

コストというのは最も一般的なのは「計算時間」についてであるが、問題によっては「メモリの使用容量」だったりする場合もある。

今回は「計算時間」という観点でのみアルゴリズムの性能評価を行いたいと思う。考えるまでもなく、同じ答えを出すのであれば計算時間が短い方がより良いアルゴリズムということができる。

性能の評価方法

さて、ある種の問題を解く必要がでてきてAさんとBさんがそれぞれ独自に別のアルゴリズムを考案したとしよう(ここでは例を考えるのが面倒だったのであえて省略する)

問題の規模にも依るが、最近のパソコンは極めて性能が高いので身の回りにあるような問題に対してはほとんど一瞬で正しい答えを返す。

でも実際には一瞬で答えを返せない難しい問題のほうが現実的には多いんよね。

なのでAさんとBさんのプログラムは走らせてみると実際にはほとんど同じ時間で答えをだすのでどちらがどのくらい性能が良いのかわかりかねるのである。

もちろん、問題の規模(三桁の掛け算を百桁の掛け算にするだけで難しくなるのは容易に理解できるだろう)を大きくすればそれに比例して計算時間は長くなるが、適当に数を大きくしてもアルゴリズムの正当な評価ができていなければどのくらい時間がかかるようになるのかは実際にやってみなければわからない。

あんまり数を大きくすると数時間かかってしまうかもしれないのである。

入力される数を大きくすると途端に計算時間が増える問題の例として有名なのが「素因数分解」であり、比較的小さな数(100,000程度)であれば総当り方でも現実的な時間で解を得られるが、数が大きくなるとスーパーコンピュータを使ったとしても数年・数十年かかるのである。

素因数分解の場合、最も時間がかかるのは「入力された数Nを整数kで試し割りする」という部分なので、ここが何回繰り返されたかで性能を評価するのが一般的である。

ここに比べたら「整数kを1増やす」などは0にも等しい計算時間なのである。

「素数判定」や「素因数分館」に対して全通り試し割りは愚直で悪いアルゴリズムであるが、少しばかり改良することで実生活で使うような数に対しては一瞬で答えをだすアルゴリズムにすることができる。

以下の記事で詳しく解説しているが、素数リストで割るように改良するだけで100,000,000以下の数に対しては20倍程度高速化できるのである。

このとき、全通りの試し割りは整数Nに対してN回の除算を行うので計算時間は、

と表すことができ、素数リストでの素数判定の計算時間はおよそ、

であることがわかる。このとき、素数リストはNの平方根を更にlog Nで除するのでNに比べてものすごく小さい数になっていることがご理解いただけるだろう。

計算複雑性理論における計算時間

さて、先述した素数判定や素因数分解における計算時間の評価は入力される数が決まった時点であらかじめ推定することがわかった。

しかし、現実には入力される数がいくらであるかはわからないのである。

例えば偶数に対しては高速に解を求められるが、奇数に対しては非常に時間がかかるアルゴリズムがあったとしよう。

このとき、このアルゴリズムは速いと言っていいのか遅いといっていいのかどちらだろうか?

ここでは仮に偶数であれば0秒、奇数であれば60秒で答えを返すとする。

最良の計算時間で評価する(0秒)

いわゆるいいとこどりというやつだが、これをする人は信用してはならない。

例えば1分間に10枚印刷できるプリンタを買ったが、それが中央に一文字だけ「あ」と印刷されたテストデータで計測されたもので、実際にたくさんの文字が書かれた文章を書かれたデータを印刷しようとしたら1分間に3枚しか印刷できなかったら「詐欺だ!」と文句の一つでも言いたくならないだろうか?

平均の計算時間で評価する(30秒)

偶数と奇数の濃度は等しいので、試行回数を繰り返せば “偏りのないデータ” であればほとんど同数入力されることが見込まれる。

ということは平均的に見れば1件あたり30秒で処理できるので、計算時間30秒と評価するわけである。

これは一般的にみて納得のいく解釈であるが、計算複雑性理論的に満足のいくものではない。

最悪の計算時間で評価する(60秒)

計算複雑性理論において最も一般的に使われるのは最悪の計算時間で評価することである。

最悪の場合の性能を提示できれば、性能保証という観点からも非常にわかりやすいからだ。

実はあまりあからさまに言いたくないが、最悪の場合の評価の解析というのは他の場合(例えば上述した平均的な場合)に比べて格段に優しいとう特徴があり、それゆえにわれわれの業界で好んで使われている。

(アルゴリズム・サイエンス:出口からの超入門)

最長増加部分列問題

最長増加部分列問題とは、与えられた入力(数列)に対して次第に増加していっている部分文字列の最大の長さを求める問題である。

10, 3, 2, 5, 8, 12, 6, 13, 9, 4

の数列があったとしよう。この数列を左から順に考えていくと以下のような増加部分列が存在する。

  • 2, 5
  • 3, 5
  • 2, 5, 8
  • 3, 5, 8
  • 2, 5, 6
  • 2, 5, 6, 9
  • 2, 5, 8, 12
  • 3, 5, 8, 12
  • 2, 5, 8, 12, 13
  • 3, 5, 8, 12, 13

もちろん、5, 8などの部分列もあるのだが、これは明らかに2, 5, 8や3, 5, 8の方が長いので考えなくても良い。

数列の順番を変えなければ、部分列として選択しなくていい数字があるのがポイントよね。

気をつけなければいけないのは2, 5, 6の部分列を見逃してしまうことだろう。つまり、「現在の部分列よりも大きい数が来たら追加する」というアルゴリズムではダメということですね。

最近の計算機は強力だから愚直に虱潰し法(exhaustive method)で十分かと考える人もいるかも知れないが、数列の長さが1000にもなれば「n番目を取るか取らないか」ということを考えると2の1000乗の組み合わせをチェックしなければいけない。

2のn乗というのは猛烈な速度で増加するのでn=100の時点でもはやまったく天文学的な数字になってしまうことは有名である。

練習問題

以下のRandomList.zipには長さ1000, 5000, 10000の数列がカンマ区切りで載せたテキストが入っています。

今回は全ての数字が異なるようにしてあります。

  1. 最長増加部分列の長さを求めるプログラムを書け
  2. 最長増加部分列の長さを求めよ
  3. そのアルゴリズムの性能を評価せよ

自分もまだ答えが出せていないのでチャレンジしてみようと思います。