Muszę zachować tysiące ciągów w pamięci, aby można było uzyskać do nich dostęp szeregowo w Javie. Czy powinienem przechowywać je w tablicy, czy powinienem użyć listy?

Skoro tablice przechowują wszystkie dane w ciągłym kawałku pamięci (w przeciwieństwie do list), czy użycie tablicy do przechowywania tysięcy łańcuchów spowoduje problemy?

Sugeruję użycie profilera do przetestowania, który jest szybszy.

Moja osobista opinia jest taka, że ​​powinieneś używać list.

Pracuję na dużej bazie kodu, a poprzednia grupa programistów wszędzie używała tablic . Dzięki temu kod był bardzo nieelastyczny. Po zmianie dużych fragmentów na Listy nie zauważyliśmy żadnej różnicy prędkości.

Sposób Java polega na tym, że powinieneś rozważyć, która abstrakcja danych najbardziej odpowiada Twoim potrzebom. Pamiętaj, że w Javie lista jest abstrakcyjnym, a nie konkretnym typem danych. Powinieneś zadeklarować ciągi jako Listę, a następnie zainicjować go za pomocą implementacji ArrayList.

List<String> strings = new ArrayList<String>();

Oddzielenie typu danych abstrakcyjnych od konkretnej implementacji jest jednym z kluczowych aspektów programowania obiektowego.

ArrayList implementuje List Abstract Data Type przy użyciu tablicy jako podstawowej implementacji. Szybkość dostępu jest praktycznie identyczna z tablicą, z dodatkowymi zaletami dodawania i odejmowania elementów do listy (chociaż jest to operacja O (n) z ArrayList) i że jeśli zdecydujesz się później zmienić podstawową implementację możesz. Na przykład, jeśli uznasz, że potrzebujesz zsynchronizowanego dostępu, możesz zmienić implementację na Vector bez przepisywania całego kodu.

W rzeczywistości ArrayList został specjalnie zaprojektowany w celu zastąpienia konstrukcji tablicy niskiego poziomu w większości kontekstów. Gdyby dziś projektowano Javę, jest całkiem możliwe, że tablice zostałyby całkowicie pominięte na rzecz konstrukcji ArrayList.

Skoro tablice przechowują wszystkie dane w ciągłym kawałku pamięci (w przeciwieństwie do list), czy użycie tablicy do przechowywania tysięcy łańcuchów spowoduje problemy?

W Javie wszystkie kolekcje przechowują tylko odwołania do obiektów, a nie same obiekty. Zarówno tablice, jak i ArrayList będą przechowywać kilka tysięcy referencji w ciągłej tablicy, więc są one zasadniczo identyczne. Możesz wziąć pod uwagę, że ciągły blok kilku tysięcy 32-bitowych odniesień będzie zawsze łatwo dostępny na nowoczesnym sprzęcie. Nie gwarantuje to, że nie zabraknie ci pamięci, oczywiście, tylko że ciągły blok zapotrzebowania na pamięć nie jest trudny do uzyskania.

Chociaż w większości scenariuszy odpowiedzi proponujące użycie ArrayList są sensowne, tak naprawdę nie znaleziono odpowiedzi na pytanie dotyczące względnej wydajności.

Jest kilka rzeczy, które możesz zrobić z tablicą:

• Stwórz To
• ustaw przedmiot
• dostać przedmiot
• sklonuj / skopiuj to

Ogólny wniosek

Chociaż operacje pobierania i ustawiania są nieco wolniejsze na ArrayList (odpowiednio 1 i 3 nanosekundy na każde wywołanie na mojej maszynie), jest bardzo mały narzut związany z używaniem ArrayList w porównaniu z tablicą do jakiegokolwiek nie intensywnego użycia.Należy jednak pamiętać o kilku kwestiach:

• zmiana rozmiaru operacji na liście (podczas połączenia list.add(...) ) są kosztowne i należy spróbować ustawić początkową pojemność na odpowiednim poziomie, jeśli to możliwe (zauważ, że ten sam problem pojawia się podczas korzystania z tablicy)
• w przypadku prymitywów tablice mogą być znacznie szybsze, ponieważ pozwolą uniknąć wielu konwersji boksu / rozpakowania
• aplikacja, która pobiera / ustawia wartości tylko w ArrayList (niezbyt często!), może uzyskać wzrost wydajności o ponad 25% po przełączeniu na tablicę

Szczegółowe wyniki

Oto wyniki, które zmierzyłem dla tych trzech operacji przy użyciu biblioteki testów porównawczych jmh (czasy w nanosekundach) z JDK 7 na standardowej maszynie stacjonarnej x86. Należy pamiętać, że ArrayList nigdy nie jest zmieniany w testach, aby upewnić się, że wyniki są porównywalne. Kod testu dostępny tutaj .

