アルゴリズムの効率

コンピュータ サイエンス では、アルゴリズムの効率とは、アルゴリズムが使用する計算リソースの量に関連するアルゴリズムの特性です。アルゴリズムの効率は、反復プロセスまたは継続プロセスのエンジニアリング生産性に類似したものと考えることができます。

効率を最大化するには、リソースの使用を最小限に抑えることが望ましいです。ただし、時間や空間の複雑さなどのさまざまなリソースを直接比較することはできないため、2 つのアルゴリズムのどちらがより効率的であるかは、効率のどの尺度が最も重要であるかによって決まることがよくあります。

たとえば、バブル ソートとティムソートはどちらも、項目のリストを最小から最大の順にソートするアルゴリズムです。バブル ソートでは、要素数の 2 乗に比例した時間でリストが整理されます ( 、Big O 表記法を参照)。ただし、必要な追加メモリはリストの長さに対して一定で、少量のみです ( )。ティムソートでは、リストの長さに比例した時間(ある量とその対数の積に比例) でリストがソートされます( )。ただし、必要な領域はリストの長さに比例します ( )。特定のアプリケーションで大きなリストを高速にソートする必要がある場合は、ティムソートの方が適しています。ただし、ソートのメモリ使用量を最小限に抑えることの方が重要な場合は、バブル ソートの方が適しています。 ${\textstyle O(n^{2})}$${\textstyle O(1)}$${\textstyle O(n\log n)}$${\textstyle O(n)}$

時間に関する効率の重要性は、 1843 年にチャールズ バベッジの機械解析エンジン に適用されたエイダ ラブレスによって強調されました。

「ほとんどすべての計算において、プロセスの連続性にはさまざまな配置が可能であり、計算エンジンの目的に応じてさまざまな考慮事項がそれらの選択に影響を与える必要があります。重要な目的の 1 つは、計算を完了するために必要な時間を最小限に抑える配置を選択することです。」^[1]

初期の電子コンピュータは、速度とランダム アクセス メモリの両方に限界がありました。そのため、空間と時間のトレードオフが発生しました。タスクでは、大量のメモリを使用する高速アルゴリズムを使用することも、メモリをほとんど使用しない低速アルゴリズムを使用することもできます。したがって、エンジニアリング上のトレードオフは、使用可能なメモリに収まる最速のアルゴリズムを使用することでした。

現代のコンピュータは初期のコンピュータに比べて大幅に高速化しており、利用可能なメモリ量もはるかに多くなっています (キロバイトではなくギガバイト)。それでも、ドナルド・クヌースは、効率は依然として重要な考慮事項であると強調しました。

「確立されたエンジニアリング分野では、簡単に得られる12％の改善は決して限界とはみなされず、ソフトウェアエンジニアリングでも同じ視点が優先されるべきだと私は信じています。」^[2]

アルゴリズムが効率的であるとは、そのリソース消費量 (計算コストとも呼ばれる) が許容レベル以下である場合に考えられます。大まかに言えば、「許容できる」とは、利用可能なコンピュータ上で、通常は入力のサイズに応じて、妥当な時間またはスペースで実行されることを意味します。1950 年代以降、コンピュータでは利用可能な計算能力と利用可能なメモリ量の両方が劇的に増加したため、現在の許容レベルは 10 年前でさえ許容できなかったでしょう。実際、コンピュータの能力は 2 年ごとにほぼ 2 倍になっているため、現代のスマートフォンや組み込みシステムでは許容できるほど効率的なタスクが、10 年前は産業用サーバーでは許容できないほど非効率的だった可能性があります。

コンピュータメーカーは、より高性能な新モデルを頻繁に発売しています。ソフトウェアのコストは非常に高額になる可能性があるため、既存のコンピュータと互換性があれば、より高速なコンピュータを購入するのが、より高性能を得る最も簡単で安価な方法となる場合があります。

