Différence entre ArrayList et LinkedList en Java - les tenants de la performance
J'ai pensé que j'ai compris la différence entre ArrayList et LinkedList théoriquement assez bien. Cependant, c'est la première fois, je l'ai mis à un petit test, et les tests est sorti, bien différent de mes attentes.
Attentes :
-
Arraylist sera plus lente que LinkedList lors de l'insertion à l'
début, car c'est de "déplacer" les éléments, pour linkedlist, son
juste la mise à jour de 2 références.Réalité : je suis arrivé à être le même sur la plupart des itérations. Pour une poignée d'
itérations, il a été plus lente. -
Arraylist sera plus lente que LinkedList lors de la suppression, au début, car c'est de "déplacer" les éléments, pour Linkedlist, c'est juste de détruire un élément.
Réalité : la Performance a été de même lors de la suppression de mendier.
Cas de Test : 1 000 000 d'éléments
public static void main(String[] args) {
int n = 1000000;
List arrayList = new ArrayList(n+10);
long milis = System.currentTimeMillis();
for(int i= 0 ;i<n;i++){
arrayList.add(i);
}
System.out.println("insert arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
List linkedList = new LinkedList();
milis = System.currentTimeMillis();
for(int i= 0 ;i<n;i++){
linkedList.add(i);
}
System.out.println("insert linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
//System.out.println("Adding at end");
milis = System.currentTimeMillis();
arrayList.add(n-5,n+1);
System.out.println("APPEND arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
linkedList.add(n-5,n+1);
System.out.println("APPEND linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
//add at front
milis = System.currentTimeMillis();
arrayList.add(0,0);
System.out.println("INSERT BEG arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
linkedList.add(0,0);
System.out.println("INSERT BEG linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
//add at middle
milis = System.currentTimeMillis();
arrayList.add(n/2,n/2);
System.out.println("INSERT MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
linkedList.add(n/2,n/2);
System.out.println("INSERT MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
//get from front, mid, end
milis = System.currentTimeMillis();
arrayList.get(0);
System.out.println("get front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
linkedList.get(0);
System.out.println("get front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
arrayList.get(n/2);
System.out.println("get MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
linkedList.get(n/2);
System.out.println("get MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
arrayList.get(n-4);
System.out.println("get last arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
linkedList.get(n-4);
System.out.println("get last linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
//delete from front, mid, end.
milis = System.currentTimeMillis();
arrayList.remove(0);
System.out.println("del front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
linkedList.remove(0);
System.out.println("del front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
arrayList.remove(n/2);
System.out.println("del mid arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
linkedList.remove(n/2);
System.out.println("del mid linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
arrayList.remove(n-4);
System.out.println("del end arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
milis = System.currentTimeMillis();
linkedList.remove(n-4);
System.out.println("del end linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
}
Journal De Sortie
insert arraylist takes 141 ms
insert linkedlist takes 312 ms
APPEND arraylist takes 0 ms
APPEND linkedlist takes 0 ms
INSERT BEG arraylist takes 0 ms
INSERT BEG linkedlist takes 0 ms
INSERT MIDDLE arraylist takes 0 ms
INSERT MIDDLE linkedlist takes 0 ms
get front arraylist takes 0 ms
get front linkedlist takes 0 ms
get MIDDLE arraylist takes 0 ms
get MIDDLE linkedlist takes 16 ms
get last arraylist takes 0 ms
get last linkedlist takes 0 ms
del front arraylist takes 0 ms
del front linkedlist takes 0 ms
del mid arraylist takes 0 ms
del mid linkedlist takes 15 ms
del end arraylist takes 0 ms
del end linkedlist takes 0 ms
Alors, quelle est la raison? JDK 1.6 utilisé.
EDIT : Après l'utilisation du Système.nanotime(), il ne me donner les réponses que j'attendais. D'accord, ce n'est qu'un seul essai, et devrait être en moyenne.
insert arraylist takes 137076082 ns
insert linkdlist takes 318985917 ns
APPEND arraylist takes 69751 ns
APPEND linkdlist takes 98126 ns
**INSERT BEG arraylist takes 2027764 ns
INSERT BEG linkdlist takes 53522 ns**
INSERT MIDDLE arraylist takes 1008253 ns
INSERT MIDDLE linkdlist takes 10395846 ns
get front arraylist takes 42364 ns
get front linkdlist takes 77473 ns
get MIDDLE arraylist takes 39499 ns
get MIDDLE linkdlist takes 9645996 ns
get last arraylist takes 46165 ns
get last linkdlist takes 43446 ns
**del front arraylist takes 1720329 ns
del front linkdlist takes 108063 ns**
del mid arraylist takes 1157398 ns
del mid linkdlist takes 11845077 ns
del end arraylist takes 54149 ns
del end linkdlist takes 49744 ns
System.nanoTime()
Je me demande combien de temps l'autoboxing de int prend dans votre cas, sur votre premier passage, vous serez combler les Entiers cache
D'accord avec @Nishant ci-dessus. L'0ms pour la plupart des tests n'est pas utile. Le temps réel peut être dire 50nanoseconds vs 300nanoseconds.
Ne pas faire un seul test, faire la moyenne, comme vous le faites sur votre premier essai
Oui, merci Nishant, mon erreur. Retour à nanos, justifie les attentes.
OriginalL'auteur Achow | 2013-03-01
Vous devez vous connecter pour publier un commentaire.
L'explication de vos deux premières (bizarre) tester les nombres est:
De l'insertion dans ArrayList est généralement plus lent, car il a de croître une fois que vous atteint ses limites. Il sera nécessaire de créer un nouveau grand tableau, et de copier des données à partir de l'original.
Mais lorsque vous créez une liste de tableaux qui est déjà énorme assez pour s'adapter à tous vos inserts (ce qui est votre cas puisque vous êtes en train de faire
new ArrayList(n+10)
) - il sera bien évidemment de ne pas impliquer n'importe quel tableau de la copie des opérations. En ajoutant à cela le sera encore plus rapide qu'avec LinkedList parce que LinkedList aura à faire face à ses "liens" (pointeurs), tandis que l'énorme liste de tableaux que des séries de la valeur à la donnée (le dernier) de l'indice.Aussi vos tests ne sont pas bonnes parce que chaque itération consiste à l'autoboxing (conversion de int en Entier) - il va à la fois prennent plus de temps pour le faire et aussi visser les résultats en raison de la Entiers cache qui sera rempli lors de la première passe.
OriginalL'auteur Oleg Mikheev
int n = 1000000;
est trop petit. Vous obtenez0 ms
ne veut pas dire qu'il ne prend pas de temps pour terminer l'insertion ou la suppression. Cela signifie que le temps écoulé est inférieur à 1ms . Essayez la hausse du nombre deint n = 1000000;
. Vous pouvez voir la différence ensuite.EDIT: j'ai mal lu votre code. J'ai pensé que vous insérez
n
éléments à l'avant du tableau de la liste. Vous devriez certainement insérer plusieurs éléments au lieu d'insérer une seule.Un AUTRE EDIT: Si vous insérez
n
éléments, vous n'auriez pas besoin d'augmenter la valeur den
. À l'inverse, vous auriez probablement eu envie de le diminuer en raison de l'insertion dans le front de liste de tableaux est une opération lente.OriginalL'auteur Careal Manic
Avec une liste de tableaux, de les insérer au milieu de l'opération va être en deux étapes en termes de connaissances théoriques Big Oh:
Avec une LinkedList, si le Nœud n'est pas encore connu (boucle du nœud de tête), il est également à deux étapes:
Cependant, outre les attendus de la complexité algorithmique, il y a d'autres points qui peuvent avoir un impact sur la réelle de l'exécution:
Langue spécifique implémentations peuvent faire parties spécifiques d'un processus plus rapide. Dans ce cas, Java arraycopy(), qui ArrayList les utilisations, les coutures plus rapide qu'une boucle de la copie de chaque valeur. Cela pourrait ne pas être vrai pour tous les tableaux (les tailles, les types) - encore une fois, elle sera mise en œuvre spécifique.
Big Oh ignore constantes qui pourraient avoir un impact sur certains jeux de données. Par exemple, le Tri à Bulles est O(n*n), mais peut détecter un pré-tableau trié en O(n) et est très rapide avec la quasi-trier les tableaux.
LinkedList nécessite plus de mémoire pour être demandées à la machine virtuelle (création de l'objet Nœud). Les processus qui requièrent plus de mémoire pour être demandées peuvent parfois être à l'origine de goulots d'étranglement.
Pour résumer: méfiez-vous des hypothèses théoriques et toujours de mesurer, de préférence avec des données du monde réel et des opérations :).
OriginalL'auteur MyNameIsZero