Array / ArrayList Creation

Przeprowadziłem 4 testy, wykonując następujące instrukcje:

• createArray1: Integer[] array = new Integer[1];
• createList1: List<Integer> list = new ArrayList<> (1);
• createArray10000: Integer[] array = new Integer[10000];
• createList10000: List<Integer> list = new ArrayList<> (10000);

Wyniki (w nanosekundach na połączenie, 95% ufności):

a.p.g.a.ArrayVsList.CreateArray1         [10.933, 11.097]
a.p.g.a.ArrayVsList.CreateList1          [10.799, 11.046]
a.p.g.a.ArrayVsList.CreateArray10000    [394.899, 404.034]
a.p.g.a.ArrayVsList.CreateList10000     [396.706, 401.266]

Wniosek: brak zauważalnej różnicy .

uzyskać operacje

Przeprowadziłem 2 testy, wykonując następujące instrukcje:

• getList: return list.get(0);
• getArray: return array[0];

Wyniki (w nanosekundach na połączenie, 95% ufności):

a.p.g.a.ArrayVsList.getArray   [2.958, 2.984]
a.p.g.a.ArrayVsList.getList    [3.841, 3.874]

Wniosek: uzyskanie z tablicy jest około 25% szybsze niż pobieranie z ArrayList, chociaż różnica jest rzędu jednego nanosekundy.

ustawić operacje

Przeprowadziłem 2 testy, wykonując następujące instrukcje:

• Setlista: list.set(0, value);
• setArray: array[0] = value;

Wyniki (w nanosekundach na połączenie):

a.p.g.a.ArrayVsList.setArray   [4.201, 4.236]
a.p.g.a.ArrayVsList.setList    [6.783, 6.877]

Wniosek: ustawione operacje na tablicach są o około 40% szybsze niż na listach, ale jeśli chodzi o get, każda operacja zestawu zajmuje kilka nanosekund - więc aby różnica osiągnęła 1 sekundę, trzeba ustawić pozycje na setkach listy / tablicy milionów razy!

klon / kopia

ArrayList jest konstruktor kopiujący delegatów Arrays.copyOfwięc wydajność jest identyczna kopia tablicy (kopiowanie tablicę via clone, Arrays.copyOflub System.arrayCopy nie ma istotnego znaczenia z punktu widzenia wydajności ).

Powinieneś preferować typy ogólne niż tablice. Jak wspomnieli inni, tablice są nieelastyczne i nie mają ekspresyjnej mocy typów ogólnych. (Obsługują one jednak sprawdzanie typów środowiska wykonawczego, ale źle się to miesza z typami ogólnymi).

Ale, jak zawsze, podczas optymalizacji należy zawsze wykonać następujące kroki:

• Nie optymalizuj, dopóki nie będziesz mieć ładnego, czystego i działającego wersji kodu. Już teraz na tym etapie można bardzo dobrze zmotywować się do typów ogólnych.
• Gdy masz wersję ładną i czystą, zdecyduj, czy jest wystarczająco szybka.
• Jeśli nie jest wystarczająco szybki, zmierz jego wydajność . Ten krok jest ważny z dwóch powodów. Jeśli nie wykonasz pomiaru, (1) nie będziesz wiedział wpływu dokonanych optymalizacji i (2) będziesz wiedział, gdzie je zoptymalizować.
• Zoptymalizuj najgorętszą część kodu.
• Zmierz ponownie. Jest to tak samo ważne jak pomiar wcześniej. Jeśli optymalizacja niczego nie poprawiła, cofnij ją . Pamiętaj, że kod bez optymalizacji był czysty, ładny i działał.

Domyślam się, że oryginalny plakat pochodzi z tła C ++ / STL, co powoduje pewne zamieszanie. W C ++std::list jest podwójnie połączona lista.

W Javie [java.util.]Listjest interfejsem bez implementacji (czysta klasa abstrakcyjna w kategoriach C ++). Listmoże być podwójnie połączoną listą - java.util.LinkedListjest podana. Jednak 99 razy na 100, jeśli chcesz zrobić nowy List, chcesz użyć java.util.ArrayListzamiast niego, co stanowi przybliżony odpowiednik C ++ std::vector. Istnieją inne standardowe implementacje, takie jak te zwrócone przez java.util.Collections.emptyList()i java.util.Arrays.asList().

Z punktu widzenia wydajności, przejście przez interfejs i dodatkowy obiekt jest bardzo niewielkim hitem, jednak wstawianie w czasie wykonywania oznacza, że ​​rzadko ma to jakiekolwiek znaczenie. Pamiętaj też, że Stringzazwyczaj są to obiekt plus tablica. Tak więc dla każdego wpisu prawdopodobnie masz dwa inne obiekty. W C ++ std::vector<std::string>, chociaż kopiowanie według wartości bez wskaźnika jako takiego, tablice znaków utworzą obiekt dla ciągu (i zwykle nie będą one udostępniane).

