Searching a nested data structure for 2 attributes

Question

So I have the following data structures

export class BudgetGroupInfo {
    name: string;
    bcInfo: BudgetCatInfo[] = [];
}

export class BudgetCatInfo {
    name: string;
    description: string;
    bcAccounts: BCAccountInfo[] = [];
}

export class BCAccountInfo {
  name: string;
  description: string;
}

What I need to be able to do is find which BudgetGroupInfo contains both BudgetCatInfo.name and BCAccountInfo.name

This is what I have so far and it works, but I feel like this isn't the most efficient want to do this.

getGroupInfo(budCat: string, account: string, budgetGroupInfo: BudgetGroupInfo[]): BudgetGroupInfo {
    let groupInfo = null;

    budgetGroupInfo.forEach(infoGroup => {
      infoGroup.bcInfo.filter(bcInfo => bcInfo.name == budCat)
      .map(bcInfo => bcInfo.bcAccounts)
        .forEach(accounts => {
            const acctInfo: BCAccountInfo = accounts.find(acct => acct.name == account);
            if(acctInfo) {
              groupInfo = infoGroup;
            }
          });
      })

    return groupInfo;
  }

1. First I go through the groups and find which ones have the specific budCat
2. I take the valid BudgetCatInfo and map the bcAccount array
3. I search that array and look for the specified account
4. If I find it then I set it for return.

Just a note that there won't always be a result and there will never be multiple matches.

Answer 1

You are correct, this is an inefficient way to do this search. Even if the groupInfo is found in the first iteration of each loop, you still go through (almost) every single element.

First a couple comments on your code:

1. The return type is lying to me. The function doesn't return BudgetGroupInfo. It returns BudgetGroupInfo | null. The fact that this doesn't complain means that you don't have strictNullChecks on. In my experience, this is the single most helpful feature available. It will let TypeScript tell you about a whole class of errors that it otherwise ignores.

2. filter.map.forEach is fine if you know only a few elements will be looped over, but if you end up having a lot of data, this will end up taking 3x the time. I don't find it that helpful for readability here, so I'd just pull the checks into the loop function.

3. TypeScript is generally pretty good about figuring out what variable types are. You don't need to manually type the result of Array#find.

The main trick for optimizing this is to make use of Array#some and change the outer forEach into a find. Here's how I'd write your function:

function getGroupInfo(budCat: string, account: string, budgetGroupInfo: BudgetGroupInfo[]) {
    return budgetGroupInfo.find(group => {
        return group.bcInfo.some(info => {
            if (info.name !== budCat) return false;
            return info.bcAccounts.some(acct => acct.name === account);
        });
    });
}

There are a few subtle differences:

1. This returns undefined instead of null if there is no result. If this is a problem, it's a straightforward fix.

2. I removed the return type of the function. TypeScript can infer it easily in this case, and it will still be correctly inferred if you turn on strictNullChecks

3. If there is multiple matches (I know you said there wouldn't be but...) my version will return the first match, while yours returns the last match.