フロントエンド上級編: よく使われるいくつかの JS 検索アルゴリズムの概要とパフォーマンス比較

[[356180]]

序文

今日は引き続き js アルゴリズムについてお話ししましょう。以下の説明を通じて、検索アルゴリズムの基本的な実装とさまざまな実装方法のパフォーマンスを理解し、for ループ、forEach、While のパフォーマンスの違いを見つけることができます。また、Web ワーカーを介してアルゴリズムをシャーディングして、アルゴリズムのパフォーマンスを大幅に向上させる方法も学習します。

同時に、古典的なバイナリアルゴリズムとハッシュテーブル検索アルゴリズムも簡単に紹介しますが、これらはこの章の焦点ではありません。後ほど、これらの高度なアルゴリズムを詳細に紹介する関連記事を公開します。興味のある友人は、私のコラムをフォローしたり、一緒に議論したりすることができます。

アルゴリズムのパフォーマンスについては、前回の章「フロントエンドアルゴリズムシリーズ」の getFnRunTime 関数を引き続き使用して、フロントエンドコードの速度を 60 倍に上げる方法を学習します。興味がある場合は、確認していただければ、ここでは詳しく説明しません。

前回の章「フロントエンドアルゴリズムシリーズ」では、フロントエンドコードの速度を60倍に上げる方法について、19,000個のデータをシミュレートしました。この章では、効果をより明確にするために、テスト用に170万個のデータを偽造しますが、信じてください、これはjsにとって何でもありません。。。

1. forループ検索

基本的な考え方は、forループを介して配列を走査し、配列内で検索する値のインデックスを見つけて、それを新しい配列にプッシュすることです。

コードは次のように実装されます。

 const getFnRunTime = require( './getRuntime' ); 
 
 /**
  * 通常のアルゴリズム - forループバージョン
  * @param {*} 引数
  * 消費時間: 7～9ms
  */
関数searchBy(arr, 値) {
     結果 = [] とします。
 (i = 0, len = arr.length; i < len; i++)の場合{
        if(arr[i] === 値) {
            結果.push(i);
        }
    }
結果を返す
 }
 getFnRunTime(検索条件、6)

n 回テストした結果は次のとおりです。

2. forEachループ

基本的な考え方は for ループに似ています。

 /**
  * 通常のアルゴリズム - forEach ループバージョン
  * @param {*} 引数
  * 消費時間: 21～24ms
  */
関数searchByForEach(arr, 値) {
    結果 = [] とします。
    arr.forEach((item,i) => {
        if(項目 === 値) {
            結果.push(i);
        }
    })
結果を返す
}

これには 21 ～ 24 ミリ秒かかり、パフォーマンスは for ループほど良くないことがわかります (今のところ、本質も真実であるとだけ言っておきます)。

3. whileループ

コードは次のとおりです。

 /**
  * 通常のアルゴリズム - whileループバージョン
  * @param {*} 引数
  * 消費時間: 11ms
  */
関数searchByWhile(arr, 値) {
     i = arr.lengthとします。
     結果 = [];
    while(i) {
        if(arr[i] === 値) {
            結果.push(i);
        }
        私  - ;  
    } 
     
結果を返す
}

while ループと for ループのパフォーマンスは似ており、どちらも優れていることがわかりますが、forEach のパフォーマンスが低いため使用すべきではないという意味ではありません。 for ループと比較すると、 foreach はコードを削減しますが、 foreach は IEnumerable に依存します。実行時の効率は for ループよりも低くなります。ただし、ループ回数が不明なループを扱う場合や、ループ回数を計算する必要がある場合は、 foreach を使用する方が便利です。さらに、 foreach のコードはコンパイラシステムによって最適化された後、 for ループのループと似たものになります。

4. 二分探索

バイナリ検索は、値が一意で順序付けられている配列でよく使用されます。ここでは、for/while/forEach とのパフォーマンスの比較は行いません。

基本的な考え方: シーケンスの途中から比較を開始します。現在の位置の値が検索対象の値と等しい場合、検索は成功します。検索対象の値が現在の位置の値より小さい場合は、シーケンスの前半で検索します。検索対象の値が現在の位置の値より大きい場合は、見つかるまでシーケンスの後半で検索を続けます。