Jeśli ten konkretny kod jest naprawdę wrażliwy na wydajność, możesz utworzyć pojedynczą char[]tablicę (lub nawet byte[]) dla wszystkich znaków wszystkich ciągów, a następnie tablicę przesunięć. IIRC, tak implementuje się javac.

Zgadzam się, że w większości przypadków powinieneś wybierać elastyczność i elegancję ArrayLists zamiast tablic - w większości przypadków wpływ na wydajność programu będzie znikomy.

Jeśli jednak wykonujesz ciągłą, intensywną iterację z niewielkimi zmianami strukturalnymi (bez dodawania i usuwania) dla, powiedzmy, renderowania grafiki programowej lub niestandardowej maszyny wirtualnej, moje testy porównawcze sekwencyjnego dostępu pokazują, że ArrayLists są 1,5x wolniejsze niż tablice na moim system (Java 1.6 na moim rocznym komputerze iMac).

Jakiś kod:

import java.util.*;

public class ArrayVsArrayList {
    static public void main( String[] args ) {

        String[] array = new String[300];
        ArrayList<String> list = new ArrayList<String>(300);

        for (int i=0; i<300; ++i) {
            if (Math.random() > 0.5) {
                array[i] = "abc";
            } else {
                array[i] = "xyz";
            }

            list.add( array[i] );
        }

        int iterations = 100000000;
        long start_ms;
        int sum;

        start_ms = System.currentTimeMillis();
        sum = 0;

        for (int i=0; i<iterations; ++i) {
          for (int j=0; j<300; ++j) sum += array[j].length();
        }

        System.out.println( (System.currentTimeMillis() - start_ms) + " ms (array)" );
        // Prints ~13,500 ms on my system

        start_ms = System.currentTimeMillis();
        sum = 0;

        for (int i=0; i<iterations; ++i) {
          for (int j=0; j<300; ++j) sum += list.get(j).length();
        }

        System.out.println( (System.currentTimeMillis() - start_ms) + " ms (ArrayList)" );
        // Prints ~20,800 ms on my system - about 1.5x slower than direct array access
    }
}

Po pierwsze, warto wyjaśnić, czy masz na myśli „listę” w klasycznym znaczeniu struktur danych strukturalnych (tj. Listę połączoną) czy masz na myśli java.util.List? Jeśli masz na myśli java.util.List, jest to interfejs. Jeśli chcesz użyć tablicy, po prostu skorzystaj z implementacji ArrayList, a uzyskasz podobne do tablicy zachowanie i semantykę. Problem rozwiązany.

Jeśli masz na myśli tablicę vs połączoną listę, jest to nieco inny argument, dla którego wrócimy do Big O (tutaj jest proste angielskie wyjaśnienie, jeśli jest to nieznany termin).

Szyk;

• Dostęp losowy: O (1);
• Wstaw: O (n);
• Usuń: O (n).

Połączona lista:

• Dostęp losowy: O (n);
• Wstaw: O (1);
• Usuń: O (1).

Więc wybierasz ten, który najlepiej odpowiada zmianie rozmiaru tablicy. Jeśli często zmieniasz rozmiar, wstawiasz i usuwasz, być może lepsza jest lista z linkami. To samo dotyczy losowego dostępu rzadko. Wspominasz o dostępie szeregowym. Jeśli korzystasz głównie z dostępu szeregowego z niewielkimi modyfikacjami, prawdopodobnie nie ma znaczenia, który wybierzesz.

Listy połączone mają nieco większy narzut, ponieważ, jak mówisz, masz do czynienia z potencjalnie nieciągłymi blokami pamięci i (skutecznie) wskaźnikami do następnego elementu. Prawdopodobnie nie jest to ważny czynnik, chyba że masz do czynienia z milionami wpisów.

Napisałem mały test porównawczy, aby porównać ArrayLists z tablicami. Na moim starym laptopie czas przejścia przez 5000-elementową tablicę aranżacji, 1000 razy, był o około 10 milisekund wolniejszy niż równoważny kod tablicy.

Więc jeśli robisz tylko iterację listy i robisz to dużo, to może warto ją zoptymalizować. W przeciwnym razie skorzystałbym z Listy, ponieważ ułatwi to optymalizację kodu.

NB I zrobił uwagę, że przy użyciu for String s: stringsListbyło około 50% wolniej niż przy użyciu starego stylu dla pętli, aby otworzyć listę. Idź rysunek ... Oto dwie funkcje, które sprawdziłem; tablica i lista zostały wypełnione 5000 losowymi (różnymi) ciągami.

