Javascript - For loop vs Linked List vs ES6 Set 查找两个匹配的整数

标签 javascript node.js binary-search singly-linked-list

我准备了 2 个 Javascript 函数来查找匹配的整数对,这些整数对相加并返回一个 bool 值。

第一个函数使用这样的二进制搜索:

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

我的问题是:链表方法是真正的线性搜索吗?毕竟我遍历了所有 Node ,而我的外循环遍历了初始数组。

这是我的 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;
}

更新:

根据目前的评论,回去再考虑一下这个问题是个好主意。

感谢 @nem035 对小型数据集的评论,我运行了另一个测试,但这次使用 100,000 1 到 8 之间的整数。我将 9 分配给第一个和最后一个位置并搜索 18 以确保将搜索整个数组。

感谢@Oriol,我还包含了相对较新的 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)

总结:

所以看起来链表对于高达 ~1,000 的较小数据集来说确实很快,而 ES6 集对于较大的数据集来说非常好。 尽管如此,For 循环 在所有测试中都是明显的赢家。

所有 3 种方法都将随数据量线性扩展。

请注意:ES6 Set 不向后兼容旧浏览器,以防必须在客户端完成此操作。

最佳答案

不要使用这个。使用一套。

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

就是这样。 addhas 都保证平均是次线性的(可能是常量)。

关于Javascript - For loop vs Linked List vs ES6 Set 查找两个匹配的整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41755864/

相关文章:

node.js - Mongoose 使用 SSL digital ocean 与 CA_CERT 连接

java - 编写通用的二分查找方法

PHP - cURL 发布到网站 -> 模拟浏览器(执行 javascript) -> 返回 html 结果

javascript - Laravel Jquery Ui Ajax 发布到 Controller 并为 Blade 获取值(value)

javascript - 从一个 polymer 组件调用一个函数到另一个

Node.js 和express 无法获取/

javascript - 如何在选择下拉菜单中设计有序列表

javascript - 如果它们都是 promise ,我如何执行多次计数并使用最高的计数?

java - 二分查找算法的正确方法

java - 有效地找到排序数组中的整数数量