アルゴリズムが使用するリソースを測定する方法は多数あります。最も一般的な 2 つの測定基準は速度とメモリ使用量です。その他の測定基準には、伝送速度、一時ディスク使用量、長期ディスク使用量、電力消費、総所有コスト、外部刺激に対する応答時間などがあります。これらの測定基準の多くは、アルゴリズムへの入力のサイズ、つまり処理されるデータの量に依存します。また、データの配置方法に依存する場合もあります。たとえば、一部のソート アルゴリズムは、すでにソートされているデータや逆順にソートされたデータに対してはパフォーマンスが低下します。

実際には、精度や信頼性の要件など、アルゴリズムの効率に影響を与える要因は他にもあります。以下に詳述するように、アルゴリズムの実装方法も実際の効率に大きな影響を与える可能性がありますが、その多くは最適化の問題に関連しています。

アルゴリズム の理論的分析では、通常、漸近的な意味でその複雑さを推定します。リソース消費または「複雑さ」を記述するために最も一般的に使用される表記法は、ドナルド・クヌースのBig O 表記法で、アルゴリズムの複雑さを入力 のサイズの関数として表します。Big O 表記法は関数の複雑さの漸近的な尺度であり、おおよそ は、アルゴリズムの時間要件が に比例することを意味し、 が任意に大きくなるにつれて関数の増加によりも小さい寄与をする低次の項は省略されます。 が小さい場合、この推定値は誤解を招く可能性がありますが、 が大きい場合は表記法が漸近的であるため、一般に十分に正確です。たとえば、ソートする項目が少数の場合、バブルソートはマージソートよりも高速ですが、どちらの実装でも小さなリストのパフォーマンス要件を満たす可能性があります。通常、プログラマーは大きな入力サイズに効率的に拡張できるアルゴリズムに関心があり、ほとんどのデータ集約型プログラムで見られる長さのリストでは、バブルソートよりもマージソートが好まれます。 ${\textstyle n}$${\textstyle f(n)=O{\bigl (}g(n){\bigr )}}$${\displaystyle g(n)}$${\displaystyle g(n)}$${\textstyle n}$ ${\textstyle n}$${\textstyle n}$

アルゴリズムの漸近的時間計算量に適用された Big O 表記法の例には次のものがあります。

ソフトウェアの新バージョンや競合システムとの比較のために、ベンチマークが使用されることがあります。ベンチマークは、アルゴリズムの相対的なパフォーマンスを測定するのに役立ちます。たとえば、新しいソート アルゴリズムが作成された場合には、機能の改善を考慮に入れた上で、少なくとも既知のデータでは以前と同様に効率的であることを確認するために、以前のアルゴリズムと比較することができます。ベンチマークは、顧客がさまざまなサプライヤの製品を比較して、機能とパフォーマンスの面で特定の要件に最も適した製品を見積もるときに使用できます。たとえば、メインフレームの世界では、 Syncsortなどの独立系ソフトウェア会社の特定の独自のソート製品は、速度の点でIBMなどの大手サプライヤの製品と競合しています。

^{いくつかのベンチマークは、例えば[3] [4]}のような様々なコンパイル言語とインタープリタ言語の相対速度を比較する分析を行う機会を提供し 、またコンピュータ言語ベンチマークゲームは、いくつかのプログラミング言語における典型的なプログラミング問題の実装のパフォーマンスを比較します。

「自分で作る」ベンチマークさえも、さまざまなユーザー指定の基準を使用して、さまざまなプログラミング言語の相対的なパフォーマンスを示すことができます。これは、Christopher W. Cowell-Shah による「9 つの言語のパフォーマンスのまとめ」が例を挙げて示しているように、非常に簡単です。^[5]

実装上の問題も効率に影響を与える可能性があります。たとえば、プログラミング言語の選択、アルゴリズムの実際のコーディング方法^{[6] 、特定の言語の}コンパイラの選択、使用するコンパイル オプション、さらには使用するオペレーティング システムなどです。多くの場合、インタープリタによって実装された言語は、コンパイラによって実装された言語よりもはるかに遅くなる可能性があります。^[3]ジャストインタイム コンパイルとインタープリタ言語に関する記事を参照してください。

