Le differenze di prestazioni tra ArrayList e LinkedList

StackOverflow https://stackoverflow.com//questions/10656471

Domanda

Sì, questo è un vecchio argomento, ma ho ancora un po ' di confusione.

In Java, la gente dice:

  1. ArrayList è più veloce di LinkedList se posso accedere in modo casuale i suoi elementi.Penso ad accesso casuale significa "dammi l'ennesimo elemento".Perché ArrayList è più veloce?

  2. LinkedList è più veloce di un ArrayList per l'eliminazione.Ho capito questo.ArrayList lenti dall'interno il backup di matrice deve essere riassegnati.Una spiegazione di codice:

    List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.remove("b");
System.out.println(list.get(1)); //output "c"

  3. LinkedList è più veloce di un ArrayList per l'inserimento.Cosa inserimento intende qui?Se significa spostare alcuni elementi e quindi inserire l'elemento in mezzo vuoto, ArrayList dovrebbe essere più lento di LinkedList.Se l'inserimento significa solo un add(Object) operazione, come potrebbe essere lento?

È stato utile?

Soluzione

ArrayList è più veloce di LinkedList se posso accedere in modo casuale i suoi elementi.Penso ad accesso casuale significa "dammi l'ennesimo elemento".Perché ArrayList è più veloce?

ArrayList ha riferimenti diretti per ogni elemento della lista, in modo che si può ottenere l'n-esimo elemento in un tempo costante. LinkedList deve attraversare la lista dall'inizio per ottenere l'n-esimo elemento.

LinkedList è più veloce di un ArrayList per l'eliminazione.Ho capito questo.ArrayList lenti dall'interno il backup di matrice deve essere riassegnati.

ArrayList è più lento perché ha bisogno di copiare parte della matrice al fine di rimuovere le slot che è diventato gratuito.Se la cancellazione viene effettuata utilizzando il ListIterator.remove() API, LinkedList deve solo modificare un paio di riferimenti;se la cancellazione viene effettuata da un valore o un indice, LinkedList ha potenzialmente la scansione dell'intera lista prima di trovare l'elemento(s) per essere eliminati.

Se questo significa spostare alcuni elementi e quindi inserire l'elemento in mezzo vuoto, ArrayList dovrebbe essere più lento.

Sì, questo è ciò che significa. ArrayList è infatti più lento rispetto a LinkedList perché deve liberare uno slot nel mezzo della matrice.Questo comporta lo spostamento di alcuni riferimenti in giro e nel peggiore dei casi una ridistribuzione di tutto l'array. LinkedList ha appena di manipolare alcuni riferimenti.

Altri suggerimenti

Ignorare questa risposta per ora.Le altre risposte, in particolare quella di aix, sono per lo più corretto.A lungo termine sono il modo per scommettere.E se si hanno abbastanza dati (su un benchmark su una macchina, sembrava essere di circa un milione di voci) ArrayList e LinkedList attualmente lavoro come pubblicizzato.Tuttavia, ci sono alcuni punti che si applicano all'inizio del 21esimo secolo.

Moderna tecnologia di computer sembra, dal mio test, per dare un enorme margine di matrici.Elementi di un array possono essere spostati e copiato a velocità folle.Come risultato matrici e ArrayList, nella maggior parte delle situazioni pratiche, battere la LinkedList di inserimenti ed eliminazioni, spesso in modo drammatico.In altre parole, ArrayList di battere la LinkedList nel suo gioco.

L'aspetto negativo di un ArrayList si tende ad aggrapparsi spazio in memoria dopo le eliminazioni, dove LinkedList dà spazio in quanto dà le voci.

Il più grande ribasso di matrici e ArrayList è frammento di memoria libera e affaticare il garbage collector.Come un ArrayList si espande, ne crea di nuovi, più grandi matrici, copia il vecchio array per il nuovo, e libera il vecchio.La memoria si riempie di grandi blocchi contigui di memoria che non sono abbastanza grande per l'assegnazione successiva.Alla fine non c'è lo spazio adeguato per tale assegnazione.Anche se il 90% di memoria libera, non il singolo pezzo è abbastanza grande per fare il lavoro.Il GC sarà lavorare freneticamente per spostare le cose intorno, ma se ci vuole troppo tempo per riorganizzare lo spazio, verrà generata un'OutOfMemoryException.Se non rinunciare, può comunque rallentare il programma di discesa.