コードは次のとおりです。

 /**
   * バイナリアルゴリズム
   * @param {*} 引数
   * @param {*} 値
   */
関数binarySearch(arr, 値) {
    min = 0 とします。
    max = arr.length - 1 とします。 
     
    (最小値<=最大値)の間
      定数mid = Math.floor(( min + max ) / 2); 
   
      (arr[mid] === 値)の場合{
ミッドに戻ります。
      }そうでなければ (arr[mid] > 値) {
最大= 中間 - 1;
      }それ以外{
最小= 中間 + 1;
      }
    } 
   
戻る  '見つかりません' ;
  }

大量のデータを扱うシナリオでは、バイナリ検索は非常に効率的ですが、不安定であるため、大規模なデータクエリでは若干不利になります。

5. ハッシュテーブル検索

ハッシュテーブル検索はハッシュテーブル検索とも呼ばれます。キーワードを検索することで、比較せずに必要なレコードの保存場所を取得できます。レコードの保存場所とそのキーワードの間に一定の対応fを確立し、各キーワードキーが保存場所f（キー）に対応します。

ハッシュテーブル検索の使用シナリオ:

ハッシュテーブルが最も適している問題は、指定された値に等しいレコードを見つけることです。
ハッシュ検索は、同じキーワードが複数のレコードに対応する状況には適していません。
18歳から22歳の学生を検索するなどの範囲検索には適していません

ここでは、ハッシュを誰もが理解しやすいように、hashTable の最もシンプルなバージョンを紹介します。

 /**
 * ハッシュテーブル
 * 以下の方法ではデータの上書きの問題が発生する可能性があります
 */
関数ハッシュテーブル() {
  varテーブル= []; 
 
  // ハッシュ関数
  var loseloseHashCode =関数(キー) {
    var ハッシュ = 0;
 ( var i=0; i<キー.length; i++) {
      ハッシュ +=キー.charCodeAt(i);
    }
ハッシュ% 37を返す
  }; 
 
  // 置く
  this.put =関数(キー、値) {
    var position = loseloseHashCode(キー);
テーブル[位置] = 値;
  } 
 
  // 得る
  this.get =関数(キー) {
戻る テーブル[loseloseHashCode(キー)]
  } 
 
  // 取り除く
  this.remove =関数(キー) {
テーブル[loseloseHashCode(キー)] = 未定義;
  }
 }

この方法ではデータの競合が発生する可能性がありますが、解決策はあります。ここでは多くの知識ポイントが関係しているので、後でそれらを紹介する特別な記事を公開します。

オープンアドレス
二次検出
ランダムプロービング

Webワーカー最適化を使用する

上記の方法により、さまざまなアルゴリズムのパフォーマンスと適用シナリオがすでにわかっています。アルゴリズムを使用する場合、Web ワーカーを介してアルゴリズムを最適化し、プログラムが並列処理できるようにすることもできます。たとえば、大きな配列を複数のブロックに分割し、Web ワーカースレッドに計算結果の処理を任せ、最後に結果をマージしてワーカーのイベントメカニズムを介してブラウザーに渡します。その効果は非常に顕著です。

要約する

複雑な配列クエリの場合、for/whileはforEachや他の配列メソッドよりもパフォーマンスが優れています。
O(logn) の二分探索は非常に効率的なアルゴリズムです。しかし、その欠陥も明らかです。配列は順序付けられる必要があり、配列が順序付けられていることを保証するのは困難です。もちろん、配列を構築するときにソートすることはできますが、その場合、配列でなければならないという 2 番目のボトルネックが発生します。配列の読み取り効率は O(1) ですが、要素の挿入と削除の効率は O(n) です。これにより、順序付けられた配列を構築する際の効率が低下します。
ハッシュテーブル検索の基本的な使用法とシナリオ。
条件が許せば、Web ワーカーを使用してアルゴリズムを最適化し、バックグラウンドで並列実行できます。

さて、この記事は比較的シンプルですが、とても重要です。検索アルゴリズムについて、皆さんがより直感的に理解できるようになることを願っています。また、皆さんがより良い方法を見つけ、一緒に議論したり、アイデアを交換したりできるようになることを願っています。

<<: 2020 年の生体認証市場 - パンデミックによる業界の動向の変化

>>: YouTube でフォローすべき 5 人のデータサイエンティストと機械学習エンジニア