時間やスペースの問題に影響を与える可能性があるが、プログラマーが制御できない他の要因もあります。これには、データアライメント、データ粒度、キャッシュの局所性、キャッシュの一貫性、ガベージコレクション、命令レベルの並列性、マルチスレッド（ハードウェアレベルまたはソフトウェアレベルのいずれか）、同時マルチタスク、サブルーチン呼び出しが含まれます。^[7]

一部のプロセッサにはベクトル処理機能があり、単一の命令で複数のオペランドを操作できます。プログラマやコンパイラにとって、これらの機能を使用するのは簡単な場合もあれば、そうでない場合もあります。順次処理用に設計されたアルゴリズムは、並列処理を利用するために完全に再設計する必要がある場合がありますが、簡単に再構成できる場合もあります。2010年代後半に並列コンピューティングと分散コンピューティングの重要性が高まるにつれて、 CUDA、TensorFlow、Hadoop、OpenMP、MPIなどの並列コンピューティングと分散コンピューティング システム用の効率的な高レベル APIへの投資が増えています。

プログラミングで発生する可能性があるもう 1 つの問題は、同じ命令セットと互換性のあるプロセッサ ( x86-64やARMなど) が異なる方法で命令を実装する場合があるため、一部のモデルでは比較的高速な命令が、他のモデルでは比較的低速になる可能性があることです。これは多くの場合、最適化コンパイラにとって課題となります。最適化コンパイラは、プログラムのパフォーマンスを最適に最適化するために、コンパイル対象で使用可能な特定のCPUやその他のハードウェアに関する広範な知識を持っている必要があります。極端な場合、コンパイラは、コンパイル対象のプラットフォームでサポートされていない命令をエミュレートすることを余儀なくされ、他のプラットフォームではネイティブにサポートされていてハードウェアでより効率的であっても、そのプラットフォームでは計算できない結果を生成するためにコードを生成したり、外部ライブラリ呼び出しをリンクしたりすることを余儀なくされる場合があります。これは、浮動小数点演算に関する組み込みシステムでよく発生します。組み込みシステムでは、小型で低電力のマイクロコントローラでは浮動小数点演算のハードウェア サポートが不足していることが多く、そのため浮動小数点計算を行うために計算コストの高いソフトウェア ルーチンが必要になります。

測定値は通常、入力のサイズの関数として表現されます。 ${\displaystyle \scriptstyle {n}}$

最も一般的な 2 つの対策は次のとおりです。

• 時間: アルゴリズムが完了するまでにどれくらいの時間がかかりますか?
• スペース: アルゴリズムにはどれくらいの作業メモリ (通常は RAM) が必要ですか? これには、コードに必要なメモリの量 (補助スペース使用量) と、コードが動作するデータに必要なメモリの量 (固有スペース使用量) という 2 つの側面があります。

バッテリーで電力が供給されるコンピューター（例：ノートパソコンやスマートフォン）、または非常に長い/大規模な計算（例：スーパーコンピューター）の場合、他の重要な測定基準は次のとおりです。

• 直接電力消費: コンピューターを動作させるために直接必要な電力。
• 間接電力消費：冷却、照明などに必要な電力。

2018 年現在、組み込みIoTデバイスからシステムオンチップデバイス、サーバー ファーム^[update]に至るまで、あらゆる種類と規模の計算タスクにおいて、電力消費は重要な指標として増加しています。 この傾向は、グリーン コンピューティングと呼ばれることがよくあります。

計算効率のあまり一般的ではない測定基準も、場合によっては関連することがあります。

• 転送サイズ: 帯域幅が制限要因となる場合があります。転送するデータの量を減らすには、データ圧縮を使用できます。画像やイメージ (例: Google ロゴ) を表示すると、テキスト「Google」の 6 バイトの転送と比較して、数万バイト (この場合は 48K) の転送が必要になる場合があります。これは、I/O バウンドのコンピューティングタスクにとって重要です。
• 外部スペース: ディスクまたはその他の外部メモリ デバイス上に必要なスペース。これは、アルゴリズムの実行中に一時的に保存する場合もあれば、将来の参照のために持ち越す必要がある長期保存の場合もあります。
• 応答時間(待ち時間): これは、コンピュータ システムが何らかの外部イベントに迅速に応答する必要があるリアルタイム アプリケーションで特に重要です。
• 総所有コスト: 特にコンピューターが特定のアルゴリズム専用である場合。

