ArrayList Vs LinkedList

Question

J'ai été à la suite d'un post précédent sur ce qui est dit:

For LinkedList

    * get is O(n)
    * add is O(1)
    * remove is O(n)
    * Iterator.remove is O(1)

For ArrayList

    * get is O(1)
    * add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
    * remove is O(n)

Donc, en regardant cela, j'en ai conclu que Si j'ai à faire, juste séquentielle insérer dans ma collection pour dire 5000000 élément, LinkedList surclassera ArrayList.

Et Si j'ai juste chercher les éléments de la collection par l'itération à-dire ne Pas l'accaparement de l'élément dans le milieu, encore LinkedList surclassera ArrayList.

Maintenant, pour vérifier mes deux rapports ci-dessus, j'ai écrit ci-dessous exemple de programme... Mais je suis surpris de voir que mon énoncés ci-dessus ont été révélées fausses.

Liste de tableaux surclasser Linkedlist dans les deux cas. Il a fallu moins de temps que LinkedList pour ajouter ainsi à la corvée de la Collecte. Est-ce que je fais mal, ou les déclarations initiales sur LinkedList et ArrayList n'est pas vrai pour les collections de taille 5000000?

Je l'ai mentionné taille, parce que si je réduire le nombre d'éléments à 50000, LinkedList de mieux performer et de la déclaration initiale est vrai.

long nano1 = System.nanoTime();

List<Integer> arr = new ArrayList();
for(int i=0;i<5000000;++i){
    arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );

for(int j: arr){
    ;
}
System.out.println( (System.nanoTime() - nano1) );

long nano2 = System.nanoTime();

List<Integer> arrL = new LinkedList();
for(int i=0;i<5000000;++i){
    arrL.add(i);
}
System.out.println( (System.nanoTime() - nano2) );

for(int j:arrL){
    ;
}
System.out.println( (System.nanoTime() - nano2) );

Answer 1

Rappelez-vous que big-O complexité décrit le comportement asymptotique et peut ne pas refléter la réalité de la mise en œuvre de vitesse. Il décrit comment le coût de chaque opération augmente avec la taille de la liste, et non pas la vitesse de chaque opération. Par exemple, la suite de la mise en œuvre de l' add O(1) mais n'est pas rapide:

public class MyList extends LinkedList {
    public void add(Object o) {
        Thread.sleep(10000);
        super.add(o);
    }
}

Je soupçonne que dans votre cas ArrayList fonctionne bien parce qu'il augmente la taille du tampon interne de façon assez énergique donc, il n'y aura pas un grand nombre de réaffectations. Lorsque la mémoire tampon n'a pas besoin d'être redimensionnée ArrayList aura plus rapide adds.

Vous devez également être très prudent lorsque vous effectuez ce type de profilage. Je voudrais vous suggérer de changer votre code de profilage de faire une phase d'échauffement (de sorte que le JIT a l'occasion de faire de l'optimisation, sans incidence sur vos résultats) et la moyenne des résultats sur un certain nombre de pistes.

private final static int WARMUP = 1000;
private final static int TEST = 1000;
private final static int SIZE = 500000;

public void perfTest() {
    // Warmup
    for (int i = 0; i < WARMUP; ++i) {
        buildArrayList();
    }
    // Test
    long sum = 0;
    for (int i = 0; i < TEST; ++i) {
        sum += buildArrayList();
    }
    System.out.println("Average time to build array list: " + (sum / TEST));
}

public long buildArrayList() {
    long start = System.nanoTime();
    ArrayList a = new ArrayList();
    for (int i = 0; i < SIZE; ++i) {
        a.add(i);
    }
    long end = System.nanoTime();
    return end - start;
}

... same for buildLinkedList

(À noter qu' sum peut déborder et vous pourriez être mieux d'utiliser System.currentTimeMillis()).

Il est également possible que le compilateur est l'optimisation de loin votre vide get boucles. Assurez-vous que la boucle ne fait quelque chose pour s'assurer que le bon code est appelé.

Answer 2

C'est un mauvais indice de référence de l'OMI.

