フロントエンドではアルゴリズムを理解する必要はないと思いますか?実際の例を見てみましょう。

[[431020]]

アルゴリズムは、問題を解決するための手順です。同じ問題でも複数の解決策が存在する場合があり、したがってアルゴリズムも複数存在します。ただし、良いアルゴリズムと悪いアルゴリズムがあり、その違いは複雑さにあります。

複雑さは、時間消費/メモリ使用量のパフォーマンスを推定するために使用できるため、複雑さを使用してアルゴリズムを評価します。

(複雑性がわからない場合は、この記事をお読みください: パフォーマンス分析には必ずしもプロファイラーは必要なく、複雑性分析でも問題ありません)

開発の際には、ほとんどのシナリオで最も単純なアイデアを使用します。つまり、比較的複雑度の高いアルゴリズムで問題はなく、さまざまな高度なアルゴリズムは必要ないようです。アルゴリズムは、学習できるものでも、そうでないものでもかまわないようです。

実際にはそうではありません。それは、大量のデータを扱うシナリオに遭遇したことがないからです。

以前の会社での具体的なシナリオの例を挙げてみましょう。

アルゴリズムの力の例

これは私の以前の会社である AutoNavi での実際の例です。

ソースコード全体に対して依存関係の解析を行うと、モジュールは数万個になります。あるモジュールが別のモジュールに依存することを前方依存関係、あるモジュールが別のモジュールに依存することを逆依存関係と呼びます。まず前方依存関係を分析し、次に後方依存関係を分析します。

逆依存関係を分析する場合、従来の考え方では、依存関係ごとに、一方側のすべてのモジュールを走査して、それに依存するモジュール、つまり逆依存関係を見つけます。

このアイデアは非常にシンプルで考えやすいですが、このアイデアに何か問題はありますか?

このアルゴリズムの複雑さは O(n^2) です。n が数十万に達すると、複雑さから推測できるようにパフォーマンスは非常に低下します。

実際、これは事実です。後になって、すべてのソースコードの依存関係を実行するのに 10 時間以上かかり、一晩中実行することさえできませんでした。

最適化するように求められた場合、どのようにパフォーマンスを最適化しますか?

システムを複数のプロセス/複数の作業スレッドに分割し、依存関係分析タスクをいくつかの部分に分割することで、パフォーマンスを数倍向上できるかどうかを尋ねる学生もいるかもしれません。

はい、数倍の改善は大きいです。

しかし、後から変更を加えてパフォーマンスが何万倍も向上したとしたら、信じますか?

変更内容は次のとおりです。

以前は、逆依存関係を分析する場合、各依存関係はすべての順依存関係を走査する必要がありました。しかし、正の依存関係は実際には逆の依存関係ではないでしょうか?

そこで、前方依存関係を分析する際に後方依存関係を記録するように直接変更しました。

この方法では、逆依存関係を個別に分析する必要がなくなり、アルゴリズムの複雑さは O(n^2) から O(n) に削減されます。

O(n^2) から O(n) への変更は、モジュールが数万個ある場合、数万倍のパフォーマンス向上に相当します。

これは、以前は実行に一晩中かかっていたコードが、今ではわずか 10 分強で完了できるという事実に反映されています。このレベルの最適化は、複数のスレッド/プロセスで実行するだけで達成できると思いますか?

これがアルゴリズムの力です。より複雑性の低いアルゴリズムを考案すると、パフォーマンスが大幅に向上します。

私たちが一日中 diff アルゴリズムについて話しているのと同じように、これは O(n^2) の単純なアルゴリズムの複雑さを O(n) に削減するためです。つまり、DOM ノードが何千もある場合、パフォーマンスが何千倍も向上するということです。

それで、アルゴリズムの力を感じますか?

要約する

マルチスレッド、キャッシュなどの手段では、せいぜい数倍のパフォーマンス向上しかできませんが、アルゴリズムの最適化では、パフォーマンスを桁違いに向上させることができます。データ量が多い場合、パフォーマンスは数千倍、数万倍向上する可能性があります。

では、なぜ私たちはアルゴリズムが役に立たないと考えるのでしょうか。それは、処理するデータの量が少なすぎるからです。数百のデータを処理する場合、O(n^2)、O(n^3)、O(n) アルゴリズムの違いはそれほど大きくありません。

処理するシーン データの量が大きくなるほど、アルゴリズムの重要性が増します。これは、優れたアルゴリズムと劣ったアルゴリズムの違いが、数倍や数十倍ではなく、数万倍になる可能性があるためです。

それで、大手企業はすべてアルゴリズムをテストしていることがわかります。それは役に立たないのでしょうか? いいえ、それは非常に重要なことです。それは書かれたコードのパフォーマンスを決定するとも言えます。