Javascript的 – 循环VS链接列表与ES6设置find两个匹配的整数

我已经准备了2个Javascript函数来查找匹配的整数对，并且返回一个布尔值。

第一个函数使用如下的二进制search： 

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

对于第二个函数，我实现了我自己的链接列表，在这里我添加了互补的整数，并在链接列表中查找值。 如果在链接列表中find值，我们知道有一个匹配。 

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

当我运行这两个函数时，我清楚地看到链接列表search执行速度快了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

这里是我的问题：链表是否是一个真正的线性search？ 毕竟我遍历所有的节点，而我的外循环遍历初始数组。

这是我的LinkedListsearchfunction： 

 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对小数据集的评论，我进行了另一次testing，但是这次是在1到8之间的100,000个整数。我将9分配到第一个和最后一个位置，并search了18，以确保search整个数组。

由于@Oriol，我还包括了相对较新的ES6 Setfunction。

顺便说一句@Oriol和@Deepak你是对的。 第一个函数不是二进制search，而是O（n * n）search，没有对数复杂度。

事实certificate，我的链表实现是所有search中最慢的。 我为每个函数分别运行了10次迭代。 结果如下： 

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

这里对10,000,000个整数的数据集进行相同的testing： 

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

概要：

所以看起来链表对于较小的数据集来说真的很快〜1000，而ES6 Set对于较大的数据集来说是很好的。 尽pipe如此， For循环在所有testing中都是明显的赢家。

所有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和都保证是次线（可能是恒定的）。

您可以通过对数组进行预先sorting然后使用真正的二进制search来对其进行优化。 

 // 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');

首先find2PairsBySumLog函数不是二进制search，它是一种parsing数组中所有元素的蛮力方法，最坏情况下的时间复杂度应该是O（n * n），第二个函数是一个线性search，为什么你得到快速运行的第二个方法，第一个函数，即find2PairsBySumLog你可以做什么是初始化二进制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; } }
Interesting Posts