Zwykły konstruktor ArrayList
to:
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 ArrayList
z początkową pojemnością, skoro możemy do niego dołączyć, jak nam się podoba?
java
data-structures
arraylist
capacity
Obrabować
źródło
źródło
Odpowiedzi:
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
n
elementów z tyłuArrayList
gwarantuje całkowityO(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ółczynnik1.5
. Przy takim podejściu można wykazaćO(n)
, że całkowita liczba operacji wynosi .źródło
O(n log n)
wykonywałby czaslog n
pracyn
. 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).Ponieważ
ArrayList
jest 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 = 30
i 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
)źródło
int newCapacity = (oldCapacity * 3)/2 + 1;
Domyślny rozmiar Arraylist to 10 .
Więc jeśli zamierzasz dodać 100 lub więcej rekordów, możesz zobaczyć narzut związany z realokacją pamięci.
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.
źródło
private static final int DEFAULT_CAPACITY = 10
Właściwie napisałem post na blogu na ten temat 2 miesiące temu. Artykuł jest przeznaczony dla C #,
List<T>
ale JavaArrayList
ma bardzo podobną implementację. PonieważArrayList
jest 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
ArrayList
zwiększyłby się rozmiar:Tak więc lista zaczyna się od pojemności
10
, po dodaniu 11. pozycji jest ona zwiększana o50% + 1
do16
. Na 17. pozycji wartośćArrayList
jest ponownie zwiększana do25
i tak dalej. Rozważmy teraz przykład, w którym tworzymy listę, na której żądana pojemność jest już znana jako1000000
. Utworzenie konstruktoraArrayList
bez rozmiaru wywołujeArrayList.add
1000000
czasy, które normalnie przyjmują O (1) lub O (n) przy zmianie rozmiaru.Porównaj to przy użyciu konstruktora, a następnie wywołanie,
ArrayList.add
które ma gwarantowane działanie w O (1) .Java vs C #
Java działa jak powyżej, zaczynając od
10
i zwiększając każdą zmianę rozmiaru o50% + 1
. C # zaczyna się od4
i rośnie znacznie agresywniej, podwajając się przy każdej zmianie rozmiaru.1000000
Dodaje przykład od góry do C # używa3097084
operacji.Bibliografia
źródło
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:
Jak widać na powyższym przykładzie - w
ArrayList
razie 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 :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 .
źródło
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.
źródło
Ma to na celu uniknięcie ewentualnych prób ponownego przydziału dla każdego obiektu.
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ępnienew 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 zaObject[]
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ć)
źródło
add
- już wewnętrznie używa jakiejś formuły wzrostu. Dlatego nie ma odpowiedzi na pytanie.int newCapacity = (oldCapacity * 3)/2 + 1;
który jest obecny w klasie ArrayList. Czy nadal uważasz, że pozostaje bez odpowiedzi?ArrayList
w 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. ;-)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ą.
źródło
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 ()
źródło
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 nazwieensureCapacity(int minCapacity)
. Ale potem trzeba znaleźć sprytny sposób ...źródło
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.
Ale kiedy ustawię LOOP_NUMBER na 1 000 000, wynik zmieni się na:
Wreszcie nie mogłem dowiedzieć się, jak to działa ?!
Przykładowy kod:
Testowałem na windows8.1 i jdk1.7.0_80
źródło