如何优化从O(n^2)到O(n)或类似的嵌套for循环的typescript ?

Question

我有两个对象数组，即arr1和arr2，假设它们的长度相等。两者的内部结构均为{id: 'some random id', ...}。我想遍历arr1中的每个对象，如果该对象的id不属于arr2，则添加一个参数checked=false，否则添加一个checked=true。

下面是我现在的代码:

for (const i of arr1) {
i.checked = false;
for (const j of arr2) {
if (i.id === j.id) {
i.checked = true;
}
}
}

我如何优化它?任何小于0 (n^2)的建议都是值得赞赏的。

Answer 1

你可以创建一个Set，它们有O(1)个访问权限使得你的循环为O(n)

const idSet = new Set(arr2.map(i => i.id))
for (const i of arr1) {
i.checked = idSet.has(i.id);
}

Answer 2

您可以使用Set从第二个数组中准备id，然后使用具有0(1)操作的Set.prototype.has。

const arr1 = [{id: 1}, {id: 2}, {id: 3}, {id: 4}]
const arr2 = [{id: 2}, {id: 5}, {id: 4}, {id: 6}]
const ids = new Set(arr2.map(({ id }) => id))
for (const item of arr1) {
item.checked = ids.has(item.id)
}
console.log(arr1)
/* Result
[
{ id: 1, checked: false },
{ id: 2, checked: true },
{ id: 3, checked: false },
{ id: 4, checked: true }
]
*/

快速基准:

Running "Array check (1000 elements)" suite...
Progress: 100%
Set.has:
15 671 ops/s, ±0.38%   | fastest
two loops:
543 ops/s, ±0.48%      | slowest, 96.54% slower
Finished 2 cases!
Fastest: Set.has
Slowest: two loops