アルゴリズムの分析は、通常、時間の複雑さなどの概念を使用して、入力データのサイズの関数として実行時間を推定するために使用できます。結果は通常、Big O 表記法を使用して表現されます。これは、特に大量のデータを処理する必要がある場合に、アルゴリズムを比較するのに役立ちます。データ量が少ない場合は、アルゴリズムのパフォーマンスを比較するために、より詳細な推定値が必要になりますが、これはあまり重要ではない可能性があります。並列アルゴリズムは、分析がより難しい場合があります。

ベンチマークは、実際のアルゴリズムのパフォーマンスを評価するために使用できます。多くのプログラミング言語には、 CPU 時間の使用状況を提供する関数が用意されています。長時間実行されるアルゴリズムの場合、経過時間も重要です。通常、結果は複数のテストで平均化されます。

実行ベースのプロファイリングは、ハードウェア構成や、マルチプロセスおよびマルチプログラミング環境で同時に実行される他のプログラムやタスクの可能性に非常に敏感になる可能性があります。

この種のテストは、特定のプログラミング言語、コンパイラ、およびコンパイラ オプションの選択に大きく依存するため、比較するアルゴリズムはすべて同じ条件で実装する必要があります。

このセクションでは、アルゴリズムの実行中のメモリ リソース (レジスタ、キャッシュ、RAM、仮想メモリ、二次メモリ)の使用について説明します。上記の時間分析と同様に、通常は空間複雑度分析を使用してアルゴリズムを分析し、入力データのサイズの関数として必要な実行時メモリの見積もりを取得します。結果は通常、Big O 表記法を使用して表現されます。

考慮すべきメモリ使用量の側面は最大 4 つあります。

• アルゴリズムのコードを保持するために必要なメモリの量。
• 入力データに必要なメモリの量。
• 出力データに必要なメモリの量。
  • ソートなどの一部のアルゴリズムでは、入力データを再配置することが多く、出力データ用に追加のスペースは必要ありません。この特性は、「インプレース」操作と呼ばれます。
• 計算中に作業スペースとして必要なメモリの量。
  • これには、ローカル変数と、計算中に呼び出されるルーチンに必要なスタック スペースが含まれます。このスタック スペースは、再帰手法を使用するアルゴリズムにとって重要になる場合があります。

初期の電子コンピュータや初期の家庭用コンピュータの作業メモリは比較的小さかった。たとえば、1949 年のElectronic Delay Storage Automatic Calculator (EDSAC) の最大作業メモリは 1024 17 ビット ワードだったが、1980 年の Sinclair ZX80 は当初 1024 8 ビット バイトの作業メモリを搭載していた。2010 年代後半には、パーソナル コンピュータのRAM は4 ～ 32 GBが一般的で、メモリは 3 億倍以上に増加している。

最近のコンピュータは比較的大容量のメモリ (ギガバイト単位) を搭載できるため、限られたメモリ量にアルゴリズムを詰め込むことは、以前ほど問題ではありません。ただし、メモリの種類とそれらの相対的なアクセス速度は、重要な意味を持ちます。

