Geekly Articles each Day

Setデータ型を使用したJavaScriptの高速化

本書の翻訳者は、多くのJavaScript開発者が主にNumber 、 String 、 Object 、 Array 、 Booleanなどのデータ型を使用していると確信しています。 ほとんどの場合、これで十分です。 ただし、コードを可能な限り高速でスケーラブルにする必要がある場合、これらのデータ型の使用が常に正当化されるとは限りません。



この記事では、一意の値のコレクションを操作する機能を提供するSetデータ型を使用して、コードを高速化する方法について説明します。 これは、特に大規模プロジェクトのコードに当てはまります。 Array型とSet型には多くの共通点がありますが、 Setデータ型を使用すると、 Array型にはないプログラムの実行中に明らかになるような機能をプログラマに提供できます。

Arrayデータ型とSetデータ型の違いは何ですか？


Arrayデータ型の主な機能（この型のオブジェクトを「配列」と呼びます）は、配列が値のインデックス付きコレクションであることです。 これは、配列内のデータがインデックスを使用して保存されることを意味します。

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

配列とは異なり、 Setタイプのオブジェクト（「コレクション」と呼びます）は、キー/値形式のデータを含むコレクションです。 インデックスを使用する代わりに、コレクションはキーを使用してアイテムを保存します。 コレクションに保存されている要素は、コレクションに追加された順序で並べ替えることができますが、コレクションは同じ要素を保存できません。 つまり、コレクションのすべての要素は一意である必要があります。

コレクションの主な長所は何ですか？


コレクションと配列を比較すると、配列よりもコレクションに優る利点がいくつかあります。特に、プログラムのパフォーマンスが重要な状況で顕著です。


Set型のオブジェクトの組み込みメソッドの完全なリストは、 ここにあります 。

アルゴリズムの時間の複雑さについて


配列が要素を検索するために使用する方法には、線形時間の複雑さ-O（N）があります。 つまり、要素の検索時間は配列のサイズに比例します。

配列とは異なり、コレクションがアイテムの検索、削除、および追加に使用するメソッドには、O（1）時間の複雑さがあります。 これは、コレクションのサイズがそのようなメソッドの作業時間に実質的に影響しないことを意味します。

ここでは、アルゴリズムの時間の複雑さについて詳しく読むことができます。

コレクションは配列よりどれくらい高速ですか？


JavaScriptコードのパフォーマンスインジケーターはさまざまな要因に強く影響されますが、特に、コードが実行されるシステム、使用されるコードランタイム、処理されたデータのサイズに依存しますが、テストの結果が配列とコレクションを比較する機会を与えることを願っています実用的な観点から、コレクションが配列よりも高速であることを理解します。 次に、3つの簡単なテストを検討し、その結果を分析します。

▍試験準備


テストを行う前に、100万個の要素と同じコレクションを持つ配列を作成しましょう。 簡単にするために、最初のカウンター値が0で最後が999999のサイクルを使用します。

 let arr = [], set = new Set(), n = 1000000; for (let i = 0; i < n; i++) { arr.push(i); set.add(i); }

▍テスト番号1：配列内およびコレクション内の要素の存在の確認


最初に、配列とコレクション内の要素123123の存在を確認します。これらのデータ構造にそのような要素が存在することを事前に知っています。

 let result; console.time('Array'); result = arr.indexOf(123123) !== -1; console.timeEnd('Array'); console.time('Set'); result = set.has(123123); console.timeEnd('Set');

このテストの結果は次のとおりです。

 Array: 0.173ms Set: 0.023ms

コレクションは、配列より7.54倍高速です。

▍テスト番号2：要素の挿入


次に、配列とコレクションに要素を追加してみましょう。

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

起こったことは次のとおりです。

 Array: 0.018ms 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');

結果は次のとおりです。

 Array: 1.122ms Set: 0.015ms

この場合、コレクションは配列の74.13倍高速でした！

一般に、配列の代わりにコレクションを使用することで、コードのパフォーマンスを大幅に向上させることができます。 いくつかの実用的な例を考えてみましょう。

例1：配列から重複した値を削除する


配列から重複した値をすばやく削除する必要がある場合は、コレクションに変換できます。 これはおそらく、重複する値を取り除く最も簡単な方法です。

 const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C']; //       let uniqueCollection = new Set(duplicateCollection); console.log(uniqueCollection) // : Set(4) {"A", "B", "C", "D"} //        let uniqueCollection = [...new Set(duplicateCollection)]; console.log(uniqueCollection) // : ["A", "B", "C", "D"]

例2：Googleでのインタビュータスク


私の資料の 1つで、Googleのインタビュアーが提起した質問に対する4つの可能な答えを調べました。 インタビューはC ++を使用して実施されましたが、この言語の代わりにJavaScriptが使用された場合、問題の解決にはSetデータ構造が必ず使用されます。

この質問に対する答えをより深く理解したい場合は、上記の記事を読んでください。 ここでは、既製のソリューションを示します。

▍タスク


整数の非ソート配列とsum値を指定します。 この配列の任意の2つの要素を加算した結果、 sum値を取得した場合にtrueを返す関数を作成します。 配列にそのような要素がない場合、関数はfalseを返す必要がありfalse 。

たとえば、配列[3, 5, 1, 4] sum [3, 5, 1, 4]とsum値9が与えられたtrue 、 4+5=9関数はtrueを返すはずです。

ソリューション


次のアイデアを使用してこの問題にアプローチできます。配列を反復処理し、 Setデータ構造を作成し、 sum値に見つかった値を補完する値を追加します。

上記の配列の例を使用して、このアイデアを分析しましょう。 3に出会ったとき、合計9 2つの数字を見つける必要があることがわかっているので、コレクションに数字6を追加できます。 その後、配列から新しい値に出会うたびに、コレクションをチェックして、そこにあるかどうかを確認できます。 5番に達したら、コレクションに4を追加します。 そして、最後に4到達すると、コレクション内でそれを見つけてtrueを返すことができ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））で解を見つけることができます。

ソリューションがArray.prototype.indexOf()メソッドまたはArray.prototype.indexOf()メソッドに依存しており、それぞれの時間複雑度がO（N）である場合、アルゴリズムの合計時間複雑度はO（N 2 ）になります。 その結果、彼はずっと遅くなるでしょう。

まとめ


JavaScriptでSetデータ型に遭遇したことがない場合は、そのアイデアを知っていれば、プロジェクトで有益に使用できることを願っています。

親愛なる読者！ コードにSetデータ構造をどのように適用しますか？

Source: https://habr.com/ru/post/J447578/

More articles:


All Articles