La cosa peggiore è che questo problema può essere difficile da prevedere.Il programma verrà eseguito una volta.Poi, con un po ' meno memoria a disposizione, nessun avviso, rallenta o si ferma.

LinkedList utilizza piccoli, delicati bit di memoria e GC amore.Funziona ancora bene quando si sta utilizzando il 99% della memoria disponibile.

Quindi, in generale, usare ArrayList per i più piccoli set di dati che non sono suscettibili di avere la maggior parte del loro contenuto eliminato, o quando si dispone di uno stretto controllo sulla creazione e la crescita.(Per esempio, la creazione di un ArrayList che utilizza il 90% della memoria e l'utilizzo senza il riempimento per la durata del programma è di multa.Continua creazione e la liberazione dell'ArrayList istanze che utilizzano il 10% di memoria ti ucciderà.) In caso contrario, andare con LinkedList (o di una Mappa di una certa specie se avete bisogno di accesso casuale).Se si dispone di ampie collezioni (diciamo più di 100.000 elementi), senza preoccupazioni per il GC e il piano di un sacco di inserimenti ed eliminazioni e non ad accesso casuale, eseguire alcuni benchmark per vedere cosa c'è di più veloce.

Il ArrayList la classe è una classe wrapper per una matrice.Esso contiene un interno di un array.

public ArrayList<T> {
    private Object[] array;
    private int size;
}

Un LinkedList è una classe wrapper per una lista collegata, con all'interno un nodo per la gestione dei dati.

public LinkedList<T> {
    class Node<T> {
        T data;
        Node next;
        Node prev;
    }
    private Node<T> first;
    private Node<T> last;
    private int size;
}

Nota, il presente codice è utilizzato per mostrare come la classe può essere, non l'effettiva attuazione.Sapendo come l'attuazione può essere, possiamo fare un'ulteriore analisi:

ArrayList è più veloce di LinkedList se posso accedere in modo casuale i suoi elementi.Penso ad accesso casuale significa "dammi l'ennesimo elemento".Perché ArrayList è più veloce?

Il tempo di accesso per ArrayList:O(1).Il tempo di accesso per LinkedList:O(n).

In un array, è possibile accedere a qualsiasi elemento utilizzando array[index], mentre in una lista collegata è necessario passare attraverso tutte le lista a partire da first fino a quando si ottiene l'elemento di cui avete bisogno.

LinkedList è più veloce di un ArrayList per l'eliminazione.Ho capito questo.ArrayList lenti dall'interno il backup di matrice deve essere riassegnati.

La cancellazione di tempo per ArrayList:Il tempo di accesso + O(n).La cancellazione di tempo per LinkedList:Il tempo di accesso + O(1).

L'ArrayList devono spostare tutti gli elementi da array[index] per array[index-1] a partire dalla voce di eliminare l'indice.La LinkedList dovrebbe passare fino a che la voce e poi cancellare il nodo con la separazione dalla lista.

LinkedList è più veloce di un ArrayList per l'eliminazione.Ho capito questo.ArrayList lenti dall'interno il backup di matrice deve essere riassegnati.

Tempo di inserzione per ArrayList:O(n).Tempo di inserzione per LinkedList:O(1).

Perché l'ArrayList può prendere O(n)?Perché quando si inserisce un nuovo elemento e l'array è pieno, è necessario creare un nuovo array con più dimensioni (è possibile calcolare la nuova dimensione con una formula come 2 * dimensioni o 3 * dimensioni / 2).La LinkedList basta aggiungere un nuovo nodo successivo all'ultimo.

Questa analisi non è solo in Java, ma in un altro linguaggio di programmazione come C, C++ e C#.

Maggiori info qui:

Sia remove() e inserire() hanno un tempo di esecuzione di efficienza di O(n) per entrambi ArrayLists e LinkedLists.Tuttavia la ragione per la trasformazione lineare del tempo deriva da due ragioni molto diverse:

In un ArrayList si ottiene l'elemento in O(1), ma, in realtà, la rimozione o l'inserimento di qualcosa lo fa O(n), in quanto tutti i seguenti elementi devono essere modificate.

