Can this algorithm be made more efficient?-CodePudding

Currently I have an algorithm that runs to compare to different arrays of objects.

const allGroups = [{ id: '12345', name: 'groupOne'}, {id: '23421', name: 'groupTwo'},
{id: '28182', name: 'groupThree'}]


const clientsGroups = [{ id: 'abcde', clientGroupID: '12345'}, {id: 'dfcdae', clientGroupID: '93282'},
{id: 'jakdab', clientGroupID: '28182'}, {id: 'oiewad', clientGroupID: '93482'}]

const updateClientGroups = (allGroups, clientsGroups) => {
  let allGroupsCopy = [...allGroups];
  for (let i = 0; i < allGroupsCopy.length; i  ) {
    const allGroupsId = allGroupsCopy[i].id;
    for (let j = 0; j < clientsGroups.length; j  ) {
      if (allGroupsId === clientsGroups[j].clientGroupID) {
        allGroupsCopy[i] = {
          ...allGroupsCopy[i],
          inGroup: true,
          clientGroupID: clientsGroups[j].id,
        };
      }
    }
  }
  return allGroupsCopy;
};

I check two different arrays of objects, if the id of allGroups matches the clientGroupID of clientGroups, I mutate the 'allGroupsCopy' to have 'inGroup: true' and add in the id of the clientsGroups.

The problem with this algorithm is it runs in n^2 time. Is there a more efficient way to do this?

CodePudding user response：

If you change allGroups structure from array to map, you can do the job in linear time. Something like:

const allGroups = {
    '12345': { id: '12345', name: 'groupOne'}
    ...
}
const updateClientGroups = (allGroups, clientsGroups) => {
  const clientGroupsMap = {};
  clientsGroups.forEach(({clientGroupID}) => 
     if(allGroups[clientGroupID]) {
         clientGroupsMap[clientGroupID] = {...allGroups[clientGroupID], inGroup: true};
     }
  );
  return {...allGroups, ...clientGroupsMap};
};

CodePudding user response：

Without changing the original arrays, could this be the an optimization ?

const allGroups = [
  { id: "12345", name: "groupOne" },
  { id: "23421", name: "groupTwo" },
  { id: "28182", name: "groupThree" },
];

const clientsGroups = [
  { id: "abcde", clientGroupID: "12345" },
  { id: "dfcdae", clientGroupID: "93282" },
  { id: "jakdab", clientGroupID: "28182" },
  { id: "oiewad", clientGroupID: "93482" },
];

const updateClientGroups = (groups, clients) => {
  return clients.reduce((acum, current) => {
    const isInGroup = groups.find((group) => group.id === current.clientGroupID);

    acum.push({
      ...current,
      inGroup: Boolean(isInGroup),
    });

    return acum;
  }, []);
};

updateClientGroups(allGroups, clientsGroups)