• プロセッサ レジスタは、最小のスペースで最速のメモリです。現代のコンピュータでのほとんどの直接計算は、必要に応じてキャッシュ、メイン メモリ、仮想メモリに更新される前に、レジスタ内のソース オペランドと宛先オペランドを使用して行われます。プロセッサ コアでは、通常、数百バイト以下のレジスタが使用可能ですが、レジスタファイルには、命令セット アーキテクチャで定義されたアーキテクチャレジスタよりも多くの物理レジスタが含まれる場合があります。
• キャッシュ メモリは、メモリ階層で 2 番目に高速で、2 番目に小さいメモリです。キャッシュは CPU や GPU などのプロセッサに存在し、通常はスタティック RAMに実装されていますが、ディスク ドライブなどの周辺機器にも存在します。プロセッサ キャッシュには多くの場合、独自のマルチレベル階層があります。下位レベルはサイズが大きく、低速で、通常はマルチコア プロセッサのプロセッサ コア間で共有されます。キャッシュ メモリ内のオペランドを処理するには、処理ユニットがキャッシュからデータをフェッチし、レジスタ内で操作を実行して、データをキャッシュに書き戻す必要があります。これは、 L1 キャッシュ内にある場合、CPU または GPU の算術論理ユニットまたは浮動小数点ユニットと同等の速度 (約 2 ～ 10 倍遅い) で動作します。^{[8] L1}キャッシュミスがあり、 L2キャッシュからデータを取得して書き込む必要がある場合は約10倍遅くなり、L2キャッシュミスがあり、 L3キャッシュ（存在する場合）からデータを取得する必要がある場合は、さらに10倍遅くなります。
• メイン物理メモリは、ほとんどの場合、ダイナミックRAM （DRAM）に実装されています。メインメモリは、L3 CPUキャッシュよりもはるかに大きく（通常、ギガバイト対≈8メガバイト）、読み取りと書き込みのレイテンシは通常10〜100倍遅くなります。^[8] 2018年現在、RAMはCPUまたはGPUメモリとしてプロセッサのオンチップに^[update]実装されることが増えています。^[要出典]
• 仮想メモリ管理によく使用されるページメモリは、ハードディスクなどの二次記憶装置に格納されるメモリであり、メモリ階層の拡張であり、潜在的に大きなストレージスペースの使用を可能にしますが、レイテンシがはるかに高くなり、通常、RAMの値のキャッシュミスの約1000倍遅くなります。 ^[8]仮想メモリは、実際に使用できるメモリよりも多くのメモリが使用可能であるという印象を与えることが本来の目的でしたが、現代の使用法では、時間と空間のトレードオフと仮想マシンの使用を可能にする点でより重要になっています。^{[8]メインメモリからのキャッシュミスは}ページフォールトと呼ばれ、プログラムに大きなパフォーマンスの低下をもたらします。

メモリ要件がキャッシュ メモリに収まるアルゴリズムは、メイン メモリに収まるアルゴリズムよりもはるかに高速です。メイン メモリに収まるアルゴリズムは、ページングに頼る必要があるアルゴリズムよりもはるかに高速です。このため、キャッシュ置換ポリシーは、キャッシュ対応プログラミングやデータ アライメントと同様に、高性能コンピューティングにとって非常に重要です。さらに問題を複雑にしているのは、一部のシステムには、有効速度が異なる最大 3 レベルのキャッシュ メモリがあるということです。システムによって、これらのさまざまな種類のメモリの量は異なるため、アルゴリズムのメモリ要件の影響はシステムごとに大きく異なります。

電子計算の初期の頃は、アルゴリズムとそのデータがメイン メモリに収まらない場合、そのアルゴリズムは使用できませんでした。今日では、仮想メモリの使用により、より多くのメモリが提供されるようですが、パフォーマンスが犠牲になっています。アルゴリズムとそのデータがキャッシュ メモリに収まる場合、はるかに高速化できます。この場合、スペースを最小限に抑えると、時間も最小限に抑えられます。これは局所性の原理と呼ばれ、参照の局所性、空間の局所性、および時間的な局所性に細分できます。キャッシュ メモリに完全には収まらないが、参照の局所性を示すアルゴリズムは、かなり良好なパフォーマンスを発揮する可能性があります。

• アルゴリズムの分析- アルゴリズムに必要なリソースを決定する方法
• ベンチマーク- 定義されたケースでの実行時間の比較を測定する方法
• 最良、最悪、平均のケース- 3 つのシナリオで実行時間を見積もるための考慮事項
• コンパイラ最適化—コンパイラ由来の最適化
• 計算複雑性理論
• コンピュータのパフォーマンス- コンピュータのハードウェア メトリック
• 経験的アルゴリズム学— 経験的手法を用いてアルゴリズムの挙動を研究する実践
• 最適化（コンピュータサイエンス）
• パフォーマンス分析- 実行時にアルゴリズムの実際のパフォーマンスを測定する方法