reduce the time complexity of nested for loop

Smokey Dawson

Basically I am trying to bring down the time complexity of a series of functions that I have

const companies = [
    {
     staff: [
      {
        id: 1,
        qualities: [
          {
            id: 2,
            tags: [
              'efficient',
              'hard-working'
            ]
          }
        ]
      }
    ]
  }
]

So I have an array of companies and within that is another array of staff and then again within that there is an array of qualities and finally an array of tags

now I have a predetermined list of tags that I need to match users to for each company like so

companies: [
 xyz: [
   {
    tag: 'smart',
    users: []
   }
 ],
 // ...
];

so basically I need to loop through each pre-determined tag, then loop through each company, then loop through each user and loop through each tag to create this view

so basically something like this

const tags = [
  'smart',
  'hard-working',
  'efficient'
];

getUserTags(tagName) {
  const users = [];
  companies.forEach(company => {
    company.users.forEach(user => {
      user.tags.forEach(tag => {
        if (tag === tagName) {
          users.push(user);
        }
      });
    });  
  });
  return users; 
}

as you can see this is super inefficent and the big O works out to be O(n^4) which is horrible.

How can I solve this?

Bergi

there could be 50 tags […] so for each tag it would have to [call the getUserTags function and] loop through every user and then loop through each users tags to see if its a match to get the total count.

No, that you shouldn't do. Instead, loop only once through the users and the tags of each user, and collect them in a array-by-tagname map data structure. Use something like

getUsersByTags(companies, tags) {
  let map = new Map();
  for (const tag of tags) {
    map.set(tag, []);
  }
  for (const company of companies) {
    for (const user of company.staff) {
      for (const quality of user.qualities) {
        for (const tag of quality.tags) {
          const n = tag.name;
          if (map.has(n))
            map.get(n).push(user);
        }
      }
    }
  }
  return map;
}

You cannot avoid traversing the whole company-staff-quality-tag structure to access all your tag data. Just make sure to not do it more than once.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related