선형 시간의 목록을 포함하는지도를 반복하십시오.

Map<Object,List<Object>>을 반복하고 List<Object> (값)에있는 객체 중 임의의 객체가 특정 조건을 충족시키는 Map.Entry을 추출하고 싶습니다.
나는이 두 가지 방법을 볼 수
선형 시간의 목록을 포함하는지도를 반복하십시오.

1) 확실한 방법)이 목록을 통해 항목 - 설정 및 루프 (값을 추출하는 것입니다.
2)이 맵을 구아바의 멀티 맵으로 변환하고 값을 반복하고 조건이 맞으면 키에 플래그를 지정하고 맵에서 실제 목록을 추출하십시오.

저는 비선형 해법이므로 첫 번째 방법은 피하고 싶습니다. 이 작업을 수행하는 다른보다 효율적인 방법이 있습니까?

출처

2017-03-21 user2780757

첫 번째 방법은 선형 시간이 아닐까요? 객체의 총 개수는 선형입니다. 이 두 가지 솔루션은 동일합니다. –

나는 왜 1) 선형 시간이 없어야하는지 이해하지 못한다. 또한 프로파일 링으로 확인 된 성능 문제가 있습니까, 아니면 그냥 추측입니까? – Axel

첫 번째 접근 방식에서는 먼저 모든 항목 집합을 반복해야합니다. 각 반복에서 조건을 확인하기 위해 값을 다시 루프해야합니다. 따라서 중첩 된 루프가됩니다. 이것을 비선형으로 만들지 않겠습니까? – user2780757

아니요, 각 값을 확인해야하는 경우 모든 값을 검토해야합니다. 모든 값을 처리하려면 다음과 같이해야합니다.

public List<Object> getEntriesThatMeetCondition(Map<Object, List<Object>> input) { 
    List<Map.Entry> output = new ArrayList<>(); 

    Iterator it = input.entrySet().iterator(); 

    while(it.hasNext()) { 
     Map.Entry entry = (Map.Entry) it.next(); 

     List inputList = (List<Object>) entry.getValue(); 

     for(Object object : inputList) { 
      if(meetsCondition(object)) { 
       output.add(entry); 
      } 
     } 
    } 
}

각 항목을 한 번씩 처리한다는 것은 선형입니다.

출처

2017-03-21 17:51:36

선형 시간의 목록을 포함하는지도를 반복하십시오.

답변

관련 문제