我准备了 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;
}
就是这样。 add
和 has
都保证平均是次线性的(可能是常量)。
关于Javascript - For loop vs Linked List vs ES6 Set 查找两个匹配的整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41755864/