private static void readArray(String[] strings) {
    long totalchars = 0;
    for (int j = 0; j < ITERATIONS; j++) {
        totalchars = 0;
        for (int i = 0; i < strings.length; i++) {
            totalchars += strings[i].length();

        }
    }
}

private static void readArrayList(List<String> stringsList) {
    long totalchars = 0;
    for (int j = 0; j < ITERATIONS; j++) {
        totalchars = 0;
        for (int i = 0; i < stringsList.size(); i++) {
            totalchars += stringsList.get(i).length();
        }
    }
}

Nie, ponieważ technicznie tablica przechowuje tylko odwołanie do ciągów. Same łańcuchy są przydzielane w innym miejscu. Powiedziałbym, że dla tysiąca przedmiotów lista byłaby lepsza, jest wolniejsza, ale oferuje większą elastyczność i jest łatwiejsza w użyciu, zwłaszcza jeśli zamierzasz zmienić ich rozmiar.

Jeśli masz tysiące, rozważ użycie trie. Trie to struktura przypominająca drzewo, która łączy typowe prefiksy przechowywanego ciągu.

Na przykład, jeśli ciągi były

intern
international
internationalize
internet
internets

Trie będzie przechowywać:

intern
 -> \0
 international
 -> \0
 -> ize\0
 net
 ->\0
 ->s\0

Ciągi wymagają do przechowywania 57 znaków (w tym terminatora zerowego, „\ 0”) oraz dowolnej wielkości obiektu String, który je przechowuje. (Prawdę mówiąc, powinniśmy prawdopodobnie zaokrąglić wszystkie rozmiary do wielokrotności 16, ale ...) Z grubsza nazywamy to 57 + 5 = 62 bajtów.

Trie wymaga 29 (w tym terminatora zerowego, \ \ 0) do przechowywania, plus rozmiar węzłów trie, które są odniesieniem do tablicy i listy potomnych trie węzłów.

W tym przykładzie prawdopodobnie wygląda to tak samo; dla tysięcy prawdopodobnie wydaje się mniej, o ile masz wspólne prefiksy.

Teraz, gdy używasz trie w innym kodzie, będziesz musiał przekonwertować na String, prawdopodobnie używając StringBuffer jako pośrednika. Jeśli wiele ciągów jest używanych jednocześnie jako Ciągi, poza trie, jest to strata.

Ale jeśli używasz tylko kilku na raz - powiedzmy, do wyszukiwania rzeczy w słowniku - trie może zaoszczędzić dużo miejsca. Zdecydowanie mniej miejsca niż przechowywanie ich w zestawie Hash.

Mówisz, że uzyskujesz do nich dostęp „szeregowo” - jeśli to oznacza sekwencyjnie alfabetycznie, trie oczywiście daje ci również porządek alfabetyczny za darmo, jeśli powtórzysz go najpierw na głębokości.

AKTUALIZACJA:

Jak zauważył Mark, po rozgrzaniu JVM nie ma znaczącej różnicy (kilka testów). Sprawdzane przy użyciu ponownie utworzonej tablicy lub nawet nowego przejścia, zaczynając od nowego rzędu macierzy. Z dużym prawdopodobieństwem znak ten nie używa prostej tablicy z dostępem do indeksu na rzecz kolekcji.

Jeszcze pierwsze 1-2 przejścia prostej tablicy są 2-3 razy szybsze.

ORYGINALNY POCZTA:

Zbyt wiele słów na temat, zbyt łatwy do sprawdzenia. Bez tablicy pytań jest kilka razy szybszy niż jakikolwiek kontener klasy . W odpowiedzi na to pytanie szukam alternatyw dla mojej sekcji krytycznej dla wydajności. Oto prototypowy kod, który zbudowałem, aby sprawdzić prawdziwą sytuację:

import java.util.List;
import java.util.Arrays;

public class IterationTest {

    private static final long MAX_ITERATIONS = 1000000000;

    public static void main(String [] args) {

        Integer [] array = {1, 5, 3, 5};
        List<Integer> list = Arrays.asList(array);

        long start = System.currentTimeMillis();
        int test_sum = 0;
        for (int i = 0; i < MAX_ITERATIONS; ++i) {
//            for (int e : array) {
            for (int e : list) {
                test_sum += e;
            }
        }
        long stop = System.currentTimeMillis();

        long ms = (stop - start);
        System.out.println("Time: " + ms);
    }
}

A oto odpowiedź:

W oparciu o tablicę (linia 16 jest aktywna):

Time: 7064

Na podstawie listy (linia 17 jest aktywna):

Time: 20950

Jeszcze jakiś komentarz na temat „szybszego”? To jest całkiem zrozumiałe. Pytanie brzmi, kiedy około 3 razy szybciej jest dla Ciebie lepsze niż elastyczność List. Ale to kolejne pytanie. Przy okazji sprawdziłem to też na podstawie ręcznie zbudowanej ArrayList. Prawie taki sam wynik.

