How to optimize typescript nested for loop from O(n^2) to O(n) or similar?-CodePudding

I have two arrays of objects namely arr1 and arr2 assuming the length of both are equal. Both have {id: 'some random id', ...} inner structure. I want to iterate through each object in arr1 and add a parameter checked=false if id of that object didn't belong to arr2 else add a checked=true.

Here is my present code:

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

How do I optimize it? Any suggestions lesser than O(n^2) is appreciated.

CodePudding user response：

You can create a Set, they have O(1) access making your loop O(n)

const idSet = new Set(arr2.map(i => i.id))

for (const i of arr1) {
      i.checked = idSet.has(i.id);
 }

CodePudding user response：

You can use Set to prepare IDs from the second array, and then use Set.prototype.has which id O(1) operation.

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 }
]
*/

Quick benchmark:

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