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

149

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?

Obrabować
źródło
17
Czy próbowałeś zobaczyć kod źródłowy ArrayList?
AmitG
@Joachim Sauer: Czasami dowiadujemy się, kiedy uważnie czytamy źródło. Próbowałem, czy przeczytał źródło. Zrozumiałem twój aspekt. Dzięki.
AmitG
ArrayList to okres słabej wydajności, dlaczego miałbyś chcieć używać takiej struktury
PositiveGuy

Odpowiedzi:

196

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 .

NPE
źródło
5
Chociaż wstępne przydzielenie znanych rozmiarów jest dobrym pomysłem, zaniechanie tego zwykle nie jest straszne: będziesz potrzebować około log (n) ponownych alokacji dla listy o ostatecznym rozmiarze n , co nie jest dużo.
Joachim Sauer
2
@PeterOlson O(n log n)wykonywałby czas log npracy n. To rażące przeszacowanie (choć technicznie poprawne z dużym O, ponieważ jest to górna granica). W sumie kopiuje s + s * 1,5 + s * 1,5 ^ 2 + ... + s * 1,5 ^ m (tak, że s * 1,5 ^ m <n <s * 1,5 ^ (m + 1)) elementów. Nie jestem dobry w sumach, więc nie mogę podać dokładnej matematyki z mojej głowy (dla współczynnika zmiany rozmiaru 2 wynosi 2n, więc może to być 1,5 n, dawaj lub przyjmuj małą stałą), ale tak nie jest Nie trzeba zbyt często mrużyć oczu, aby zobaczyć, że ta suma jest co najwyżej stałym czynnikiem większym niż n. Potrzeba więc O (k * n) kopii, czyli oczywiście O (n).
1
@delnan: Nie można się z tym kłócić! ;) Swoją drogą, bardzo podobał mi się twój mrużący argument; dodam go do mojego repertuaru trików.
NPE
6
Łatwiej jest kłócić się z podwojeniem. Załóżmy, że podwoisz się, gdy pełny, zaczynając od jednego elementu. Załóżmy, że chcesz wstawić 8 elementów. Wstaw jeden (koszt: 1). Wstaw dwa - podwójne, skopiuj jeden element i wstaw dwa (koszt: 2). Wstaw trzy - podwójne, skopiuj dwa elementy, wstaw trzy (koszt: 3). Wstaw cztery (koszt: 1). Wstaw pięć - podwójnie, skopiuj cztery elementy, wstaw pięć (koszt: 5). Wstaw sześć, siedem i osiem (koszt: 3). Całkowity koszt: 1 + 2 + 3 + 1 + 5 + 3 = 16, czyli dwukrotność liczby wstawionych elementów. Na podstawie tego szkicu możesz udowodnić, że ogólnie rzecz biorąc średni koszt jednej wkładki wynosi dwa .
Eric Lippert
9
To koszt w czasie . Widać jednak, że ilość zmarnowanego miejsca zmieniała się w czasie, czasami wynosi 0%, a czasami prawie 100%. Zmiana współczynnika z 2 na 1,5 lub 4 lub 100 lub cokolwiek zmienia średnią ilość zmarnowanego miejsca i średnią ilość czasu spędzonego na kopiowaniu, ale złożoność czasowa pozostaje średnio liniowa, bez względu na to, jaki jest współczynnik.
Eric Lippert,
41

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)

Iulius Curt
źródło
9
to jest faktycznieint newCapacity = (oldCapacity * 3)/2 + 1;
AmitG
25

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.

xyz
źródło
Nie ma gwarancji, że domyślna pojemność zawsze będzie wynosić 10 dla wersji JDK w przyszłości -private static final int DEFAULT_CAPACITY = 10
vikingsteve
17

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

Daniel Imms
źródło
9

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 .

dsgriffin
źródło
3

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.

Sanober Malik
źródło
3

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;
AmitG
źródło
ArrayList nie wykona realokacji dla każdego pojedynczego add- już wewnętrznie używa jakiejś formuły wzrostu. Dlatego nie ma odpowiedzi na pytanie.
AH
@AH Moja odpowiedź brzmi: negatywny test . Uprzejmie czytaj między wierszami. Powiedziałem: „Jeśli nie masz powyższego kodu (żadnego algorytmu, który myślisz) do ponownego przydziału, to za każdym razem, gdy wywołujesz arraylist.add (), należy utworzyć nowy obiekt [], co jest bezcelowe i tracimy czas”. a kod jest int newCapacity = (oldCapacity * 3)/2 + 1;który jest obecny w klasie ArrayList. Czy nadal uważasz, że pozostaje bez odpowiedzi?
AmitG
1
Nadal myślę, że nie ma odpowiedzi: ArrayListw amortyzowanej realokacji odbywa się w każdym przypadku z dowolną wartością początkowej zdolności produkcyjnej. A pytanie brzmi: po co w ogóle używać niestandardowej wartości początkowej pojemności? Poza tym: „czytanie między wierszami” nie jest czymś pożądanym w odpowiedzi technicznej. ;-)
AH
@AH Odpowiadam, co by się stało, gdybyśmy nie mieli procesu realokacji w ArrayList. Taka jest odpowiedź. Spróbuj odczytać ducha odpowiedzi :-). Lepiej wiem, że w ArrayList amortyzowana realokacja ma miejsce w każdym przypadku z dowolną wartością początkowej pojemności.
AmitG
2

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ą.

sk2212
źródło
2

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 ()

Daniel Magnusson
źródło
0

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 ...

Tushar Patidar
źródło
0

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

Hamedz
źródło
1
Cześć, niestety tolerancja currentTimeMillis wynosi do stu milisekund (w zależności), co oznacza, że ​​wynik jest mało wiarygodny. Sugerowałbym użycie własnej biblioteki, aby zrobić to dobrze.
Bogdan