Lookup an array against another with performance

Question

I got an initial array, I am checking against another array to find how many objects have at least one instance of the Domain in data.

I wonder if there is a more performant way to achieve the same goal.

const data = [
  {
    Domain: 'google.com',
    '# Reocurring Domains': 0
  },
  {
    Domain: 'apple.com',
    '# Reocurring Domains': 0
  },
  {
    Domain: 'facebook.com',
    '# Reocurring Domains': 0
  }
]

const domains = [
  {
    'google.com': true,
    'microsoft.com': true,
    'google.com': true
  },
  {
    'apple.com': true,
    'microsoft.com': true,
    'twitter.com': true
  },
  {
    'facebook.com': true,
    'apple.com': true,
    'facebook.com': true
  }
]

for (const obj of data) {
  let count = 1
  for (const entry of domains) {
    if (entry[obj.Domain]) {
      obj['# Reocurring Domains'] = count++
    }
  }
}

console.log(data)

In there any way to this with a more performant approach?

Answer 1

You could create a look up table (a simple object) where you can pre calculate the amount of times a domain is in the repeated in the domains array, this reduces the algorithmic complexity of your current solution which is n * m (dataElements * domainElements)

Whereas my suggestion has a lower complexity of (n + m)

const data = [
    {
        Domain: 'google.com',
        '# Reocurring Domains': 0
    },
    {
        Domain: 'apple.com',
        '# Reocurring Domains': 0
    },
    {
        Domain: 'facebook.com',
        '# Reocurring Domains': 0
    }
]

const domains = [
    {
        'google.com': true,
        'microsoft.com': true,
        'google.com': true
    },
    {
        'apple.com': true,
        'microsoft.com': true,
        'twitter.com': true
    },
    {
        'facebook.com': true,
        'apple.com': true,
        'facebook.com': true
    }
]

const domainsObj = {}

domains.forEach(domain => {
    Object.keys(domain).forEach(key => key in domainsObj ? domainsObj[key] += 1: domainsObj[key] = 1)
})

data.forEach(element => element['# Reocurring Domains'] = domainsObj[element.Domain]);

console.log(data);

This approach increases memory usage, but improves calculation speed.