집계 값의 일부를 추적하는 Java 알고리즘

Question

내 프로그램에서 수억 개의 레코드를 평가했습니다. 따라서 기억과 성능의 문제는 중요합니다. 각 레코드에 key - ticketID가 있습니다. 또한 레코드에는 필드 값과 필드 source_name이 있습니다. 소스 티켓 ID에는 1에서 많은 (근사치 100) source_name까지 있습니다. ticketID에 의해서만 집계가 필요합니다. 거의 백만 건의 레코드를받을 수 있지만 지정된 source_name에 대한 가능성 값을 뺄 수 있어야합니다. 그래서 트랙 기여가 있습니다.

이 문제를 해결할 수있는 알고리즘이나 데이터 구조가 있습니까?

Answer 1

내가 꽤 나는 가정합니다 완전히 질문을 구문 분석 할 수 없습니다 :

• "거의 1 백만 기록"거의 1 백만 독특한 ticketID 필드가 있음을 의미합니다.
• 시스템에서 "거의 100"이 다릅니다. source_name
• 모두 ticketId은 source_names이다. 우리는 1 억 1 천 2 백x source_name 조합을 가지고 있지 않습니다.
• ticketId을 모두 합계 할 수 있고 합계는 source_name입니다.

이러한 가정에서는 Map 개의지도를 사용합니다. 바깥 쪽 Map에는 source_name의 키와 Map의 값이 있습니다. 내부 Map에는 ticketId 키와 누적 value 키가 있습니다. 당신은 쉽게 source_name지도의 각을 추가하여 총을 얻을 수

Map<String, Map<Integer,Double>> valueMap = 
    new HashMap<String, Map<Integer,Double>>(); 

while (...reading in and processing data...) { 
    int ticketId = ...; 
    String sourceName = ...; 
    double entryValue = ...; 

    Map<Integer,Double> sourceNameMap = valueMap.get(sourceName); 
    Double value = sourceNameMap.get(ticketId); 
    if (oldValue == null) { 
     value = entryValue; 
    } else { 
     value += entryValue; 
    } 
    sourceNameMap.put(ticketId, value); 
} 

:

그래서 의사 코드는 같을 것이다. 물론 각 source_name의 누적 합계를 유지할 수도 있습니다. 시스템이 JVM에 기가 바이트를 할당 할 수 있다면 좋은 숫자 인 ticketID x source_name 쌍을 처리 할 수 ​​있어야합니다.

당신은 GC 사이클을 절약하기 위해 변경 가능한 내부 값 클래스를 생성하는 것이 좋습니다 : 그럼 당신이 말할 수

private static class MutableValue { 
    double value; 
    public MutableValue(double value) { 
     this.value = value; 
    } 
    public void add(double value) { 
     this.value += value; 
    } 
} 

을 : 당신이 당신의 질문을 편집하면 내가 편집거야,

MutableValue value = sourceNameMap.get(ticketId); 
if (oldValue == null) { 
    sourceNameMap.put(new MutableValue(entryValue)); 
} else { 
    value.add(entryValue); 
} 

내 부적절한 가정을 한 경우를 대비하여 대답합니다.