underdog underdog - 16 days ago 4
Java Question

Avoiding nested for loops in iterating through complex objects

I have a match table in my app which holds the details of the matches scheduled

enter image description here

I have a

user
table & a
user_match
table which is a bridge table.

user_match
table below specifies info on which user follows which match & supports which team.
enter image description here

Now in my controller method I am returning today's scheduled matches & also check at the same time if the loggedIn user follows the today's scheduled matches.

The problem is I have to run two nested for loops in the process Complexity O(n^2). First I iterate through the current day matches & then for every current day match I iterate through all the matches the user follows & check if the current match is present. I was hoping if I could get rid of the nested for loop, could there be a better way to deal with this.

@RequestMapping(value="/getTodaysMatches", method=RequestMethod.GET, consumes = "application/json", produces = "application/json")
public @ResponseBody List<Match> getMatchesForCurrentDate(){
logger.debug("inside /getTodaysMatches CricketController method");

DateTime currentServerTimeStamp = CricketUtil.getServerDateTime();
List<Match> currentDayMatchList = this.cricketService.fetchMatchesForInputDate(currentServerTimeStamp);
CustomUserDetail myUserDetails = currentUserAccessor.getCurrentLoggedInUser();
User loggedInUser = myUserDetails.getUser();
List<UserMatchInfo> userMatchInfoList = this.cricketService.getUserMatchInfoByUserId(loggedInUser.getUserId());

/*check if the logged in user already follows matches scheduled for today*/

for(Match todaysMatch : currentDayMatchList){
for(UserMatchInfo tmpUserMatchInfo : userMatchInfoList){
String teamFollowedByUser = tmpUserMatchInfo.getSupportingTeam();
Match matchWhichUserFollows = tmpUserMatchInfo.getMatch();
if((matchWhichUserFollows.getMatchId().intValue()) == (todaysMatch.getMatchId().intValue())){
todaysMatch.setLoggedInUserFollowsThisMatch(true);
}

if((todaysMatch.getTeamOne().equals(teamFollowedByUser))){
todaysMatch.setLoggedInUserSupportsTeamOne(true);
}

if((todaysMatch.getTeamTwo().equals(teamFollowedByUser))){
todaysMatch.setLoggedInUserSupportsTeamTwo(true);
}
}
}

return currentDayMatchList;
}

Answer

The lists you've provided are somewhat unwieldy because you search for the Map by ID, which is a child of the Object, so it looks like an O(n^2) nested for loop, when it can be optimized to O(n).

Instead, convert the List into a HashMap by ID for O(n).

HashMap<Integer, Match> matchMap = new HashMap<>();

for(Match m : currentDayMatchList) {
    int id = m.getMatchId().intValue()
    matchMap.put(id, m);
}

This gives us a HashMap that is mapped by indices, and a keyset with the IDs. Now we don't have to iterate through the Match over and over. Instead, we can do an O(1) get.

for(UserMatchInfo tmpUserMatchInfo : userMatchInfoList){
    String teamFollowedByUser = tmpUserMatchInfo.getSupportingTeam();
    Match matchWhichUserFollows = tmpUserMatchInfo.getMatch();
    if(matchMap.get(matchWhichUserFollows.getMatchId().intValue()) {
        //... etc.

    }
}

As you can see, the for loop has been split apart, so rather than doing the UserMatch info for every Match, you're doing the UserMatch info once and then doing an O(1) from the Map, so performance is O(2n) = O(n).