In una LinkedList richiede O(n) per ottenere effettivamente l'elemento desiderato, perché dobbiamo iniziare all'inizio, fino a raggiungere l'indice desiderato.La rimozione o l'inserimento è costante una volta che si arriva lì, perché abbiamo solo da cambiare 1 di riferimento per rimuovere() e 2 riferimenti per inserire().

Quale dei due è più veloce per l'inserimento e la rimozione dipende da dove capita.Se siamo più vicini all'inizio della LinkedList sarà più veloce, perché dobbiamo passare attraverso relativamente pochi elementi.Se siamo più vicini alla fine di un ArrayList sarà più veloce, perché noi arrivare in tempo costante, e solo da cambiare le poche rimanenti elementi che seguono.

Bonus:Mentre non c'è modo di rendere questi due metodi O(1) per un ArrayList, effettivamente c'è un modo per fare questo in LinkedLists.Supponiamo di voler passare attraverso l'intero Elenco rimozione e l'inserimento di elementi sulla nostra strada.Di solito si dovrebbe partire da molto lontano per ciascun elementi utilizzando la LinkedList, abbiamo anche potuto "salvare" l'elemento corrente stiamo lavorando con un Iteratore.Con l'aiuto di un Iteratore si ottiene un O(1) efficienza di rimozione() e inserire() quando si lavora in una LinkedList.Facendo il solo vantaggio di performance sono a conoscenza di dove una LinkedList è sempre meglio di un ArrayList.

ArrayList

  • ArrayList è la scelta migliore se i nostri frequenti operazione operazione di recupero.
  • ArrayList è scelta peggiore se la nostra operazione di inserimento e cancellazione in mezzo perché internamente diverse operazioni vengono eseguite.
  • In ArrayList elementi saranno memorizzati in locazioni di memoria consecutive, di conseguenza, operazione di recupero sarà facile.

LinkedList:-

  • LinkedList è la scelta migliore se i nostri frequenti operazione di inserimento e cancellazione in mezzo.
  • LinkedList è la scelta peggiore è la nostra frequenti operazione operazione di recupero.
  • In LinkedList elementi non verrà memorizzato in una consecutivi posizione di memoria e, di conseguenza, operazione di recupero sarà complesso.

Ora venendo alle tue domande:-

1) ArrayList salva i dati in base agli indici e implementa RandomAccess interfaccia, che è un marker di interfaccia che fornisce la possibilità Casuale di un recupero di ArrayList ma LinkedList non implementa RandomAccess Interfaccia, perché ArrayList è più veloce di LinkedList.

2) La struttura di dati sottostante per LinkedList è la lista doppiamente linkata in modo di inserimento e cancellazione in mezzo è molto facile, in LinkedList non dover spostare ogni elemento per ogni cancellazione e l'inserimento di operazioni come ArrayList(che non è consigliato se la nostra operazione di inserimento e cancellazione in mezzo perché internamente diverse operazioni vengono eseguite).
Fonte

Risposta 1:ArrayList utilizza una matrice sotto il cofano.Accedere a un membro di un oggetto ArrayList è semplice come l'accesso a la matrice a ha fornito indice, supponendo che l'indice è entro i limiti del supporto di matrice.Una LinkedList è per scorrere attraverso i suoi membri per raggiungere l'n-esimo elemento.Che è O(n) per una LinkedList, rispetto a O(1) per ArrayList.

In una LinkedList gli elementi hanno un riferimento all'elemento prima e dopo di esso.In un ArrayList la struttura di dati è solo un array.

  1. Una LinkedList deve iterare N elementi per ottenere l'n-Esimo elemento.Un ArrayList ha solo bisogno di tornare elemento N di supporto di matrice.

  2. Il supporto di matrice deve essere riassegnate, per la dimensione e la matrice copiati o ogni elemento dopo aver eliminato l'elemento deve essere spostato fino a riempire lo spazio vuoto.Una LinkedList deve solo impostare il precedente riferimento all'elemento dopo l'rimosso per la prima rimosso e il successivo riferimento all'elemento prima di rimuovere, elemento per elemento dopo elemento rimosso.Più tempo per spiegare, ma più veloce da fare.

  3. Stesso motivo per cui la cancellazione qui.

