CODEWITHSUNDEEP
javaperformance
techPackets
techPackets

Reputation: 4504

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;
}

Upvotes: 4

Views: 9179

Answers (1)

Compass
Compass

Reputation: 5937

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).

Upvotes: 5

Related Questions