Po co rozpoczynać ArrayList z początkową pojemnością?

Zwykły konstruktor ArrayListto:

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

Ale jest też przeciążony konstruktor z parametrem określającym jego pojemność początkową:

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

Dlaczego warto utworzyć plik ArrayListz początkową pojemnością, skoro możemy do niego dołączyć, jak nam się podoba?

Jeśli wiesz z wyprzedzeniem, jaki będzie rozmiar ArrayList, skuteczniej będzie określić początkową pojemność. Jeśli tego nie zrobisz, wewnętrzna tablica będzie musiała być wielokrotnie przenoszona w miarę powiększania się listy.

Im większa ostateczna lista, tym więcej czasu oszczędzasz, unikając ponownych przydziałów.

To powiedziawszy, nawet bez wstępnej alokacji, wstawianie nelementów z tyłu ArrayListgwarantuje całkowity O(n)czas. Innymi słowy, dołączanie elementu jest amortyzowaną operacją o stałym czasie trwania. Osiąga się to poprzez wykładnicze zwiększenie rozmiaru tablicy przy każdej ponownej alokacji, zazwyczaj o współczynnik 1.5. Przy takim podejściu można wykazaćO(n) , że całkowita liczba operacji wynosi .

Ponieważ ArrayListjest to struktura danych tablicy o dynamicznej zmianie rozmiaru , co oznacza, że ​​jest implementowana jako tablica o początkowym (domyślnym) stałym rozmiarze. Kiedy to się zapełni, tablica zostanie rozszerzona do podwójnej wielkości. Ta operacja jest kosztowna, więc chcesz jak najmniej.

Tak więc, jeśli wiesz, że twoja górna granica to 20 elementów, to utworzenie tablicy o początkowej długości 20 jest lepsze niż użycie domyślnej wartości, powiedzmy, 15, a następnie zmień jej rozmiar 15*2 = 30i użyj tylko 20, marnując cykle na rozszerzenie.

PS - Jak mówi AmitG, współczynnik ekspansji zależy od implementacji (w tym przypadku (oldCapacity * 3)/2 + 1)

Domyślny rozmiar Arraylist to 10 .

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

Więc jeśli zamierzasz dodać 100 lub więcej rekordów, możesz zobaczyć narzut związany z realokacją pamięci.

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

Więc jeśli masz jakieś pojęcie o liczbie elementów, które będą przechowywane w Arraylist, lepiej jest utworzyć Arraylist o tym rozmiarze, zamiast zaczynać od 10, a następnie zwiększać go.

Właściwie napisałem post na blogu na ten temat 2 miesiące temu. Artykuł jest przeznaczony dla C #, List<T>ale Java ArrayListma bardzo podobną implementację. Ponieważ ArrayListjest implementowany przy użyciu tablicy dynamicznej, zwiększa się na żądanie. Dlatego konstruktor pojemności ma na celu optymalizację.

Gdy wystąpi jedna z tych operacji zmiany rozmiaru, ArrayList kopiuje zawartość tablicy do nowej tablicy, która ma dwukrotnie większą pojemność niż stara. Ta operacja działa w czasie O (n) .

Przykład

Oto przykład, jak ArrayListzwiększyłby się rozmiar:

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

Tak więc lista zaczyna się od pojemności 10, po dodaniu 11. pozycji jest ona zwiększana o 50% + 1do 16. Na 17. pozycji wartość ArrayListjest ponownie zwiększana do 25i tak dalej. Rozważmy teraz przykład, w którym tworzymy listę, na której żądana pojemność jest już znana jako 1000000. Utworzenie konstruktora ArrayListbez rozmiaru wywołuje ArrayList.add 1000000czasy, które normalnie przyjmują O (1) lub O (n) przy zmianie rozmiaru.

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851 operacji

Porównaj to przy użyciu konstruktora, a następnie wywołanie, ArrayList.addktóre ma gwarantowane działanie w O (1) .

1000000 + 1000000 = 2000000 operacji

Java vs C #

Java działa jak powyżej, zaczynając od 10i zwiększając każdą zmianę rozmiaru o 50% + 1. C # zaczyna się od 4i rośnie znacznie agresywniej, podwajając się przy każdej zmianie rozmiaru. 1000000Dodaje przykład od góry do C # używa 3097084operacji.

Bibliografia

• Mój wpis na blogu w C #'s List <T>
• Kod źródłowy ArrayList w Javie

