嵌套for循環中通過複雜的迭代避免對象

我有一個user表&一個user_match表比賽這是一個橋樑的細節表。

user_match下表指定了哪個用戶遵循哪個匹配&支持哪個團隊的信息。

現在在我的控制方法，我回到今天的比賽安排也&檢查的同時，如果用戶的loggedIn跟隨今天的計劃匹配。

問題是我必須在進程Complexity O（n^2）中運行兩個嵌套循環。首先我遍歷當天的比賽&，然後對於每一天的比賽，我遍歷所有比賽用戶按照&檢查是否存在當前比賽。我希望能夠擺脫嵌套循環，能否有更好的方法來處理這個問題。

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

來源

2016-11-23 underdog

索引數據可能（在某些地圖中） – 2016-11-23 18:52:40

這不是O（n^2），那就是O（n * m），這實際上並不是什麼大不了的事情。你是否真的面臨性能問題 - 這聽起來更像是不成熟的優化？ – luk2302

不，我不面臨任何性能問題。開發工作正處於初始階段，所以我希望能夠降低複雜性，避免嵌套for循環，但不能想出任何其他方式來處理這種情況。避免嵌套循環有點經驗法則不是嗎？ – underdog

您提供的名單，因爲您搜索的ID的地圖，它是對象的孩子有些笨重，所以它看起來像一個爲O（n^2）嵌套for循環，當它可以優化爲O（n）。

取而代之，將List轉換爲一個HashMap，ID爲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信息一次，然後從地圖（1）做一個O ，所以性能是O（2n）= O（n）。

來源

2016-11-23 19:26:49 Compass

嵌套for循環中通過複雜的迭代避免對象

回答

相關問題