Avoiding nested for loops in iterating through complex objects

Question

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

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.

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

That is not O(n^2), that is O(n*m) which really is not a big deal. Are you actually facing performance problems - this sounds more like premature optimization? — luk2302
– luk2302, Commented Nov 23, 2016 at 18:54
Then "forget" about performance. Instead focus on creating readable code. For example by learning about the "single responsibility" and the "single layer of abstraction" principles. Which would both help improving the quality of your code. — GhostCat
– GhostCat, Commented Nov 23, 2016 at 18:56
Option 1: query the database in a more efficient way by simply joining the two tables there already. That way you can make use of the indexing and performance optimizations the database has in place. Option 2: do not change anything since the code is presumably not a problem. — luk2302
– luk2302, Commented Nov 23, 2016 at 18:57
If you're really against nested fors and not willing to change the DB query, the alternative is to do the intersection in Java. More code, more hashmaps, no nested for loops, but ultimately the same result. — Compass
– Compass, Commented Nov 23, 2016 at 19:07

Compass · Accepted Answer · 2016-11-23 19:53:49Z

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

Collectives™ on Stack Overflow

Avoiding nested for loops in iterating through complex objects

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related