在迭代复杂对象时避免嵌套 for 循环

Question

我的应用程序中有一个比赛表，其中包含已安排比赛的详细信息

我有一张user桌子和user_match一张桥桌。

user_match下表指定了有关哪个用户关注哪场比赛以及支持哪支球队的信息。

现在，在我的控制器方法中，我将返回今天的预定比赛，并同时检查登录用户是否遵循今天的预定比赛。

问题是我必须在流程复杂度 O(n^2) 中运行两个嵌套的 for 循环。首先，我迭代当前的匹配项，然后对于当前的每个匹配项，我迭代用户关注的所有匹配项并检查当前匹配项是否存在。我希望如果我能摆脱嵌套的 for 循环，是否有更好的方法来处理这个问题。

@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 1

您提供的列表有些笨拙，因为您通过 ID 搜索 Map，它是对象的子级，因此它看起来像一个 O(n^2) 嵌套 for 循环，当它可以优化为 O(n ）。

相反，通过 ID 将 List 转换为 HashMap，时间复杂度为 O(n)。

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

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

这为我们提供了一个通过索引映射的 HashMap，以及一个带有 ID 的键集。现在我们不必一遍又一遍地迭代 Match。相反，我们可以执行 O(1) get。

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

    }
}

正如您所看到的，for 循环已被分开，因此您不必为每个匹配都执行 UserMatch 信息，而是执行一次 UserMatch 信息，然后从 Map 执行 O(1) 操作，因此性能为 O(2n ) = O(n)。