実測の問題点
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/13 15:58 UTC 版)
アルゴリズムはプラットフォームに依存しない（すなわち、アルゴリズムは任意のオペレーティングシステムが動作する任意のコンピュータ上で任意のプログラミング言語で実装できる）ので、複数のアルゴリズムの性能を比較するのに経験的技法（実測値）を用いるのはあまりにも問題が多い。 例として、大きさ n のソートされたリストから特定のエントリを検索するプログラムを考える。そして、最新型の高性能なコンピュータAでは線型探索アルゴリズムでプログラムを実装し、古い低性能なコンピュータBでは二分探索アルゴリズムでプログラムを実装したとする。それら2つのコンピュータでそれぞれのプログラムのベンチマークテストを実施し、次のような結果が得られたとする。 n（リストの大きさ）コンピュータAの実行時間（ナノ秒単位）コンピュータBの実行時間（ナノ秒単位）15 7 100,000 65 32 150,000 250 125 200,000 1,000 500 250,000 この測定結果を見ると、コンピュータAで実行したアルゴリズムの方がコンピュータBのそれよりも遥かに高速だと結論しそうになる。しかし、入力リストの大きさを十分大きくすると、その結論は全くの間違いだったことが判明する。 n（リストの大きさ）コンピュータAの実行時間（ナノ秒単位）コンピュータBの実行時間（ナノ秒単位）15 7 100,000 65 32 150,000 250 125 200,000 1,000 500 250,000 ... ... ... 1,000,000 500,000 500,000 4,000,000 2,000,000 550,000 16,000,000 8,000,000 600,000 ... ... ... 63,072 × 1012 31,536 × 1012 ナノ秒、または1年 1,375,000 ナノ秒,または 1.375 ミリ秒 線型探索プログラムを実行したコンピュータAでの成長率（実行時間の増加率）は線型性を示す。すなわち、そのプログラムの実行時間は入力サイズに比例している。入力サイズが2倍になれば実行時間も2倍になり、入力サイズが4倍になれば実行時間も4倍になる、という具合である。一方コンピュータBでは二分探索プログラムを実行したので、成長率は対数的になる。入力サイズが2倍になったとき、実行時間の増加は一定である（この例では25,000ナノ秒）。表面上コンピュータAの方が高速でも、コンピュータBの方が成長率が低い（遅い）ので、入力サイズが大きくなれば必然的にコンピュータBの方が勝つことになる。
※この「実測の問題点」の解説は、「アルゴリズム解析」の解説の一部です。
「実測の問題点」を含む「アルゴリズム解析」の記事については、「アルゴリズム解析」の概要を参照ください。
- 実測の問題点のページへのリンク
