Javascript循环vs链接列表与ES6设置以找到两个匹配的整数

Question

我准备了两个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;
}

更新：

这是一个好主意，回到过去，让另一个想法，问题的基础上，到目前为止。

由于@ for 035对小数据集的注释，我运行了另一个测试，但这次使用的是1到8之间的100,000整数。我将9分配到第一个和最后一个位置，并搜索18个以确保整个数组都将被搜索。

我还包括了相对较新的ES6 Set函数，以供比较，这要归功于@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)

摘要：

因此，看起来链接列表对于更小的数据集来说确实是非常快的，而对于较大的数据集来说，ES6集是很好的。不过，For循环在所有测试中都是明显的赢家。

所有3种方法都将与数据量成线性关系。

请注意: ES6集与旧浏览器不向后兼容，以防此操作必须由客户端执行。

Answer 1

别用这个。用一套。

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 2

通过对数组进行预排序，然后使用真正的二进制搜索，您可以对其进行实质性的优化。

​

// 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个元素组成的数组需要几微秒。

重写includesBinary以避免递归可能会进一步提高性能。

Answer 3

首先，find2PairsBySumLog函数不是二进制搜索，它是一种蛮力方法，它解析数组的所有元素，最坏的情况是时间复杂度应为O(n*n)，第二个函数是线性搜索，‘为什么要让第二个方法快速运行，对于第一个函数，您可以做的是初始化二进制HashMap并检查数组中的每一对整数，就像在第二个函数中所做的那样。

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;
  }
}