強力なハードウェアがあれば、アルゴリズムはもはや重要ではないのでしょうか?

この記事は、プログラマーの質問と回答のコミュニティである stackexchange.com の質問から翻訳されたものです。

質問: アルゴリズム (特に一般的に効率的なもの) の追求はもはや重要ではありません。

コンピュータのハードウェアのコストが以前よりもはるかに安くなっているということは、アルゴリズムやアルゴリズムを改善するためのスキルがそれほど重要ではなくなったということでしょうか?ほとんどの場合、無限ループを書かないようにしてください。しかし、強力なハードウェアがあれば、悪いコードは大きな問題にならないのでしょうか?

パベル・ザイチェンコフ 11 票

私は特に、『アルゴリズム入門』という本からのこの例が好きです。これはアルゴリズムのパフォーマンスの重要性を圧倒的な方法で示しています。

「挿入ソート」と「マージソート」という 2 つのソートアルゴリズムを比較してみましょう。それらのアルゴリズムの複雑さはそれぞれ O(n ² )=c ₁ n ²と O(nlogn)=c ₂ n lg n です。一般に、マージソートアルゴリズムは定数係数が大きいため、 c ₁ < c _{2 と想定します。}

ご質問にお答えするために、最新の高速コンピュータ A で「挿入ソート」アルゴリズムを実行し、それを旧式のコンピュータ B で「マージソート」アルゴリズムを実行しているものと比較します。

以下を前提とします:

• 入力問題のデータ量は1000万個です: n=10 ⁷ ;
• コンピュータAは1秒あたり10 ^{10 回の}演算を実行できます（約10GHz）。
• コンピュータ B は 1 秒あたり 10 ^{7 回の}演算 (~ 10MHz) しか実行できません。
• 定数係数 C ₁ = 2 (少し誇張)、C ₂ = 50 (実際より少し小さい)

したがって、上記の仮定の下では、次の結果が得られます。

コンピュータA:

2⋅(107)2 操作 1010 操作/秒 = 2⋅104 秒

コンピュータB :

50⋅107lg107 操作107 操作/秒≈1163 秒

つまり、1000 倍遅いコンピューターは、速いコンピューターよりも 17 倍速く動作するのです。さらに、実際には、特に計算量が増加すると、マージ アルゴリズムの方が効率的になります。この回答があなたの質問に対する答えとなることを願っています。

しかし、これは単にアルゴリズムの複雑さの問題ではありません。現在、CPU 周波数を上げるだけでは大幅なパフォーマンス向上を達成することは不可能です。マルチコア CPU アーキテクチャ上でのアルゴリズムのパフォーマンスを改善する必要があります。そして、コア数が増えるにつれて、他のオーバーヘッド（メモリアクセスのスケジュール制御など）がパフォーマンスの障害となるため、これは対処が難しい問題です。したがって、ヒープ ハードウェアが線形のパフォーマンス向上を達成することは困難です。

つまり、アルゴリズムの改善は、CPU コアの数やクロック速度がどれだけ高くても、アルゴリズムの改善と同じ利益をもたらすことはできないため、今も昔もアルゴリズムの改善は重要です。

ユヴァル・フィルマス 11 票

逆に、ハードウェアが安価になるにつれて、新たなコンピューティングのニーズが増加しています。

まず第一に、私たちが処理しなければならないデータの量は飛躍的に増加しています。ここで、「準線形時間アルゴリズム」とビッグデータ研究という話題に移ります。たとえば、検索エンジンのアルゴリズム設計について考えてみましょう。検索エンジンは膨大な数のリクエストを処理し、膨大な量のデータの中から結果をすばやく見つけて返す必要があり、アルゴリズムの効率性が以前よりも重要になっています。

第二に、「機械学習」が勢いを増しています。これはアルゴリズムの世界です（大学で学んだものとは異なるかもしれません）。この分野は困難に満ちていますが、新しいアルゴリズムが生まれる場所でもあります。

さらに、「分散コンピューティング」が非常に重要になってきており、CPU周波数を上げる上でボトルネックが発生しています。今日、コンピュータのパフォーマンスは並列コンピューティングを通じてのみ向上することができ、ここでアルゴリズムが役立ちます。

最後に、CPU/GPU パフォーマンスの急速な発展のバランスをとるために、多数の仮想マシン テクノロジを使用して、セキュリティ脆弱性の脅威から防御します。オペレーティング システムは、セキュリティの脅威とアラートに対処するために多くの時間とエネルギーを費やし、残りの CPU 時間は重要な作業に使用できなくなり、プログラムのパフォーマンスが低下します。特に、CPU リソースを大量に消費するビデオの圧縮/解凍計算があります。コンピューターのハードウェアのパフォーマンスは日々向上していますが、その効率は同じ割合で向上していません。

まとめると、ビッグデータ処理、人工知能、分散コンピューティングにはアルゴリズムの改善が不可欠です。CPU コンピューティング能力に対する需要が急速に高まる中、さまざまな理由から有効活用されておらず、アルゴリズムの重要性はまだまだ衰えていません。

元のリンク: http://cs.stackexchange.com/questions/15017/are-algorithms-and-efficiency-in-general-getting-less-important

翻訳リンク: http://junius.lofianima.com/post/algorithms-is-important