• besoin de répéter en boucle plusieurs fois pour se réchauffer de la jvm
• besoin de FAIRE quelque chose dans votre boucle itérative ou elle peut être optimisée tableau
• ArrayList redimensionne, ce qui est coûteux. Si vous le avait construit ArrayList comme new ArrayList(500000) vous serait de construire d'un seul coup, et puis toutes les allocations devraient être assez bon marché (un preallocating soutenu tableau)
• Vous ne précisez pas votre mémoire de la JVM - il doit être exécuté avec -xMs == -Xmx (tout préaffectés) et suffisamment élevé pour qu'aucun GC est susceptible d'être déclenchée
• Ce test ne permet pas de couvrir le plus désagréable aspect de la LinkedList à accès aléatoire. (un itérateur n'est pas forcément la même chose). Si vous nourrissez-dire 10% de la taille d'une grande collection comme une sélection aléatoire d' list.get vous trouverez linkedlists sont terribles pour saisir autre chose que le premier ou le dernier élément.

Pour une liste de tableaux: le jdk obtenez est ce que vous attendez:

public E get(int index) {
    RangeCheck(index);

    return elementData[index];
}

(en gros, il suffit de retourner le tableau indexé élément.,

Pour une linkedlist:

public E get(int index) {
    return entry(index).element;
}

ressemble? Pas tout à fait. l'entrée est une méthode qui n'est pas une primitive de tableau, et regardez ce qu'il a à faire:

private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

C'est vrai, si vous demandez pour dire list.get(250000),, ça doit commencer à la tête et à plusieurs reprises itérer sur l'élément suivant. 250000 accède ou alors (il y a une optimisation dans le code où il commence à tête ou de queue, en fonction de ce qui serait de moins en moins accès.)

Answer 3

Une ArrayList est une simplification de la structure de données que d'une LinkedList. Une liste de tableaux a qu'un seul tableau de pointeurs en mémoire contiguë endroits. Il n'a qu'à être recréé si le tableau est élargi au-delà de sa taille allouée.

Une LinkedList est constitué d'une chaîne de nœuds; chaque nœud est séparé alloué et a l'avant et à l'arrière des pointeurs vers d'autres nœuds.

Alors qu'est-ce que cela signifie? Sauf si vous avez besoin d'insérer dans le milieu, splice, supprimer dans le milieu etc. une liste de tableaux sera généralement plus rapide. Il a besoin de moins d'allocations de mémoire, a beaucoup mieux la localité de référence (ce qui est important pour la mise en cache du processeur) etc.

Answer 4

Pour comprendre pourquoi les résultats que vous avez obtenu ne pas en contradiction avec le "big O" caractérisation. Nous avons besoin de revenir à des principes; c'est à dire la définition.

Soit f(x) et g(x) deux fonctions définies sur un sous-ensemble des nombres réels. On écrit

f(x) = O(g(x)) as x -> infinity

si, et seulement si, pour suffisamment grandes valeurs de x, f(x) est au plus une constante multipliée par g(x) en valeur absolue. C'est, f(x) = O(g(x)) si et seulement si il existe un nombre réel positif M et un nombre réel x0 tel que

|f(x)| <= M |g(x)| for all x > x_0.

Dans de nombreux contextes, l'hypothèse que nous sommes intéressés par le taux de croissance de la variable x tend vers l'infini est laissé implicite, et on écrit plus simplement que f(x) = O(g(x)).

Ainsi, l'énoncé add1 is O(1), signifie que le coût du temps d'un add1 opération sur une liste de taille N tend vers une constante C_add1 lorsque N tend vers l'infini.

Et l'énoncé add2 is O(1) amortized over N operations, signifie que la moyenne des coûts en temps d'une séquence de N add2 des opérations tend vers une constante C_add2 lorsque N tend vers l'infini.

Qu'est-ce que ne dit pas c'est que ces constantes C_add1 et C_add2 . En fait, la raison qui LinkedList est plus lent que ArrayList dans votre test, c'est que C_add1 est plus grand que C_add2.

La leçon est que big O notation ne permet pas de prévoir absolu, ni même la performance relative. Tous il prédit est la forme de la performance de la fonction de contrôle variable devient très grande. C'est utile de le savoir, mais elle ne vous dit pas tout ce que vous devez savoir.

Answer 5

Le big-O-notation n'est pas sur absolut timings, mais à propos de la relative timings, et vous ne pouvez pas comparer les chiffres d'un algorithme à l'autre.

Vous obtenez seulement l'information sur la façon dont le même algorithme réagit à l'augmentation ou à la baisse du nombre de n-uplets.

Un algorithme peut prendre une heure pour une opération, et 2h pour les deux opérations, et est O(n), et un autre est en O(n), et prend une milliseconde pour une opération, et de deux millisecondes pour les deux opérations.

Une autre question si la mesure avec la JVM est l'optimisation du point d'accès-compilateur. Un ne-rien-boucle peut être éliminé par le JIT-compilateur.

Une troisième chose à considérer est l'OS et de la JVM, à l'aide de caches et de l'exécution de la collecte des déchets pendant ce temps.