Loading article…
コンピュータ科学 において、アルゴリズム効率とは、アルゴリズムが使用する計算リソースの量に関連するアルゴリズムの特性である。アルゴリズム効率は、反復的または連続的なプロセスにおける生産性の向上に類似していると考えることができる。
効率を最大限に高めるには、リソースの使用量を最小限に抑えることが望ましい。しかし、時間計算量や空間計算量といった異なるリソースは直接比較できないため、どちらのアルゴリズムがより効率的かは、どの効率性の指標を最も重要視するかによって決まることが多い。
例えば、サイクルソートとティムソートはどちらも、項目のリストを小さい順に並べ替えるアルゴリズムです。サイクルソートは、要素数の二乗に比例する時間でリストを整理します（（ビッグO記法を参照）ですが、元の配列への書き込みを最小限に抑え、リストの長さに対して一定の少量の追加メモリしか必要としません（Timsort はリストの長さに比例した時間 (ある量とその対数の積に比例) でリストをソートします()、ただしリストの長さに比例するスペース要件があります(特定のアプリケーションで大きなリストを高速にソートする必要がある場合は、timsort の方が適しています。ただし、ソートのプログラム/消去 サイクルとメモリ使用量を最小限に抑えることがより重要な場合は、サイクルソートの方が適しています。
時間効率の重要性は、 1843年にエイダ・ラブレスによって、チャールズ・バベッジの機械式解析機関に適用された際に強調された。
「ほぼすべての計算において、プロセスの順序付けにはさまざまな構成が可能であり、計算エンジンの目的のために、それらの選択にはさまざまな考慮事項が影響する。重要な目的の1つは、計算を完了するために必要な時間を最小限に抑えるような構成を選択することである」[ 1 ]
初期の電子計算機は、処理速度とランダムアクセスメモリ容量の両方に限界があった。そのため、処理時間と空間のトレードオフが生じた。タスクによっては、多くのメモリを使用する高速アルゴリズムを使用するか、少ないメモリを使用する低速アルゴリズムを使用するかのどちらかを選択する必要があった。したがって、エンジニアリング上のトレードオフは、利用可能なメモリに収まる最速のアルゴリズムを使用することであった。
現代のコンピュータは初期のコンピュータよりもはるかに高速で、利用可能なメモリ容量もはるかに大きい（キロバイトではなくギガバイト）。しかしながら、ドナルド・クヌースは効率性も依然として重要な考慮事項であると強調した。
「確立された工学分野では、容易に達成できる12%の改善は決して些細なものとは見なされず、ソフトウェア工学においても同じ見解が主流となるべきだと私は信じています」[ 2 ]
AIの時代において、LLMは動作するコードを生成できるものの、リソース制約のあるアプリケーションや時間制約のあるアプリケーションで要求されるパフォーマンス基準を満たさないことが多く[ 3 ]、コードの効率性が実世界での展開における重要なボトルネックとなっている。
アルゴリズムは、リソース消費量（計算コストとも呼ばれる）が許容レベル以下であれば効率的であるとみなされます。大まかに言えば、「許容レベル」とは、入力データのサイズに応じて、利用可能なコンピュータ上で妥当な時間またはメモリ容量で実行できることを意味します。 1950年代以降、コンピュータの計算能力とメモリ容量は劇的に増加しており、現在の許容レベルは10年前でさえ許容できないレベルでした。実際、コンピュータの処理能力が約2年ごとに倍増しているおかげで、現代のスマートフォンや組み込みシステムでは許容できる効率性を持つタスクでも、10年前の産業用サーバーでは許容できないほど非効率だった可能性があります。
コンピュータメーカーは頻繁に新モデルを発表し、多くの場合、性能が向上しています。ソフトウェアのコストはかなり高額になる場合があるため、既存のコンピュータと互換性がある限り、より高速なコンピュータを購入するのが、性能向上を実現する最も簡単で安価な方法となる場合もあります。
アルゴリズムが使用するリソースを測定する方法は数多くあります。最も一般的な測定方法は速度とメモリ使用量ですが、その他にも伝送速度、一時ディスク使用量、長期ディスク使用量、消費電力、総所有コスト、外部刺激に対する応答時間などが測定対象となります。これらの測定方法の多くは、アルゴリズムへの入力サイズ、つまり処理するデータ量に依存します。また、データの並び方にも依存する場合があります。例えば、一部のソートアルゴリズムは、既にソート済みのデータや逆順にソートされたデータに対しては性能が低下します。
実際には、アルゴリズムの効率に影響を与える要因は他にもあり、例えば精度や信頼性に関する要件などが挙げられます。後述するように、アルゴリズムの実装方法も実際の効率に大きな影響を与える可能性がありますが、その多くは最適化の問題に関連しています。
アルゴリズムの理論解析では、通常、漸近的な意味でその複雑さを推定します。リソース消費量、つまり「複雑さ」を表す最も一般的な表記法は、ドナルド・クヌースのビッグオー記法であり、入力サイズの関数としてアルゴリズムの複雑さを表します。ビッグオー記法は関数の複雑さの漸近的な尺度であり、おおよそ、アルゴリズムに必要な時間は比例することを意味しますより低い次数項を省略すると、関数の成長としては任意に大きくなる。この推定は、次のような場合に誤解を招く可能性がある。小さいが、一般的には十分な精度がある表記法が漸近的であるため、サイズが大きくなります。たとえば、少数の項目をソートする場合、バブルソートはマージソートよりも高速になる可能性があります。ただし、どちらの実装も、小さなリストのパフォーマンス要件を満たす可能性が高いです。通常、プログラマーは大きな入力サイズに効率的に拡張できるアルゴリズムに関心があり、ほとんどのデータ集約型プログラムで遭遇する長さのリストでは、バブルソートよりもマージソートが好まれます。
アルゴリズムの漸近的な時間計算量にビッグオー記法を適用した例をいくつか挙げます。
ソフトウェアの新バージョンや競合システムとの比較のために、アルゴリズムの相対的なパフォーマンスを評価するのに役立つベンチマークが使用されることがあります。たとえば、新しいソートアルゴリズムが開発された場合、機能的な改善点を考慮に入れつつ、少なくとも既知のデータに対して以前と同等の効率性があることを、以前のアルゴリズムと比較することができます。ベンチマークは、顧客がさまざまなサプライヤーの製品を比較し、機能とパフォーマンスの面でどの製品が特定の要件に最適かを推定する際にも使用できます。たとえば、メインフレームの世界では、 Syncsortなどの独立系ソフトウェア企業の独自ソート製品が、 IBMなどの大手サプライヤーの製品と速度面で競合しています。
いくつかのベンチマークは、さまざまなコンパイル言語とインタプリタ言語の相対的な速度を比較する分析を行う機会を提供します。たとえば、[ 4 ] [ 5 ] やComputer Language Benchmarks Gameは、いくつかのプログラミング言語での典型的なプログラミング問題の実装のパフォーマンスを比較します。
自分でベンチマークを作成するだけでも、さまざまなユーザー指定の基準を使用して、異なるプログラミング言語の相対的なパフォーマンスを実証できます。これは非常に簡単で、Christopher W. Cowell-Shah による「9 つの言語のパフォーマンス比較」が例で示しています。[ 6 ]
実装上の問題も効率に影響を与える可能性があります。例えば、プログラミング言語の選択、アルゴリズムの実際のコーディング方法[ 7 ] 、特定の言語のコンパイラの選択、使用されるコンパイルオプション、さらには使用されているオペレーティングシステムなどです。多くの場合、インタプリタによって実装された言語は、コンパイラによって実装された言語よりもはるかに遅くなる可能性があります。[ 4 ]ジャストインタイムコンパイルとインタプリタ言語に関する記事を参照してください。
時間や空間の問題に影響を与える可能性のある他の要因もありますが、それらはプログラマの制御範囲外である可能性があります。これらには、データのアライメント、データの粒度、キャッシュの局所性、キャッシュの一貫性、ガベージコレクション、命令レベルの並列性、マルチスレッド（ハードウェアレベルまたはソフトウェアレベル）、同時マルチタスク、サブルーチン呼び出しなどが含まれます。[ 8 ]
一部のプロセッサはベクトル処理機能を備えており、単一の命令で複数のオペランドを操作できます。プログラマやコンパイラがこれらの機能を使用するのは容易な場合もあれば、そうでない場合もあります。逐次処理用に設計されたアルゴリズムは、並列処理を利用するために完全に再設計する必要がある場合もあれば、簡単に再構成できる場合もあります。 2010年代後半に並列および分散コンピューティングの重要性が高まるにつれて、 CUDA、TensorFlow、Hadoop、OpenMP、MPIなどの並列および分散コンピューティングシステム向けの効率的な高レベルAPIへの投資が増えています。
プログラミングにおいて発生する可能性のあるもう1つの問題は、同じ命令セット（x86-64やARMなど）と互換性のあるプロセッサでも、命令の実装方法が異なる場合があることです。そのため、あるモデルでは比較的高速な命令が、別のモデルでは比較的低速になることがあります。これは、最適化コンパイラにとってしばしば課題となります。コンパイラは、コンパイル対象で使用可能な特定のCPUやその他のハードウェアに関する広範な知識を持ち、プログラムのパフォーマンスを最適に最適化する必要があるからです。極端な場合、コンパイラはコンパイル対象プラットフォームでサポートされていない命令をエミュレートせざるを得ず、他のプラットフォームではネイティブにサポートされていてハードウェア効率が良い場合でも、そのプラットフォームでは計算できない結果を生成するために、コードを生成したり、外部ライブラリ呼び出しをリンクしたりする必要が生じる場合があります。これは、組み込みシステムにおける浮動小数点演算でよく見られるケースです。小型で低消費電力のマイクロコントローラは、浮動小数点演算のハードウェアサポートが不足していることが多く、そのため、浮動小数点演算を行うには計算コストの高いソフトウェアルーチンが必要になります。
測定値は通常、入力サイズの関数として表される。。
最も一般的な2つの対策は以下のとおりです。
バッテリー駆動のコンピュータ（ノートパソコンやスマートフォンなど）や、非常に長時間の大規模な計算（スーパーコンピュータなど）の場合、他に注目すべき指標は以下のとおりです。
2018年現在電力消費量は、組み込みIoTデバイスからシステムオンチップデバイス、サーバーファームに至るまで、あらゆる種類と規模の計算タスクにおいて重要な指標として増加しています。この傾向はしばしばグリーンコンピューティングと呼ばれます。
計算効率に関するあまり一般的ではない指標も、場合によっては関連性があるかもしれない。
アルゴリズムの解析は、通常、時間計算量などの概念を用いて、入力データのサイズに応じて実行時間を推定するために使用できます。結果は通常、ビッグオー記法で表されます。これは、特に大量のデータを処理する場合に、アルゴリズムを比較するのに役立ちます。データ量が少ない場合は、アルゴリズムのパフォーマンスを比較するために、より詳細な推定が必要になりますが、これはあまり重要ではないでしょう。並列アルゴリズムの解析は、より困難になる可能性があります。
ベンチマークは、アルゴリズムの実際のパフォーマンスを評価するために使用できます。多くのプログラミング言語には、CPU使用時間を提供する関数が用意されています。実行時間の長いアルゴリズムの場合は、経過時間も参考になります。結果は一般的に、複数のテストの平均値を用いるべきです。
実行ベースのプロファイリングは、ハードウェア構成や、マルチプロセッシングおよびマルチプログラミング環境において他のプログラムやタスクが同時に実行される可能性に非常に敏感です。
この種のテストは、特定のプログラミング言語、コンパイラ、およびコンパイラオプションの選択に大きく依存するため、比較対象となるアルゴリズムはすべて同じ条件下で実装されなければならない。
このセクションでは、アルゴリズムの実行中にメモリリソース（レジスタ、キャッシュ、RAM、仮想メモリ、二次記憶装置）がどのように使用されるかについて説明します。上記の時間解析と同様に、アルゴリズムを分析し、通常は空間計算量解析を使用して、入力データのサイズに応じて実行時に必要なメモリ量を推定します。結果は通常、ビッグオー記法で表されます。
メモリ使用量に関して考慮すべき点は最大で4つあります。
初期の電子計算機や家庭用コンピュータは、比較的少量のメモリしか搭載していませんでした。例えば、1949年の電子遅延記憶自動計算機（EDSAC）の最大メモリ容量は1024ワード（17ビット）でしたが、1980年のシンクレアZX80は当初1024バイト（8ビット）のメモリを搭載していました。2010年代後半になると、パーソナルコンピュータのRAM容量は4～32GBが一般的となり、メモリ容量は3億倍以上に増加しました。
現代のコンピュータは比較的大きなメモリ容量（場合によってはギガバイト単位）を持つことができるため、限られたメモリ容量にアルゴリズムを詰め込むことは、かつてのような問題ではなくなりました。しかし、メモリの種類とそのアクセス速度の違いは、大きな影響を与える可能性があります。
キャッシュメモリに収まるメモリ要件を持つアルゴリズムは、メインメモリに収まるアルゴリズムよりもはるかに高速であり、メインメモリに収まるアルゴリズムは、ページングに頼らざるを得ないアルゴリズムよりもはるかに高速です。このため、キャッシュ置換ポリシーは、キャッシュを考慮したプログラミングやデータアライメントと同様に、高性能コンピューティングにおいて非常に重要です。さらに問題を複雑にしているのは、システムによっては、実効速度が異なる最大3レベルのキャッシュメモリを備えている場合があることです。システムによってこれらの様々な種類のメモリの容量が異なるため、アルゴリズムのメモリ要件の影響はシステムごとに大きく異なる可能性があります。
電子計算機の黎明期には、アルゴリズムとそのデータがメインメモリに収まらない場合、そのアルゴリズムは使用できませんでした。現在では、仮想メモリの使用によりメモリ容量が大幅に増加しましたが、その代償としてパフォーマンスが低下します。アルゴリズムとそのデータがキャッシュメモリに収まる場合は、はるかに高速な処理が可能になります。この場合、メモリ容量を最小限に抑えることで、処理時間も最小限に抑えることができます。これは局所性の原理と呼ばれ、参照の局所性、空間的局所性、時間的局所性に細分化できます。キャッシュメモリに完全に収まらないアルゴリズムでも、参照の局所性を示すものであれば、十分に良好なパフォーマンスを発揮する可能性があります。
