초기 용량으로 ArrayList를 시작하는 이유는 무엇입니까?

초기 용량으로 ArrayList를 시작하는 이유는 무엇입니까?

---

일반적인 생성자 ArrayList는 다음과 같습니다.

ArrayList<?> list = new ArrayList<>();

그러나 초기 용량에 대한 매개 변수가있는 오버로드 된 생성자가 있습니다.

ArrayList<?> list = new ArrayList<>(20);

원하는 ArrayList대로 추가 할 수있을 때 초기 용량 으로 생성하는 것이 유용한 이유는 무엇 입니까?

---

크기를 미리 알고 있다면 ArrayList초기 용량을 지정하는 것이 더 효율적입니다. 이 작업을 수행하지 않으면 목록이 커짐에 따라 내부 배열을 반복적으로 재 할당해야합니다.

최종 목록이 클수록 재 할당을 피함으로써 더 많은 시간을 절약 할 수 있습니다.

즉, 사전 할당이 없어도 n뒷면에 요소를 삽입 ArrayList하는 데 총 O(n)시간이 걸립니다. 다시 말해, 요소를 추가하는 것은 상각 된 상수 시간 연산입니다. 이것은 각각의 재 할당이 어레이의 크기를 지수 적으로, 전형적으로 씩 증가시킴으로써 달성된다 1.5. 이 방법을 사용하면 총 작업 수를로 표시 할 수 있습니다O(n) .

---

왜냐하면 ArrayListA는 동적 리사이징 어레이 는 초기 (기본) 고정 크기 어레이로서 구현되는 수단, 데이터 구조. 이것이 채워지면 배열은 두 배 크기로 확장됩니다. 이 작업은 비용이 많이 들기 때문에 최대한 적게 원합니다.

따라서 상한이 20 개의 항목 인 경우 초기 길이가 20 인 배열을 만드는 것이 기본값 인 15를 사용하는 것보다 낫습니다. 그런 다음 15*2 = 30확장주기를 낭비하면서 크기를 조정하고 20 만 사용하십시오.

PS-AmitG가 말했듯이 확장 요소는 구현에 따라 다릅니다 (이 경우 (oldCapacity * 3)/2 + 1)

---

Arraylist의 기본 크기는 10 입니다.

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
    this(10);
    } 

따라서 100 개 이상의 레코드를 추가하려는 경우 메모리 재 할당 오버 헤드를 볼 수 있습니다.

ArrayList<?> list = new ArrayList<>();    
// same as  new ArrayList<>(10);      

따라서 Arraylist에 저장 될 요소 수에 대한 아이디어가 있다면 10으로 시작한 다음 증가시키는 대신 해당 크기의 Arraylist를 만드는 것이 좋습니다.

---

나는 실제로 2 개월 전에 주제에 대한 블로그 게시물 을 썼습니다 . 이 기사는 C #에 대한 List<T>것이지만 Java의 ArrayList구현은 매우 유사합니다. ArrayList동적 배열을 사용하여 구현 되므로 필요에 따라 크기가 커집니다. 용량 생성자의 이유는 최적화를위한 것입니다.

이러한 크기 조정 작업 중 하나가 발생하면 ArrayList는 배열의 내용을 이전 것보다 두 배 큰 새 배열로 복사합니다. 이 작업은 O (n) 시간에 실행됩니다 .

예

다음은 ArrayList크기가 어떻게 증가 하는지에 대한 예입니다 .

10
16
25
38
58
... 17 resizes ...
198578
297868
446803
670205
1005308

따라서 목록의 용량은 1011 번째 항목이 추가 될 때로 증가 50% + 1합니다 16. 17 번째 항목에서 ArrayList가 다시 증가합니다 25. 이제 원하는 용량이 이미 알려진 목록을 작성하는 예를 고려하십시오 1000000. ArrayList크기 생성자를 사용하지 않고 생성하면 크기 조정시 O (1) 또는 O (n)ArrayList.add 1000000 이 걸리는 시간 이 호출됩니다 .

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851 연산

생성자를 사용하여 이것을 비교 한 다음 O (1)ArrayList.add 에서 실행되도록 보장하는 호출하십시오 .

1000000 + 1000000 = 2000000 연산

자바 대 C #

