ArrayList 용량 추측과 사용되지 않은 값 사이의 상반 관계?

Question

1 개의 개체 (대다수) 또는 여러 개체 (일부 시간) 중 하나 일 수있는 데이터를 읽어야한다고합니다.

내가 할 경우 : 데이터베이스에서로드 만 한 물체가있을 때

List list = new ArrayList<Object>(1); 
... loop over the loaded object(s) and add it/them to the list... 

이 잘 시간의 대부분을 내게 될 것입니다. 그러나 초기 목록을 확장해야하는 덜 일반적인 시나리오로 가정하면 작업이 중단 될 수 있습니다.

나는이 정말 현실 세계에 영향을 많이하지 않습니다 가정,하지만 난 다음을 계산할 수있는 방법을 궁금해 :

는

내 데이터의 1 객체와 Y입니다 X %의 가정 %은 여러 개체의 목록입니다. 내 목록의 이상적인 초기 용량을 계산할 수있는 방법이 있습니까? 최소 연산 (목록 확장, 목록에 할당되었지만 사용되지 않은 필드 사용)은 어떻게됩니까?

Answer 1

데이터를 2 개의 그룹 X (1 개 요소)와 Y (2 개 이상)로 분리합니다. 가장 일반적인 경우이므로 X 그룹에 대한 코드를 최적화했습니다.

대부분의 경우 메모리를 낭비하지 않도록 ArrayList를 하나의 요소로 초기화하는 것이 좋습니다.

그러나 Y 그룹의 구성원의 평균 크기가 크고 표준 편차가 작은 경우 ensureCapacity (int cap)를 사용하여 최악의 상황을 최적화 할 수 있습니다. 두 번째 반복에서는 ArrayList 백업 배열의 평균 크기를 Y 그룹의 크기로 조정할 수 있습니다.

100 개 요소가있는 Y 그룹 구성원의 경우 배열을 12 번 작성/복사하고 1 개의 작은 배열 복사본에 대해 백업 배열 길이가 141이고 최적화를 구현하는 경우 낭비되는 메모리가 없습니다. 이 최적화의

예 :

Iterator<Obj> it = // Get your iterator from your resource 
ArrayList<Obj> result = new ArrayList<Obj>(1); 
if(it.hasNext()) { 
    result.add(it.next()); 
} 
if(it.hasNext()) { 
    result.ensureCapacity(100);// Avg size of the Y group 
    while(it.hasNext()) { 
     result.add(it.next()); 
    } 
} 

하지만 성능이 중요한 기능 않는 한 그것은 노력이 가치가 없어. 이 트릭이 속도와 메모리를 최적화 할 것이므로 Y 그룹의 크기 분포를 분석해야합니다.

그것은 drectly 문제와 관련된하지만 ArrayList에 유용한 의견이 많이 포함되어 아니에요 : When to use LinkedList over ArrayList?