javascript - 大数组查找优化的一个问题？

Question

var arr1=[2,4,5,7,10]var arr2=[1,2,3,4,5,6,7,8,9,10,11,1,12,5......]//假如这个数组中存在大量数据arr1.map((item)=>{  arr2.map((current,index)=>{      if(item == current){            .....            arr2.splice(index,1);//如果每次符合条件后，我就把符合过条件的数据从这个大数组中删除，减少下一次循环时候的数据量。结果发现这样不行，结果不对了。        }  })})

我有这样两个数组需要循环匹配出结果，如果没有用splice，出来的结果是正确的。但是我想优化下循环查找的代码，发现结果不对了

后来我又试了下splice函数

发现果然结果和我预想的不同了

请问上面的代码我该如何降低每次的循环量？

Answer 1

首先Array.prototype.map()主要是用来将一个数组转换为一个新的数组，如果只是遍历的话，规范来讲不应该使用 map，而是使用 forEach 或者是 fori、for-of、for-in 等其他单纯用来遍历的方式。

如果需要在循环中删除元素，那么删除元素后需要同时修改索引位置才行，示例如下：

const arr1 = [2, 4, 5, 7, 10];const arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 12, 5];for (let i = 0; i < arr2.length; i += 1) {  for (const item of arr1) {    if (item === arr2[i]) {      arr2.splice(i, 1);      i -= 1;    }  }}

另外，可以这个需求可以简洁一点实现：

arr2.filter((item) => !arr1.includes(item));

Answer 2

结果不对，是因为你在map循环中splice，splice会减少数组长度，但是map不会停留当前位置，比如你把下标为5的元素删除了，下标为6的元素进位为下标5，下次应该还是计算下标5，但是map直接计算下标6，跳过了应该继续计算的下标5，和for循环没有把下标减1一个道理。

简单计算可以直接使用filter配合indexOf

arr2.filter(item => arr1.indexOf(item) >= 0)

这样写起来简便，在性能上也有优化，但是并没有减少循环次数，减少循环次数需要使用对象的键值对

let obj = arr1.reduce((o, i) => {    o[i] = true    return o}, {})arr2.filter(i => !!obj[i])

Answer 3

你用splice去删除元素，数组的索引已经变了，得到的结果自然不是你想要的的，不要在遍历集合的时候增加或者删除集合的元素，很容易带来问题。使用一个新数组来存储即可：

var arr1 = [2, 4, 5, 7, 10];var arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 12, 5, ...]; // 假设这个数组中存在大量数据var matchedItems = [];arr1.forEach((item) => {  arr2.forEach((current, index) => {    if (item === current) {      matchedItems.push(current);    }  });});matchedItems.forEach((item) => {  var index = arr2.indexOf(item);  if (index !== -1) {    arr2.splice(index, 1);  }});

Answer 4

const arr1 = [2, 4, 5, 7, 10];const arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 12, 5];// 直接用 includes 来判断是否存在于 arr1 中const r1 = arr2.filter(n => !arr1.includes(n));console.log(r1);// [1, 3, 6, 8, 9, 11, 1, 12]// 如果 arr1 也比较大，可以先生成集合，通过集合来检查会更快；生成集合的同时也可以去重const arr1Set = new Set(arr1);const r2 = arr2.filter(n => !arr1Set.has(n));console.log(r2);// [1, 3, 6, 8, 9, 11, 1, 12]

如果你确实需要通过 splice 来修改原数组，可能从最后一个元素开始，按逆序来处理，这样就不存在索引移位的问题。不过理论上来说，删除索引是个重量级操作 —— 对真数组来说，每次删除元素都会造成后面的所有元素重排，非常耗时。

如果又想改原数组，又想优化，就需要自己写算法。假如你的是作业，那么接下来的东西就是你需要写的内容了：

1. 找到第一个需要删除的位置 x，记录 s = x
2. 从 x + 1 开始找到下一个不需要删除的位置 y
3. 从 y + 1 开始找到再下一个需要删除的位置 z
4. 将从 y 到 z（不含）之间的元素挪到 s 处，记录结束位置 p（此时 p = s + (z - y)）
5. 赋值 s = p; x = z，从第 2 步开始重复处理
6. 注意上述循环的退出条件和剩余处理

大概画了个示意图，看你能懂不