JavaScript で Set オブジェクトを使用してコードを高速化する方法についての詳細な説明

基本的なグローバル オブジェクト (数値、文字列、オブジェクト、配列、ブール値) に行き詰まっている開発者はたくさんいると思います。多くのユースケースでは、これらが必要になります。ただし、コードを可能な限り高速かつスケーラブルにしたい場合、これらの基本的な型が常に十分であるとは限りません。

この記事では、JS の Set オブジェクトによってコードがどのように高速化されるか、特にスケーラブルになるかについて説明します。 Array と Set の動作には重複する部分が多くあります。ただし、Set を使用すると、コードの実行速度の点で Array よりも有利になります。

Set の違いは何ですか。

最も基本的な違いは、配列がインデックス付きコレクションであることです。これは、配列内のデータ値がインデックスによって並べ替えられることを意味します。

const arr = [A, B, C, D];
console.log(arr.indexOf(A)); // Result: 0
console.log(arr.indexOf(C)); // Result: 2

対照的に、set はキーのコレクションです。 setインデックスは使用しませんが、キーを使用してデータを並べ替えます。 set の要素は挿入順に反復可能であり、重複データを含めることはできません。つまり、set の各項目は一意である必要があります。

主な利点は何ですか

set には、特に実行時間の点で、配列に比べていくつかの利点があります。

• #View 要素: indexOf() または includes() を使用して配列内の項目が存在するかどうかを確認すると、処理が遅くなります。
• 要素の削除: Set では、値 に基づいて項目を削除できます。配列では、要素ベースのインデックスを使用する splice() が同等のメソッドとなります。前の点と同様に、インデックスに依存すると時間がかかります。
• NaN の保存: ## の間、値 NaN を見つけるために indexOf() または includes() を使用することはできません。 #Set はこの値を保存できます。
重複の削除
• :Setオブジェクトには一意の値のみが保存されます。重複が存在したくない場合、配列には追加のデータが必要になるため、これは配列よりも大きな利点です。重複を処理するコード。
時間の複雑さ?

配列内の要素の検索に使用されるメソッドの時間計算量は

です。言い換えれば、実行時間はデータ サイズと同じ割合で増加します。 対照的に、要素の検索、削除、挿入を行う

メソッドの時間計算量は O(1) のみです。つまり、データ サイズには実際には何も含まれていません。これらのメソッドの実行時間に関係します。 Set の速度はどれくらいですか?

実行時間は、使用するシステム、提供されるデータのサイズ、その他の変数によって大きく異なる可能性がありますが、私のテスト結果が、

についての現実的なアイデアを与えることを願っています。スピード。 3 つの簡単なテストとその結果を紹介します。

テストの準備テストを実行する前に、それぞれ 100 万個の要素を含む配列とセットを作成します。わかりやすくするために、

から始めて 999999 まで数えます。 <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:js;toolbar:false;">let arr = [], set = new Set(), n = 1000000; for (let i = 0; i &lt; n; i++) { arr.push(i); set.add(i); }</pre><div class="contentsignin">ログイン後にコピー</div></div> テスト 1: 要素の検索

番号

<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:js;toolbar:false;">let result; console.time(&amp;#39;Array&amp;#39;); result = arr.indexOf(123123) !== -1; console.timeEnd(&amp;#39;Array&amp;#39;); console.time(&amp;#39;Set&amp;#39;); result = set.has(123123); console.timeEnd(&amp;#39;Set&amp;#39;);</pre><div class="contentsignin">ログイン後にコピー</div></div>

• を検索します。 Set: 0.023ms

の方が高速です7.54 倍テスト 2: 要素の追加

console.time('Array'); 
arr.push(n);
console.timeEnd('Array');
console.time('Set'); 
set.add(n);
console.timeEnd('Set');

• Set: 0.003ms

速度は 6.73 倍高速ですテスト3: 要素の削除

最後に要素を削除します。配列には組み込みメソッドがないため、最初に補助関数を作成します:

const deleteFromArr = (arr, item) => {
  let index = arr.indexOf(item);
  return index !== -1 && arr.splice(index, 1);
};

これはテスト用のコードです:

console.time('Array'); 
deleteFromArr(arr, n);
console.timeEnd('Array');
console.time('Set'); 
set.delete(n);
console.timeEnd('Set');

• Set: 0.015ms

74.13 倍高速です 全体とはいえ、Set

Set が役立つ実際の例をいくつか見てみましょう。 ケース 1: 配列から重複値を削除する

配列から重複値をすぐに削除したい場合は、それを # に変換できます。 ＃＃セット ＃＃＃。これは、一意の値をフィルタリングする最もクリーンな方法です:

const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// 将数组转换为 Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) // Result: Set(4) {"A", "B", "C", "D"}
// 值保存在数组中
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]

ログイン後にコピー

ケース 2: Google インタビューの質問

質問:

sum が与えられた場合、配列内の 2 つの項目の合計が sum

true が返されます。それ以外の場合は、false を返します。たとえば、配列 [3,5,1,4] と sum = 9 の場合、4 5 = 9 であるため、関数は true を返す必要があります。 ＃＃＃。 回答この問題を解決する良い方法は、配列を反復処理し、

を作成して相対的な差を保存することです。

当我们遇到3时，我们可以把6加到Set中, 因为我们知道我们需要找到9的和。然后，每当我们接触到数组中的新值时，我们可以检查它是否在 Set 中。当遇到5时，在 Set 加上4。最后，当我们最终遇到4时，可以在Set中找到它，就返回true。

const findSum = (arr, val) => {
  let searchValues = new Set();
  searchValues.add(val - arr[0]);
  for (let i = 1, length = arr.length; i < length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.has(arr[i])) {
      return true;
    } else {
      searchValues.add(searchVal);
    }
  };
  return false;
};

简洁的版本：

const findSum = (arr, sum) =>
  arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));

因为Set.prototype.has()的时间复杂度仅为O(1)，所以使用 Set 来代替数组，最终使整个解决方案的线性运行时为O(N)。