Ponieważ jest tu już wiele dobrych odpowiedzi, chciałbym podać kilka innych praktycznych informacji, takich jak porównanie wydajności wstawiania i iteracji: prymitywna tablica vs lista połączona w Javie.

To jest rzeczywiście prosta kontrola wydajności.
Wynik będzie zależał od wydajności maszyny.

Kod źródłowy użyty do tego jest poniżej:

import java.util.Iterator;
import java.util.LinkedList;

public class Array_vs_LinkedList {

    private final static int MAX_SIZE = 40000000;

    public static void main(String[] args) {

        LinkedList lList = new LinkedList(); 

        /* insertion performance check */

        long startTime = System.currentTimeMillis();

        for (int i=0; i<MAX_SIZE; i++) {
            lList.add(i);
        }

        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");

        int[] arr = new int[MAX_SIZE];

        startTime = System.currentTimeMillis();
        for(int i=0; i<MAX_SIZE; i++){
            arr[i] = i; 
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");


        /* iteration performance check */

        startTime = System.currentTimeMillis();

        Iterator itr = lList.iterator();

        while(itr.hasNext()) {
            itr.next();
            // System.out.println("Linked list running : " + itr.next());
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");


        startTime = System.currentTimeMillis();

        int t = 0;
        for (int i=0; i < MAX_SIZE; i++) {
            t = arr[i];
            // System.out.println("array running : " + i);
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
    }
}

Wynik działania jest poniżej:

lista jest wolniejsza niż tablice.Jeśli potrzebujesz wydajności, użyj tablic.Jeśli potrzebujesz elastyczności, użyj listy.

Pamiętaj, że ArrayList hermetyzuje tablicę, więc jest niewielka różnica w porównaniu do korzystania z prymitywnej tablicy (z wyjątkiem faktu, że Listę można znacznie łatwiej obsługiwać w Javie).

Praktycznie jedynym sensownym rozwiązaniem, dla którego warto wybrać tablicę niż ArrayList, jest przechowywanie operacji prymitywnych, tj. Bajtów, liczb całkowitych itp., I potrzebna jest szczególna wydajność przestrzeni uzyskana dzięki zastosowaniu prymitywnych tablic.

Wybór tablicy vs. listy nie jest tak ważny (biorąc pod uwagę wydajność) w przypadku przechowywania obiektów łańcuchowych. Ponieważ zarówno tablica, jak i lista będą przechowywać odniesienia do obiektów łańcuchowych, a nie rzeczywiste obiekty.

1. Jeśli liczba ciągów jest prawie stała, użyj tablicy (lub ArrayList). Ale jeśli liczba zmienia się zbyt mocno, lepiej użyj LinkedList.
2. Jeśli istnieje (lub będzie) potrzeba dodawania lub usuwania elementów w środku, z pewnością musisz użyć LinkedList.

Przybyłem tutaj, aby lepiej poczuć wpływ używania list na tablice. Musiałem tu dostosować kod dla mojego scenariusza: tablica / lista ~ 1000 int przy użyciu głównie modułów pobierających, co oznacza tablicę [j] vs. list.get (j)

Biorąc to, co najlepsze z 7, nie jestem naukowy (kilka pierwszych z listą, gdzie 2,5x wolniej), otrzymuję to:

array Integer[] best 643ms iterator
ArrayList<Integer> best 1014ms iterator

array Integer[] best 635ms getter
ArrayList<Integer> best 891ms getter (strange though)

- więc bardzo z grubsza o 30% dzięki macierzy

Drugim powodem publikowania jest to, że nikt nie wspomina o wpływie, jeśli wykonujesz kod matematyczny / matrycowy / symulacyjny / optymalizacyjny za pomocą zagnieżdżonych pętli.

Załóżmy, że masz trzy zagnieżdżone poziomy, a wewnętrzna pętla jest dwa razy wolniejsza niż 8-krotny wzrost wydajności. Coś, co działałoby w ciągu dnia, zajmuje teraz tydzień.

* EDIT Całkiem zszokowany tutaj, dla kopnięć próbowałem zadeklarować int [1000] zamiast Integer [1000]

array int[] best 299ms iterator
array int[] best 296ms getter

Użycie Integer [] vs. int [] oznacza podwójne działanie, ListArray z iteratorem jest 3 razy wolniejszy niż int []. Naprawdę myślałem, że implementacje list Java były podobne do macierzy natywnych ...

Kod referencyjny (zadzwoń wiele razy):

    public static void testArray()
    {
        final long MAX_ITERATIONS = 1000000;
        final int MAX_LENGTH = 1000;

        Random r = new Random();

        //Integer[] array = new Integer[MAX_LENGTH];
        int[] array = new int[MAX_LENGTH];

        List<Integer> list = new ArrayList<Integer>()
        {{
            for (int i = 0; i < MAX_LENGTH; ++i)
            {
                int val = r.nextInt();
                add(val);
                array[i] = val;
            }
        }};

        long start = System.currentTimeMillis();
        int test_sum = 0;
        for (int i = 0; i < MAX_ITERATIONS; ++i)
        {
//          for (int e : array)
//          for (int e : list)          
            for (int j = 0; j < MAX_LENGTH; ++j)
            {
                int e = array[j];
//              int e = list.get(j);
                test_sum += e;
            }
        }

        long stop = System.currentTimeMillis();

        long ms = (stop - start);
        System.out.println("Time: " + ms);
    }

Jeśli wiesz z góry, jak duże są dane, tablica będzie szybsza.

Lista jest bardziej elastyczna. Możesz użyć ArrayList, który jest wspierany przez tablicę.

Jeśli możesz żyć ze stałym rozmiarem, tablice będą szybsze i będą wymagały mniej pamięci.

Jeśli potrzebujesz elastyczności interfejsu List z dodawaniem i usuwaniem elementów, pozostaje pytanie, którą implementację wybrać. Często ArrayList jest zalecany i używany w każdym przypadku, ale również ArrayList ma problemy z wydajnością, jeśli elementy na początku lub na środku listy muszą zostać usunięte lub wstawione.

Dlatego możesz zajrzeć na http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list, która wprowadza GapList. Ta nowa implementacja listy łączy zalety ArrayList i LinkedList, co zapewnia bardzo dobrą wydajność dla prawie wszystkich operacji.

W zależności od implementacji. możliwe, że tablica typów pierwotnych będzie mniejsza i bardziej wydajna niż ArrayList. Wynika to z faktu, że tablica będzie przechowywać wartości bezpośrednio w ciągłym bloku pamięci, a najprostsza implementacja ArrayList zapisze wskaźniki dla każdej wartości. Szczególnie na platformie 64-bitowej może to mieć ogromne znaczenie.

Oczywiście możliwe jest, że implementacja jvm ma specjalny przypadek dla tej sytuacji, w którym to przypadku wydajność będzie taka sama.

Lista jest preferowanym sposobem w Javie 1.5 i późniejszych wersjach, ponieważ może używać generycznych. Tablice nie mogą mieć rodzajów ogólnych. Również tablice mają z góry określoną długość, która nie może dynamicznie rosnąć. Inicjowanie tablicy o dużym rozmiarze nie jest dobrym pomysłem. ArrayList to sposób na zadeklarowanie tablicy za pomocą generics i może dynamicznie rosnąć. Ale jeśli częściej używane jest usuwanie i wstawianie, wówczas połączona lista jest najszybszą strukturą danych, która zostanie użyta.

Tablice zalecane wszędzie, gdzie można ich użyć zamiast listy, szczególnie w przypadku, gdy wiesz, że liczba i rozmiar elementów nie ulegną zmianie.

Zobacz najlepsze praktyki Oracle Java: http://docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056

Oczywiście, jeśli potrzebujesz dodawać i usuwać obiekty z kolekcji wiele razy łatwe w użyciu listy.

Żadna z odpowiedzi nie zawierała interesujących mnie informacji - wielokrotne skanowanie tej samej tablicy wiele razy. Musiałem stworzyć do tego test JMH.

Wyniki (Java 1.8.0_66 x32, iteracja zwykłej tablicy jest co najmniej 5 razy szybsza niż ArrayList):

Benchmark                    Mode  Cnt   Score   Error  Units
MyBenchmark.testArrayForGet  avgt   10   8.121 ? 0.233  ms/op
MyBenchmark.testListForGet   avgt   10  37.416 ? 0.094  ms/op
MyBenchmark.testListForEach  avgt   10  75.674 ? 1.897  ms/op

Test

package my.jmh.test;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@State(Scope.Benchmark)
@Fork(1)
@Warmup(iterations = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 10)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class MyBenchmark {

    public final static int ARR_SIZE = 100;
    public final static int ITER_COUNT = 100000;

    String arr[] = new String[ARR_SIZE];
    List<String> list = new ArrayList<>(ARR_SIZE);

    public MyBenchmark() {
        for( int i = 0; i < ARR_SIZE; i++ ) {
            list.add(null);
        }
    }

    @Benchmark
    public void testListForEach() {
        int count = 0;
        for( int i = 0; i < ITER_COUNT; i++ ) {
            for( String str : list ) {
                if( str != null )
                    count++;
            }
        }
        if( count > 0 )
            System.out.print(count);
    }

    @Benchmark
    public void testListForGet() {
        int count = 0;
        for( int i = 0; i < ITER_COUNT; i++ ) {
            for( int j = 0; j < ARR_SIZE; j++ ) {
                if( list.get(j) != null )
                    count++;
            }
        }
        if( count > 0 )
            System.out.print(count);
    }

    @Benchmark
    public void testArrayForGet() {
        int count = 0;
        for( int i = 0; i < ITER_COUNT; i++ ) {
            for( int j = 0; j < ARR_SIZE; j++ ) {
                if( arr[j] != null )
                    count++;
            }
        }
        if( count > 0 )
            System.out.print(count);
    }

}

„Tysiące” nie jest dużą liczbą. Kilka tysięcy ciągów akapitowych ma rozmiar rzędu kilku megabajtów. Jeśli wszystko, co chcesz zrobić, to uzyskać dostęp do nich szeregowo, użyj niezmiennej, pojedynczo połączonej listy .

Nie wpadnij w pułapkę optymalizacji bez odpowiedniego testu porównawczego. Jak inni sugerują użycie profilera przed przyjęciem jakichkolwiek założeń.

Różne wyliczone struktury danych mają różne cele. Lista jest bardzo skuteczna we wstawianiu elementów na początku i na końcu, ale bardzo cierpi podczas dostępu do losowych elementów. Tablica ma ustaloną pamięć, ale zapewnia szybki dostęp losowy. Wreszcie ArrayList poprawia interfejs do tablicy, umożliwiając jej wzrost. Zwykle struktura danych, która ma być używana, powinna być podyktowana sposobem, w jaki przechowywane dane będą dostępne lub dodane.

O zużyciu pamięci. Wygląda na to, że mieszasz niektóre rzeczy. Tablica da ci tylko ciągłą porcję pamięci dla rodzaju posiadanych danych. Nie zapominaj, że java ma ustalone typy danych: boolean, char, int, long, float i Object (obejmuje to wszystkie obiekty, nawet tablica jest Object). Oznacza to, że jeśli zadeklarujesz tablicę ciągów znaków [1000] lub MyObject myObjects [1000], dostaniesz tylko 1000 pól pamięci wystarczająco dużych, aby pomieścić lokalizację (referencje lub wskaźniki) obiektów. Nie dostajesz 1000 pól pamięci na tyle dużych, aby pasowały do ​​wielkości obiektów. Nie zapominaj, że Twoje obiekty są najpierw tworzone za pomocą „nowego”. Dzieje się tak, gdy alokacja pamięci jest zakończona, a następnie odwołanie (ich adres pamięci) jest przechowywane w tablicy. Obiekt nie jest kopiowany do tablicy, tylko jego odwołanie.

Nie sądzę, żeby miało to naprawdę znaczenie dla Strings. To, co przylega do szeregu ciągów, to odwołania do ciągów, same ciągi są przechowywane w przypadkowych miejscach w pamięci.

Tablice kontra listy mogą mieć znaczenie dla typów pierwotnych, a nie dla obiektów. Jeśli znasz z góry liczbę elementów i nie potrzebujesz elastyczności, tablica milionów liczb całkowitych lub podwójnych będzie bardziej wydajna w pamięci i nieznacznie szybsza niż lista, ponieważ w rzeczywistości będą one przechowywane w sposób ciągły i dostępne natychmiast. Właśnie dlatego Java nadal używa tablic znaków dla ciągów, tablic liczb całkowitych dla danych obrazu itp.

Tablica jest szybsza - cała pamięć jest wstępnie przydzielana z góry.

Wiele podanych tutaj znaków mikrobenszowania znalazło liczbę kilku nanosekund dla takich odczytów, jak tablica / ArrayList. Jest to całkiem rozsądne, jeśli wszystko znajduje się w pamięci podręcznej L1.

Pamięć podręczna wyższego poziomu lub dostęp do pamięci głównej może mieć rząd wielkości razy około 10nS-100nS, w porównaniu do 1nS dla pamięci podręcznej L1. Dostęp do ArrayList ma dodatkową pośrednią pamięć, aw prawdziwej aplikacji możesz zapłacić ten koszt od prawie nigdy do każdego za każdym razem, w zależności od tego, co robi twój kod między dostępami. I oczywiście, jeśli masz wiele małych ArrayLists, może to zwiększyć zużycie pamięci i zwiększyć ryzyko utraty pamięci podręcznej.

Wydaje się, że oryginalny plakat używa tylko jednego i uzyskuje dostęp do dużej ilości treści w krótkim czasie, więc nie powinno to stanowić wielkiego problemu. Ale może być inaczej u innych osób i należy zachować ostrożność przy interpretacji mikrodruków.

Ciągi Java są jednak przerażająco marnotrawcze, szczególnie jeśli przechowujesz wiele małych (spójrz na nie za pomocą analizatora pamięci, wydaje się, że jest to> 60 bajtów dla ciągu kilku znaków). Tablica ciągów ma pośredni związek z obiektem String, a druga z obiektu String do char [], który zawiera sam łańcuch. Jeśli cokolwiek zniszczy twoją pamięć podręczną L1, to właśnie to, w połączeniu z tysiącami lub dziesiątkami tysięcy Strun. Jeśli więc mówisz poważnie - naprawdę poważnie - o zeskrobaniu jak największej wydajności, możesz spojrzeć na to inaczej. Można, powiedzmy, trzymać dwie tablice, char [] ze wszystkimi ciągami, jedna po drugiej, i int [] z przesunięciem na początku. Będzie to PITA do zrobienia czegokolwiek i prawie na pewno jej nie potrzebujesz. A jeśli tak, to ty

To zależy od tego, jak musisz uzyskać do niego dostęp.

Po zapisaniu, jeśli chcesz głównie wykonać operację wyszukiwania, z niewielkim wstawieniem / usunięciem lub bez, a następnie przejdź do tablicy (ponieważ wyszukiwanie odbywa się w O (1) w tablicach, podczas gdy dodawanie / usuwanie może wymagać ponownego uporządkowania elementów) .

Po zapisaniu, jeśli twoim głównym celem jest dodawanie / usuwanie ciągów, z niewielką lub żadną operacją wyszukiwania, to przejdź do Listy.

ArrayList wewnętrznie używa obiektu tablicy do dodawania (lub przechowywania) elementów. Innymi słowy, ArrayList jest wspierany przez strukturę danych Array. Tablica ArrayList jest skalowalna (lub dynamiczna).

Tablica jest szybsza niż tablica, ponieważ ArrayList wewnętrznie korzysta z tablicy. jeśli możemy bezpośrednio dodawać elementy do tablicy i pośrednio dodawać element do tablicy za pomocą ArrayList, zawsze mechanizm bezpośredni jest szybszy niż mechanizm pośredni.

Istnieją dwie przeciążone metody add () w klasie ArrayList:
1 add(Object) .: dodaje obiekt na końcu listy.
2 add(int index , Object ) .: wstawia określony obiekt w określonej pozycji na liście.

Jak rozmiar ArrayList rośnie dynamicznie?

public boolean add(E e)        
{       
     ensureCapacity(size+1);
     elementData[size++] = e;         
     return true;
}

Ważną kwestią do zapamiętania z powyższego kodu jest to, że sprawdzamy pojemność ArrayList przed dodaniem elementu. sureCapacity () określa, jaki jest aktualny rozmiar zajętych elementów i jaki jest maksymalny rozmiar tablicy. Jeśli rozmiar wypełnionych elementów (w tym nowego elementu, który ma zostać dodany do klasy ArrayList) jest większy niż maksymalny rozmiar tablicy, zwiększ rozmiar tablicy. Ale rozmiaru tablicy nie można dynamicznie zwiększać. To, co dzieje się wewnętrznie, to tworzenie nowej macierzy z pojemnością

Do Java 6

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

(Aktualizacja) Z Java 7

 int newCapacity = oldCapacity + (oldCapacity >> 1);

dane ze starej tablicy są również kopiowane do nowej tablicy.

Posiadanie metod ogólnych w ArrayList, dlatego Array jest szybszy niż ArrayList.

Tablice - Zawsze byłoby lepiej, gdy musimy osiągnąć szybsze pobieranie wyników

Listy - wykonuje wyniki przy wstawianiu i usuwaniu, ponieważ można to zrobić w O (1), a także zapewnia metody łatwego dodawania, pobierania i usuwania danych. Znacznie łatwiejszy w użyciu.

Ale zawsze pamiętaj, że pobieranie danych byłoby szybkie, gdy znana jest pozycja indeksu w tablicy, w której przechowywane są dane.

Można to osiągnąć dobrze, sortując tablicę. W ten sposób wydłuża się czas pobierania danych (tj. Przechowywanie danych + sortowanie danych + poszukiwanie pozycji, w której dane znajdują się). W związku z tym zwiększa to dodatkowe opóźnienie przy pobieraniu danych z tablicy, nawet jeśli mogą one być lepsze w pobieraniu danych wcześniej.

Dlatego można to rozwiązać za pomocą struktury danych trie lub struktury danych trójskładnikowych. Jak omówiono powyżej, struktura danych trie byłaby bardzo skuteczna w wyszukiwaniu danych, wyszukiwanie określonego słowa można przeprowadzić w wielkości O (1). Gdy czas ma znaczenie, tj. jeśli musisz szybko wyszukiwać i pobierać dane, możesz przejść do struktury danych trie.

Jeśli chcesz, aby Twoje miejsce w pamięci było zużywane mniej i chcesz mieć lepszą wydajność, skorzystaj z trójskładnikowej struktury danych. Oba są odpowiednie do przechowywania dużej liczby ciągów (np. Podobnych słów zawartych w słowniku).