Javascript - forループ対Linked List vs ES6 2つの一致する整数を見つけるために設定

Question

2つのJavascript関数を用意して、合計まで加算してブール値を返す一致する整数ペアを見つけました。

最初の関数は、そのようなバイナリ検索を使用しています：私は合計に補完的な整数を追加し、で値を検索ところで、私自身の単独リンクリストを実装する第二の機能については

function find2PairsBySumLog(arr, sum) { 
for (var i = 0; i < arr.length; i++) { 
    for (var x = i + 1; x < arr.length; x++) { 
    if (arr[i] + arr[x] == sum) { 
     return true; 
    } 
    } 
} 
return false; 
} 

リンクされたリスト。リンクされたリストに値が見つかった場合、一致があることがわかります。

function find2PairsBySumLin(arr, sum) { 
    var complementList = new LinkedList(); 
    for (var i = 0; i < arr.length; i++) { 
    if (complementList.find(arr[i])) { 
     return true; 
    } else { 
     complementList.add(sum - arr[i]); 
    } 
    } 
    return false; 
} 

私は両方の機能を実行すると、私ははっきりとリンクリストの検索が実行されることがわかり〜75％高速化

var arr = [9,2,4,1,3,2,2,8,1,1,6,1,2,8,7,8,2,9]; 

console.time('For loop search'); 
console.log(find2PairsBySumLog(arr, 18)); 
console.timeEnd(‘For loop search’); 

console.time('Linked List search'); 
console.log(find2PairsBySumLin(arr, 18)); 
console.timeEnd('Linked List search'); 

true 
For loop search: 4.590ms 
true 
Linked List search: 0.709ms 

ここに私の質問：リンクリストのアプローチは、実際の線形検索ですか？結局のところ、私は外側のループが最初の配列を反復しながら、私はすべてのノードをループします。ここで

私のLinkedListの検索機能である：

LinkedList.prototype.find = function(data) { 
    var headNode = this.head; 
    if(headNode === null) { 
    return false; 
    } 
    while(headNode !== null) { 
    if(headNode.data === data) { 
     return true; 
    } else { 
     headNode = headNode.next; 
    } 
    } 
    return false; 
} 

---

UPDATE：

戻って、これまでのコメントをもとに問題の別のシンクタンクを持っているのは良いアイデアでした。小さなデータセットにnem035 @コメントへ

おかげで、私は別のテストを実行しましたが、1と8の間10万整数で、この時間は、私が最初と最後の位置に9を割り当てられ、配列全体が意志を確認するために18で検索しました検索されます。

また、私は比較的新しいES6を添付しましたは@Oriolのおかげで比較機能を設定しました。

Btw @Oriolと@Deepakあなたは正しいです。最初の関数はバイナリ検索ではなく、対数複雑さのないO（n * n）検索です。

私のリンクリストの実装は、すべての検索の中で最も遅かったことが判明しました。私は各機能ごとに10回の繰り返しを実行しました。ここでの結果：

For loop search:  24.36 ms (avg) 
Linked List search: 64328.98 ms (avg) 
Set search:   35.63 ms (avg) 

ここ10,000,000整数のデータセットの同じテスト：

For loop search:  30.78 ms (avg) 
Set search:   1557.98 ms (avg) 

が要約：

は、だから、リンクリストが小さいために本当に速いようです〜1000までのデータセット、ES6セットは大規模なデータセットに最適です。 それにもかかわらず、ループの場合はすべてのテストで明らかに勝者です。

すべての3つの方法は、データ量に比例して直線的に拡大します。

注意：この操作をクライアント側で行う必要がある場合は、ES6セットは古いブラウザと下位互換性がありません。

Answer 1

最初にfind2PairsBySumLog関数はバイナリ検索ではなく、配列のすべての要素を解析する一種のブルートフォースメソッドであり、最悪の場合の複雑さはO（n * n）でなければならず、2番目の関数はa最初の関数find2PairsBySumLogで実行できることはバイナリHashMapを初期化し、おそらく2番目の関数のような配列型の整数の各対をチェックすることです

bool isPairsPresent(int arr[], int arr_size, int sum) 
{ 
    int i, temp; 
    bool binMap[MAX] = {0}; 

    for (i = 0; i < arr_size; i++) 
    { 
    temp = sum - arr[i]; 
    if (temp >= 0 && binMap[temp] == 1) 
      return true; 
    binMap[arr[i]] = 1; 
    } 
} 

Answer 2

使用しないでください。セットを使用してください。

function find2PairsBySum(arr, sum) { 
    var set = new Set(); 
    for(var num of arr) { 
    if (set.has(num)) return true; 
    set.add(sum - num); 
    } 
    return false; 
} 

それだけです。 addとhasは、平均でサブライン（おそらく一定）であることが保証されています。

Answer 3

これを実質的に最適化するには、配列を事前ソートしてから実際のバイナリ検索を使用します。

// Find an element in a sorted array. 
 
function includesBinary(arr, elt) { 
 
    if (!arr.length) return false; 
 
    
 
    const middle = Math.floor(arr.length/2); 
 

 
    switch (Math.sign(elt - arr[middle])) { 
 
    case -1: return includesBinary(arr.slice(0, middle - 1), elt); 
 
    case 0: return true; 
 
    case +1: return includesBinary(arr.slice(middle + 1), elt); 
 
    } 
 
} 
 

 
// Given an array, pre-sort and return a function to detect pairs adding up to a sum. 
 
function makeFinder(arr) { 
 
    arr = arr.slice().sort((a, b) => a - b); 
 

 
    return function(sum) { 
 
    for (let i = 0; i < arr.length; i++) { 
 
     const remaining = sum - arr[i]; 
 
     if (remaining < 0) return false; 
 
     if (includesBinary(arr, remaining)) return true; 
 
    } 
 
    return false; 
 
    }; 
 
} 
 

 
// Test data: 100 random elements between 0 and 99. 
 
const arr = Array.from(Array(100), _ => Math.floor(Math.random() * 100)); 
 
const finder = makeFinder(arr); 
 

 
console.time('test'); 
 
for (let i = 0; i < 1000; i++) finder(100); 
 
console.timeEnd('test');

このラフなベンチマークによると、100個の要素の配列への1つのルックアップは、数マイクロ秒かかります。

再帰を避けるためにincludesBinaryを書き換えると、おそらくパフォーマンスがさらに向上します。