ArrayList:ArrayList ha una struttura come un array, ha un diretto riferimento ad ogni elemento.Così rendom accesso è veloce nel ArrayList.

LinkedList:In LinkedList per ottenere ennesimo elemnt si devono attraversare tutta la lista, richiede tempo rispetto a ArrayList.Ogni elemento ha un link alla sua precedente & nido elemento, in modo che la cancellazione è veloce.

ArrayList: La classe ArrayList si estende AbstractList e implementa l'interfaccia Elenco e RandomAccess (marker interface).ArrayList supporta la dinamica di array che può crescere in base alle esigenze. Ci dà una prima iterazione su elementi.

LinkedList: Una LinkedList è ordinato dalla posizione di indice, come ArrayList, salvo che gli elementi sono doppiamente legati l'uno all'altro.Questo collegamento dà nuovi metodi (al di là di quello che si ottiene dall'Elenco interface) per l'aggiunta e la rimozione dall'inizio o dalla fine, che lo rende una scelta facile per l'implementazione di una pila o di coda.Tenete a mente che una LinkedList può scorrere più lentamente di un ArrayList, ma è una buona scelta quando si hanno bisogno di un rapido inserimento e cancellazione. Come di Java 5, la classe LinkedList è stato migliorato per implementare java.util.Coda di interfaccia.Come tale, ora supporta il comune di coda metodi:peek (), poll () e offerta (a).

Voglio aggiungere un ulteriore pezzo di informazioni con lei che la differenza in termini di prestazioni.

Sappiamo già che per il fatto che ArrayList l'attuazione è sostenuta da un Object[] esso supporta l'accesso casuale e il ridimensionamento dinamico e LinkedList implementazione utilizza i riferimenti per la testa e la coda di navigazione.Non ha accesso casuale capacità, ma supporta il ridimensionamento dinamico come bene.

La prima cosa è che con un ArrayList, si può immediatamente accedere all'indice, mentre con una LinkedList, devi scorrere giù per la catena di oggetti.

In secondo luogo, l'inserimento in classe ArrayList è generalmente più lento perché deve crescere ancora una volta hai colpito i suoi confini.Si dovrà creare un nuovo array più grande, e copiare i dati da quello originale.

Ma il cosa interessante è che quando si creare un ArrayList che è già abbastanza grande per soddisfare tutti i vostri inserti sarà, ovviamente, non comporta alcun array le operazioni di copia.Aggiungendo sarà anche più veloce con LinkedList perché LinkedList avrà a che fare con i puntatori, mentre enormi ArrayList imposta solo valore di indice.

enter image description here

Check out per più ArrayList e LinkedList differenze.

Anche loro sembrano identici(stessa interfaccia implementata Elenco - non thread-safe),danno risultati diversi in termini di prestazioni, aggiungere/eliminare e il tempo di ricerca e di consumo di memoria (LinkedList consuma di più).

LinkedLists può essere utilizzato se si utilizza molto di inserimento/cancellazione di prestazioni O(1).ArrayLists può essere utilizzato se si utilizza l'accesso diretto le operazioni con le prestazioni O(1)

Questo codice può chiarire questi commenti e si può cercare di capire i risultati delle prestazioni.(Scusate per la caldaia, il codice identificativo) 

public class Test {

    private static Random rnd;


    static {
        rnd = new Random();
    }


    static List<String> testArrayList;
    static List<String> testLinkedList;
    public static final int COUNT_OBJ = 2000000;

    public static void main(String[] args) {
        testArrayList = new ArrayList<>();
        testLinkedList = new LinkedList<>();

        insertSomeDummyData(testLinkedList);
        insertSomeDummyData(testArrayList);

        checkInsertionPerformance(testLinkedList);  //O(1)
        checkInsertionPerformance(testArrayList);   //O(1) -> O(n)

        checkPerformanceForFinding(testArrayList);  // O(1)
        checkPerformanceForFinding(testLinkedList); // O(n)

    }


    public static void insertSomeDummyData(List<String> list) {
        for (int i = COUNT_OBJ; i-- > 0; ) {
            list.add(new String("" + i));
        }
    }

    public static void checkInsertionPerformance(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.add(rndIndex, "test");
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));
    }

    public static void checkPerformanceForFinding(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.get(rndIndex);
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));

    }

}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top