Java에서 정렬 된 반복 가능한 효율적인 정렬 된 구조

Question

나는 StackOverflow 관련 질문을 살펴 보았는데, 내가 찾은 것을 찾지 못했다고 생각합니다.

나는 다음과 같은 특성을 가진 자바 구조를 원하는 :

의 Iterable

1. 결과 순위를
2. 제네릭
3. O (logn) (이상) 삽입 및 제거
4. O (logn 지원) (또는 그 이상) 요소 액세스
5. 중복 항목 허용

왜? 나는 k-nearest distance 알고리즘을 구현 중이다. 데이터 수집의 각 점에 대해 가장 가까운 k 번째 점까지의 거리를 찾아야합니다. 알고리즘은 각 쌍의 점을 반복하고, 두 점 사이의 거리를 계산 한 다음, 거리가 해당 목록의 다른 요소보다 가까운 경우 해당 점을 가장 가까운 거리의 정렬 된 구조에 추가합니다. 여기에 설명하는 몇 가지 코드는 다음과 같습니다

ArrayList<SortedThing<Double>> nearestDistances = new ArrayList<SortedThing<Double>>(numPoints); 
for (int i = 0; i < numPoints; i++) { 
    nearestDistances.add(new SortedThing<Double>(k)); 
} 

for (int point = 0; point < numPoints; point++) { 
    for (int otherPoint = point+1; otherPoint < numPoints; otherPoint++) { 
     double distance = computeDistance(point, otherPoint); 

     if (nearestDistances.get(point).size < k) 
      nearestDistances.get(point).add(distance); 
     else if (nearestDistances.get(point).last() > distance) { 
      nearestDistances.get(point).removeLast(); 
      nearestDistances.get(point).add(distance); 
     } 

     if (nearestDistances.get(otherPoint).size < k) 
      nearestDistances.get(otherPoint).add(distance); 
     else if (nearestDistances.get(otherPoint).last() > distance) { 
      nearestDistances.get(otherPoint).removeLast(); 
      nearestDistances.get(otherPoint).add(distance); 
     } 
    } 
} 

전에 제안을 다음과 같은 내장 내가 그들을 사용하지 않는 이유 자바 클래스, 여기의 :

1. PriorityQueue 인을 -에 액세스 할 수 없음 거기에 마지막 요소
2. TreeSet의이 - O (nlogn) 시간에 일종의 그것, 그것으로 모든 n-1 개의 거리를 삽입, 그래, 내가 ArrayList를 사용할 수 다음 제거 - 중복 거리를
3. ArrayList를 허용하지 않습니다 k 번째 요소. 그러나 이것은 O (nk) 공간 대신에 O (n^2) 공간을 필요로합니다.
4. ArrayList - 또는 정렬 된 ArrayList를 유지하면서 마지막 요소를 제거하고 올바른 위치에 새 요소를 삽입 할 수 있지만 각 삽입에 대해 O (k) 시간이 걸리고 O (logk) 삽입 위치.

누구나 이러한 구조를 알고 있습니까? 나는 최근에 이것에 대해 많은 생각을 해왔고, Java가 그러한 구조를 제공하지 않는다는 것을 알게되었습니다.

Answer 1

가장 가까운 이웃 검색을 수행하는 경우 k-d tree을 사용할 수 있습니다. here's a Java implementation (.jar 파일의 \ bak 디렉토리에서 소스 코드를 찾으십시오.)

그렇지 않으면 TreeMap을 사용하는 것이 좋습니다. 여기서 값은 키 중복의 수입니다 (1은 중복이 없음을 의미하고 2는 하나를 의미 함). 중복 등)

Map<Key, Integer> map = new TreeMap<>(); 

if(map.containsKey(key)) { 
    map.put(key, map.get(key) + 1); 
} else { 
    map.put(key, 1); 
} 

Answer 2

Apache Commons Collections에서 확인 TreeBag.

TreeBag은 항목을 보유하기 위해 TreeMap을 사용합니다.