java : 주어진 키 범위 내에서 값의 개수를 구아바 멀티 맵

Question

나는 중복 키를 포함하여 TreeMultimap<Integer, String>입니다.

나는, 특정 키 범위 내에 값의 수를 얻기 위해 너무와 O (logN) 시간 복잡도를 원한다.

제가 먼저 asMap() 방법을 사용하고 필요 범위 submap를 생성하고 그 크기를 인출하여 SortedMap에 TreeMultimap 변환하여 시험해 보았다.

SortedMap<Integer, Collection<String>> sortedMap = mapList.getTmm().asMap(); 
return sortedMap.subMap(beg,end).size(); 

는 복잡도 O (logN)을 갖는?

또한 여기서 문제가 발생했습니다. TreeMultimap이 SortedMap으로 변환되면 값은 Collection 클래스의 개체입니다. 즉, TreeMultimap에 중복 키가있는 키 - 값 쌍이 하나의 Collection 클래스에 포함됩니다. 따라서 size() 메서드는 잘못된 값을 반환합니다.

다른 방법이 있나요? 도움을 주시면 감사하겠습니다.

Answer 1

당신은 원거리 쿼리에 대한 방법을 가지고 SortedMultiset을 시도 할 수 있습니다 :

subMultiset을 :

는 LOWERBOUND와 UPPERBOUND 사이의 범위에 제한이 MULTISET의 뷰를 돌려줍니다.

샘플 코드 :

import com.google.common.collect.*; 

public class GuavaMultiMap { 
    public static void main(String [] args) { 
     Multimap<Integer, String> map = TreeMultimap.create(); 
     map.put(0, "-1"); 
     map.put(1, "a"); 
     map.put(1, "b"); 
     map.put(2, "c"); 
     map.put(2, "d"); 
     map.put(3, "e"); 

     SortedMultiset<Integer> keys = TreeMultiset.create(); 
     keys.addAll(map.keys()); 

     SortedMultiset<Integer> range = keys.subMultiset(1, BoundType.CLOSED, 3, BoundType.OPEN); 
     System.out.println(range.size()); 
    } 
} 

출력 :이 줄 keys.addAll(...);이 O(n) 때문에는 4

위의 코드는 O(log(N)) 시간에 작동하지 않습니다. 그러나 SortedMultiset을 Multimap과 함께 업데이트하는 경우 시간을두고 공간을 교환 할 수 있어야합니다.