Ustawienie początkowego rozmiaru tablicy ArrayList, np. Na ArrayList<>(100), zmniejsza liczbę przypadków, w których musi nastąpić ponowna alokacja pamięci wewnętrznej.

Przykład:

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. 

Jak widać na powyższym przykładzie - w ArrayListrazie potrzeby można go rozszerzyć. To, czego nie widać, to fakt, że rozmiar tablicy Arraylist zwykle się podwaja (chociaż należy pamiętać, że nowy rozmiar zależy od implementacji). Oto cytat z Oracle :

„Każda instancja ArrayList ma pojemność. Pojemność to rozmiar tablicy używanej do przechowywania elementów na liście. Zawsze jest co najmniej równa rozmiarowi listy. W miarę dodawania elementów do tablicy ArrayList jej pojemność rośnie automatycznie. Szczegóły polityki rozwoju nie są sprecyzowane poza faktem, że dodanie elementu ma stały zamortyzowany koszt czasu. "

Oczywiście, jeśli nie masz pojęcia, jaki zakres będziesz trzymać, ustawienie rozmiaru prawdopodobnie nie będzie dobrym pomysłem - jednak jeśli masz na myśli określony zakres, ustawienie początkowej pojemności zwiększy wydajność pamięci .

ArrayList może zawierać wiele wartości, a podczas wykonywania dużych początkowych wstawień można powiedzieć ArrayList, aby na początek przydzielił większą pamięć, aby nie marnować cykli procesora, gdy próbuje przydzielić więcej miejsca na następny element. W związku z tym przydział miejsca na początku jest bardziej efektywny.

Ma to na celu uniknięcie ewentualnych prób ponownego przydziału dla każdego obiektu.

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

new Object[]powstaje wewnętrznie .
JVM wymaga wysiłku, aby utworzyć, new Object[]gdy dodajesz element do arraylisty. Jeśli nie masz powyżej kodu (każdy algo was myślę) dla realokacji wtedy za każdym razem, kiedy powoływać arraylist.add()następnie new Object[]musi zostać utworzony, które nie ma sensu i tracą czas na zwiększenie rozmiaru o 1 dla każdego obiekty do dodania. Dlatego lepiej jest zwiększyć rozmiar za Object[]pomocą następującego wzoru.
(JSL użył formuły forcastingu podanej poniżej dla dynamicznie rosnącej listy arraylistów, zamiast zwiększać ją za każdym razem o 1. Ponieważ JVM wymaga wysiłku, aby się rozwijać)

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

Myślę, że każda ArrayList jest tworzona z wartością pojemności początkowej „10”. Tak czy inaczej, jeśli utworzysz ArrayList bez ustawiania pojemności w konstruktorze, zostanie ona utworzona z wartością domyślną.

Powiedziałbym, że to optymalizacja. ArrayList bez początkowej pojemności będzie miał ~ 10 pustych wierszy i zostanie rozszerzony podczas dodawania.

Aby mieć listę z dokładnie taką liczbą elementów, którą musisz wywołać trimToSize ()

Zgodnie z moim doświadczeniem ArrayList, podanie początkowej pojemności to dobry sposób na uniknięcie kosztów ponownej alokacji. Ale zawiera zastrzeżenie. Wszystkie wspomniane powyżej sugestie mówią, że początkową pojemność należy podawać tylko wtedy, gdy znane jest zgrubne oszacowanie liczby elementów. Ale kiedy spróbujemy nadać początkową pojemność bez żadnego pomysłu, ilość zarezerwowanej i nieużywanej pamięci będzie stratą, ponieważ może nigdy nie być potrzebna po wypełnieniu listy do wymaganej liczby elementów. Chodzi mi o to, że na początku możemy być pragmatyczni podczas przydzielania pojemności, a następnie znaleźć inteligentny sposób na ustalenie wymaganej minimalnej pojemności w czasie wykonywania. ArrayList udostępnia metodę o nazwie ensureCapacity(int minCapacity). Ale potem trzeba znaleźć sprytny sposób ...

Przetestowałem ArrayList z i bez initialCapacity i otrzymałem zaskakujący wynik.
Kiedy ustawię LOOP_NUMBER na 100 000 lub mniej, wynik jest taki, że ustawienie initialCapacity jest wydajne.

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10

Ale kiedy ustawię LOOP_NUMBER na 1 000 000, wynik zmieni się na:

list1Stop-list1Start = 40
list2Stop-list2Start = 66

Wreszcie nie mogłem dowiedzieć się, jak to działa ?!
Przykładowy kod:

 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));
}

Testowałem na windows8.1 i jdk1.7.0_80