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



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

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

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

• アイテムを検索します。 配列メソッドindexOf()
  
  
  
  およびindexOf()



includes()
  
  
  
  、要素の検索および要素に要素があるかどうかの確認に使用され、動作が遅くなります。
• アイテムの削除。 アイテムは、その値に基づいてコレクション内で削除できます。 配列では、そのようなアクションに相当するのは、要素のインデックスに基づいてsplice()
  
  
  
  メソッドを使用することです。 アイテム検索と同様に、インデックスを使用してアイテムを削除するのは時間がかかります。
• アイテムを挿入します。 配列でpush()
  
  
  
  やunshift()
  
  
  
  などのメソッドを使用するよりも、コレクションに要素を追加する方がはるかに高速です。
• NaN
  
  
  
  値を処理します。 indexOf()
  
  
  
  メソッドを使用しhas()
  
  
  
  配列内のNaN
  
  
  
  値を見つけることはできませんが、 has()
  
  
  
  コレクションメソッドを使用すると、 NaN
  
  
  
  れているかどうかを確認できます。
• 重複するアイテムを削除します。 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 ² ）になります。 その結果、彼はずっと遅くなるでしょう。

まとめ

JavaScriptでSet



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



親愛なる読者！ コードにSet



データ構造をどのように適用しますか？