Java는 위와 같으며에서 시작하여 10각 크기를 조정 50% + 1합니다. C #은 시작될 4때마다 훨씬 더 적극적으로 증가하여 크기를 조정할 때마다 두 배가됩니다. 1000000C # 사용 3097084작업에 대한 위 의 추가 예제 .

참고 문헌

• C #의 List <T>에 대한 내 블로그 게시물
• 자바의 ArrayList 소스 코드

---

예를 들어 ArrayList의 초기 크기를 설정하면 ArrayList<>(100)내부 메모리의 재 할당 횟수가 줄어 듭니다.

예:

ArrayList example = new ArrayList<Integer>(3);
example.add(1); // size() == 1
example.add(2); // size() == 2, 
example.add(2); // size() == 3, example has been 'filled'
example.add(3); // size() == 4, example has been 'expanded' so that the fourth element can be added. 

위의 예에서 볼 수 있듯이 ArrayList필요한 경우 확장 할 수 있습니다. 이것이 표시하지 않는 것은 Arraylist의 크기가 일반적으로 두 배라는 것입니다 (새 크기는 구현에 따라 다릅니다). 다음은 Oracle 에서 인용 한 것입니다 .

"Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost."

Obviously, if you have no idea as to what kind of range you will be holding, setting the size probably won't be a good idea - however, if you do have a specific range in mind, setting an initial capacity will increase memory efficiency.

---

ArrayList can contain many values and when doing large initial insertions you can tell ArrayList to allocate a larger storage to begin with as to not waste CPU cycles when it tries to allocate more space for the next item. Thus to allocate some space at the beginning is more effiecient.

---

This is to avoid possible efforts for reallocation for every single object.

int newCapacity = (oldCapacity * 3)/2 + 1;

internally new Object[] is created.
JVM needs effort to create new Object[] when you add element in the arraylist. If you don't have above code(any algo you think) for reallocation then every time when you invoke arraylist.add() then new Object[] has to be created which is pointless and we are loosing time for increasing size by 1 for each and every objects to be added. So it is better to increase size of Object[] with following formula.
(JSL has used forcasting formula given below for dynamically growing arraylist instead of growing by 1 every time. Because to grow it takes effort by JVM)

int newCapacity = (oldCapacity * 3)/2 + 1;

---

I think each ArrayList is created with an init capacity value of "10". So anyway, if you create an ArrayList without setting capacity within constructor it will be created with a default value.

---

I'd say its an optimization. ArrayList without initial capacity will have ~10 empty rows and will expand when you are doing an add.

To have a list with exactly the number of items you need to call trimToSize()

---

As per my experience with ArrayList, giving an initial capacity is a nice way to avoid reallocation costs. But it bears a caveat. All suggestions mentioned above say that one should provide initial capacity only when a rough estimate of the number of elements is known. But when we try to give an initial capacity without any idea, the amount of memory reserved and unused will be a waste as it may never be required once the list is filled to required number of elements. What i am saying is, we can be pragmatic at the beginning while allocating capacity, and then find a smart way of knowing required minimal capacity at runtime. ArrayList provides a method called ensureCapacity(int minCapacity). But then, one has find a smart way...

---

I have tested ArrayList with and without initialCapacity and I got suprising result
When I set LOOP_NUMBER to 100,000 or less the result is that setting initialCapacity is efficient.

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10

But when I set LOOP_NUMBER to 1,000,000 the result changes to:

list1Stop-list1Start = 40
list2Stop-list2Start = 66

Finally, I couldn't figure out how does it works?!
Sample code:

 public static final int LOOP_NUMBER = 100000;

public static void main(String[] args) {

    long list1Start = System.currentTimeMillis();
    List<Integer> list1 = new ArrayList();
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list1.add(i);
    }
    long list1Stop = System.currentTimeMillis();
    System.out.println("list1Stop-list1Start = " + String.valueOf(list1Stop - list1Start));

    long list2Start = System.currentTimeMillis();
    List<Integer> list2 = new ArrayList(LOOP_NUMBER);
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list2.add(i);
    }
    long list2Stop = System.currentTimeMillis();
    System.out.println("list2Stop-list2Start = " + String.valueOf(list2Stop - list2Start));
}

I have tested on windows8.1 and jdk1.7.0_80

참고URL : https://stackoverflow.com/questions/15430247/why-start-an-arraylist-with-an-initial-capacity