삽입 후 HashMap 값의 평균을 계산하십시오.

Question

새 키/값 쌍이 삽입 될 때마다 HashMap 값의 두 가지 값을 효율적으로 계산하고 싶습니다.

3 4 
5 6 
8 8 
1 3 
6 8 <- Latest insertion 

최신 삽입 값 8와 키 6이었다

은 가정하자 우리는 현재이 HashMap<Double, Double> 있습니다.

계산할 첫 번째 평균은 키가 삽입 된 것보다 작은 모든 값 (6)으로 구성됩니다.

이

열쇠 3,5,1 4,6,3의 값이므로, 평균은 (4+6+3)/3=4.3...

두번째 의미는 "반대"이고, 그래서보다 6 모든 키에 대한 모든 값의 평균 크다.

값이 1 인 8 키는 8/1=8으로 표시됩니다.

이제 새로운 키/쌍 삽입됩니다 :

3 4 
5 6 
6 8 
8 8 
1 3 
4 9 <- Latest insertion 

그래서 다시, 우리는 4보다 작은 키를 사용하여 모든 값의 평균을 계산해야합니다.

이

열쇠 3,1 대한 값 4,3이고, 그래서 "작은 평균"지금 (4+3)/2=3.5

은 "큰 평균"지금 키/값 쌍에 대한 5/6,6/8,8/8(6+8+8)/3=7.3...이다.

본래의 구현은 다음과 같은 수 있습니다 :

public class CalculateMapMean { 

     private double smallerMean = 0.0; 
     private double greaterMean = 0.0; 

     private HashMap<Double, Double> someMap = new HashMap<Double, Double>(); 

     public void calculateMeans(double latestInsertedKey) { 
      double sumGreater = 0; 
      double sumSmaller = 0; 
      double sumGreaterCount = 0; 
      double sumSmallerCount = 0; 
      for (Map.Entry<Double, Double> entry : someMap.entrySet()) { 
       double key = entry.getKey(); 
       double value = entry.getValue(); 
       if (key > latestInsertedKey) { 
        sumGreater += value; 
        ++sumGreaterCount; 
       } 
       else if (key < latestInsertedKey) { 
        sumSmaller += value; 
        ++sumSmallerCount; 
       } 
      } 
      if (sumGreaterCount != 0) { 
       greaterMean = sumGreater/sumGreaterCount; 
      } 
      else { 
       greaterMean = 0.0; 
      } 
      if (sumSmallerCount != 0) { 
       smallerMean = sumSmaller/sumSmallerCount; 
      } 
      else { 
       smallerMean = 0.0; 
      } 
     } 
    } 

질문 수단의 계산이 극적으로 하나가 모든 키 반복을 가지고하지 않도록하는 TreeMap 또는 다른 datastrure 개선 할 수있는 경우이다 모든 삽입에.

전 계산을 재사용하는 우아한 방법이 있습니까?

Answer 1

내가 생각할 수있는 유일한 방법입니다 (균형 이진 검색 트리를 유지하여지도에 대한 모든 변경 O(n) 시간 이하로 얻을 수 BBST) 키를 누릅니다. 모든 노드에서 당신은 몇 가지 추가 필드

• 을 유지할 필요가 해당 노드
• 해당 노드

재조정 a를 루트로 모든 노드의 값의 합계를 루트로하는 서브 트리의 노드 수 삽입/삭제 후 BBST는 O(log n) 시간이 걸립니다. 동일한 잔액 작업에서 O(log n) 시간 (시간이 걸리는 O(log n) 작업을 수행하기 때문에)의 수와 합계도 업데이트 할 수 있습니다.

정확한 의미를 얻으려면 트리를 가로 질러 올바른 카운트를 추가해야합니다. 간단한 예를 들어 봅시다. 다음 7 가지 키 - 값 쌍이 있다고 가정합니다. 해당 BBST가 어떻게 보이는지 상상해보십시오. (8, 4) - - 루트에서

(3, 5) (4, 3) (7, 1) (8, 4) (11, 3) (12, 1)(13, 3) 

총 수와 합이 저장됩니다 [7, 20]. 왼쪽 하위 트리 루트 인 (4, 3) - 해당 하위 트리의 총 수와 합계는 [3, 9]입니다. 이제 트리에서 깊이의 함수로 이러한 추가 값을 그립니다.

[   7, 20  ] 
[ 3, 9 ][ 3, 7 ] 
[1, 5][1, 1][1, 3][1, 3] 

이제 키 10으로 새 튜플을 추가한다고 가정 해 보겠습니다. 루트에서 나무를 가로 지르기 시작합니다. 8 < 10이므로 왼쪽 하위 트리를 탐색 할 필요가 없습니다. 하위 트리의 모든 키가 10보다 작기 때문에 캐시 된 값 [3, 9]을 사용할 수 있습니다. 일부 하위 키는 10보다 작고 일부 키는 더 클 수 있기 때문에 오른쪽 하위 트리의 경우 재귀해야합니다. 12 > 10이므로 을 직접 사용할 수 있으므로 올바른 하위 트리를 트래버스하지 않아도됩니다.

트리의 모든 계층에서 한 분기를 무시하고 다른 분기에서 재귀 할 수 있습니다. 따라서 마지막으로 삽입 한 키보다 작은 키의 총 값과 개수를 찾고 마지막으로 삽입 한 키보다 큰 키의 값도 O(log n) 시간이 걸립니다.

Answer 2

당신은 당신의 구현 내에서이 값을 저장할 수 있습니다, 뭔가 같은 :

public class MyHashMap extends HashMap<Double, Double> { 
    private double sum = 0; 

    @Override 
    public void put(Double key, Double value) { 
     super (key, value); 
     if (containsKey(key)) { 
      sum -= get(key); 
     } 
     sum += value; 
     super(key, value); 
    } 

    @Override 
    public void putAll(Map<? extends Double, ? extends Double> map) { 
     for (Map.Entry<? extends Double, ? extends Double> entry: map) { 
      put(entry.getKey(), entry.getValue()); 
     } 
    } 

    @Override 
    public void remove(Object key) { 
     Double value = get(key); 
     if (value != null) 
      sum -= value; 
     super(key); 
    } 

    public double getMean() { 
     return sum/size(); 
    } 
} 

Answer 3

예, TreeSet이 도움이됩니다.

이있는 요소가 있다고 가정하십시오. 튜플을 트리 집합에 유지하면 tailSet(e)을 사용하여 v보다 큰 값을 갖는 모든 요소를 ​​가져올 수 있습니다. headSet(e)에 대해서도 마찬가지입니다. 그런 다음 일반적으로 그 세트의 숫자 평균을 찾을 수 있습니다 ( O(n*log(n)) 비용).비용으로 새 튜플을 삽입하십시오.

저는 키와 값 외에도 낮은 키를 가진 요소의 수와 그 평균을 추적하는 균형 이진 트리를 사용하여 훨씬 더 빠르게 할 수 있다고 생각합니다. 더 높은 값을 갖는 오른쪽 분기의 요소에 대해서도 마찬가지입니다. 그런 다음 새 요소가 오면 삽입 점을 이진 검색하고 발생한 평균을 추적하여 더 높은 숫자와 낮은 숫자의 평균을 적절히 구성합니다. 모든 것이 돌아 다니고, average 라벨의 무결성을 보장해야하기 때문에 균형 잡힌 비트를 구현하는 것이 까다로울 것이라고 생각합니다.

그렇다고해서 TreeSet을 사용하는 것이 좋습니다.