LinkedList ou ArrayList?

Bonjour

Le Thu, 11 Apr 2019 22:27:01 +0000, jp a écrit :

J'ai un petit programme qui utilise un Vector et qui effectue beaucoup
d'opérations sur ce dernier. J'envisage de remplacer ce Vector par une
structure de données plus rapide. Je n'ai pas besoin qu'elle soit
Synchronized.

Est-ce que quelqu'un peut me dire ce qui est le plus rapide entre une
LinkedList ou une ArrayList?

ArrayList est la structure qui ressemble le plus à Vector (et qu'on
utilise à la place en général).

Pour faire le choix entre ces deux structures de données, il faut
comprendre comment elles fonctionnent :

ArrayList/Vector est un tableau extensible : on peut ajouter des données
dedans puis, quand il est plein, un tableau plus grand est alloué, les
données qui se trouvaient dans l'ancien sont recopiées dans le nouveau.
https://fr.wikipedia.org/wiki/Tableau_(structure_de_donn%C3%A9es)

LinkedList est une liste chaînée, composées de cellules liées les unes
aux autres (chacune contient des références à ses voisines, ce qui permet
de passer de l'une à l'autre). Quand on veut ajouter une valeur, on
ajoute une cellule à la liste.
https://fr.wikipedia.org/wiki/Liste_cha%C3%AEn%C3%A9e
(en java il s'agit d'une liste doublement chaînée)

Note que s'il y a 10 valeurs dans ta liste, peu importe la représentation
que tu choisis. S'il est possible qu'il y ait beaucoup de valeurs, mieux
vaut choisir la structure appropriée à tes traitements, en particulier
s'il y a beaucoup d'opérations dessus ; ça peut dépendre aussi de si tu
veux optimiser les modifications ou les consultations :
* ArrayList
- Insertions très lentes en début de tableau (il faut décaler
toutes les valeurs existantes et parfois tout recopier dans un
plus grand tableau).
- Insertions lentes en fin de tableau (il faut parfois
créer un tableau plus grand et tout recopier dedans).
- Accès très rapide à un élément par son indice (il suffit de
calculer que la case 33 se trouve à telle position,
puisqu'elles se trouvent physiquement les unes à la suite des
autres).
- Parcours rapide dans l'ordre (avec un itérateur).
* LinkedList
- Insertions très rapides en tête et en queue (il suffit
d'ajouter une cellule).
- Insertions lentes au milieu (il faut parcourir la liste
avant de trouver l'endroit où insérer la nouvelle valeur).
- Accès lent à un élément quelconque par son indice (plus rapide
près du début ou de la fin, plus long si c'est au milieu) : il
faut parcourir la liste en suivant les liens de cellule en
cellule jusqu'à celle recherchée.
- Parcours rapide dans l'ordre (avec un itérateur).

Quand je parle d'itérateur, ça peut être avec un itérateur explicite :
Iterator<String> iterateur = chaines.iterator() ;
for (...)
ou bien implicite :
for (String chaine : chaines)

Pour formaliser les choses, on utilise la notation O pour caractériser le
temps de réalisation des opérations sur les structures de données en
fonction du nombre d'éléments dedans (en fait donner une idée de comment
croît ce temps quand la structure de données contient de plus en plus de
valeurs).

Quelques exemples :
- O(1) : la durée de l'opération de dépend pas du nombre
d'éléments dans la structure (temps constant).
- O(n) : durée proportionnelle au nombre d'éléments.
- O(n²) : durée proportionnelle au carré du nombre d'éléments.
- O(n x log n) : un peu plus mauvais que la durée proportionnelle,
mais pas aussi dramatique que O(n²).

Appliqué aux deux structures plus haut :
* ArrayList
- Insertion en début de tableau : O(n²)
- Insertion en fin de tableau : O(n) [parfois il faut recopier
tout le tableau dans un plus grand]
- Insertion en milieu de tableau : comme l'insertion en début
- Accès à un élément quelconque par son indice : O(1)
- Parcours des éléments avec un itérateur : O(n)
* LinkedList
- Insertion en début de liste : O(1)
- Insertion en fin de liste : O(1)
- Insertion en milieu de liste : O(n) [il faut partir d'un
bord pour trouver l'endroit où faire l'insertion]
- Accès à un élément quelconque par son indice : O(n)
- Parcours des éléments avec un itérateur : O(n)

Je n'ai pas traité le cas des suppressions d'éléments : pour les listes
c'est pareil, pour les tableaux c'est un peu moins gênant que les
insertions parce qu'il n'y a jamais besoin d'agrandir le tableau, par
contre il faut bien décaler tous les éléments suivants d'un rang vers la
gauche.

J'ai ici négligé les caches et autres considérations de bas niveau.

Le 12/04/2019 à 00:27, jp a écrit :

Bonjour,

J'ai un petit programme qui utilise un Vector et qui effectue beaucoup
d'opérations sur ce dernier. J'envisage de remplacer ce Vector par une
structure de données plus rapide. Je n'ai pas besoin qu'elle soit
Synchronized.

Est-ce que quelqu'un peut me dire ce qui est le plus rapide entre une
LinkedList ou une ArrayList?

Merci d'avance.

Je crois que si tu veux insérer et retirer des éléments de la liste,
c'est la LinkedList qui est mieux adaptée.
Mais pour la parcourir et retrouver des éléments, utilise plutôt une
ArrayList.
Pour une utilisation mixte et généraliste, on préfère la ArrayList.

Merci à vous deux de vos réponses qui m'éclairent un peu. Je pense que je
vais opter pour la LinkedList ou peut-être même pour un simple tableau.
En fait j'ai un nombre n d'éléments et je veux tester toutes les
permutations possibles. Il y en a donc n! en tout. Ce qui fait un nombre
considérable de calculs...

Ce que faisait mon ancien programme, il stockait chaque permutation dans
un Vector en utilisant la méthode add et recopiait chaque élément, en le
supprimant ensuite, dans certaines cases d'un tableau déjà prérempli. Il
faisait ensuite la somme de la première ligne du tableau et la comparait
à une valeur de référence. Si les deux valeurs étaient égales il faisait
la même chose pour la seconde ligne, et etc... Il faisait ensuite de même
avec les colonnes, et ensuite les deux diagonales. À chaque fois que le
test s'avérait faux, il passait à la permutation suivante sans tester les
lignes ou colonnes suivantes. Et ainsi de suite tant que la permutation
qui renvoie un vrai à tous les tests n'était pas atteinte.

En fait, je me suis aperçu en faisant une estimation grossière de la
durée d'exécution de ce programme, que les calculs pouvaient bien durer,
selon la valeur de n, plusieurs millions d'années sur mon ordinateur...

Ce qui explique que je n'ai obtenu aucun résultat jusqu'à présent. C'est
pourquoi j'ai entrepris d'optimiser ce programme en changeant le Vector
par une structure plus rapide. Et aussi en essayant de réduire le nombre
de calculs si possible. Mais là c'est une autre histoire...

Je me suis aperçu également que le nombre n d'éléments ne varie pas pour
chaque calcul. Je peux donc essayer de remplacer le Vector par un simple
tableau à une dimension. Ça accélérerait les copies d'éléments.

Il faut que je me repenche sur la structure de ce programme qui date de
2003 pour voir si c'est possible. Le principal problème vient du fait que
ma méthode de recherche de toutes les permutations de mes n éléments est
basé sur un algorithme d'exploration de tout les chemins complets d'un
graphe de n éléments. J'avais trouvé cet algorithme dans un livre
d'algorithmique en langage C. Et comme en C les index des éléments
commencent à l'indice 0, j'avais été obligé de l'adapter à mon Vector
dont les index des éléments commencent à 1. C'est pour ça qu'il va me
falloir peut-être réécrire tout ou certaines parties de mon programme.

Merci encore pour vos réponses détaillées ou résumées.

Le 13/04/2019 à 22:24, jp a écrit :

Merci à vous deux de vos réponses qui m'éclairent un peu. Je pense que je
vais opter pour la LinkedList ou peut-être même pour un simple tableau.
En fait j'ai un nombre n d'éléments et je veux tester toutes les
permutations possibles. Il y en a donc n! en tout. Ce qui fait un nombre
considérable de calculs...

Ce que faisait mon ancien programme, il stockait chaque permutation dans
un Vector en utilisant la méthode add et recopiait chaque élément, en le
supprimant ensuite, dans certaines cases d'un tableau déjà prérempli. Il
faisait ensuite la somme de la première ligne du tableau et la comparait
à une valeur de référence. Si les deux valeurs étaient égales il faisait
la même chose pour la seconde ligne, et etc... Il faisait ensuite de même
avec les colonnes, et ensuite les deux diagonales. À chaque fois que le
test s'avérait faux, il passait à la permutation suivante sans tester les
lignes ou colonnes suivantes. Et ainsi de suite tant que la permutation
qui renvoie un vrai à tous les tests n'était pas atteinte.

En fait, je me suis aperçu en faisant une estimation grossière de la
durée d'exécution de ce programme, que les calculs pouvaient bien durer,
selon la valeur de n, plusieurs millions d'années sur mon ordinateur...

Ce qui explique que je n'ai obtenu aucun résultat jusqu'à présent. C'est
pourquoi j'ai entrepris d'optimiser ce programme en changeant le Vector
par une structure plus rapide. Et aussi en essayant de réduire le nombre
de calculs si possible. Mais là c'est une autre histoire...

Je me suis aperçu également que le nombre n d'éléments ne varie pas pour
chaque calcul. Je peux donc essayer de remplacer le Vector par un simple
tableau à une dimension. Ça accélérerait les copies d'éléments.

Il faut que je me repenche sur la structure de ce programme qui date de
2003 pour voir si c'est possible. Le principal problème vient du fait que
ma méthode de recherche de toutes les permutations de mes n éléments est
basé sur un algorithme d'exploration de tout les chemins complets d'un
graphe de n éléments. J'avais trouvé cet algorithme dans un livre
d'algorithmique en langage C. Et comme en C les index des éléments
commencent à l'indice 0, j'avais été obligé de l'adapter à mon Vector
dont les index des éléments commencent à 1. C'est pour ça qu'il va me
falloir peut-être réécrire tout ou certaines parties de mon programme.

Merci encore pour vos réponses détaillées ou résumées.

Je voulais te signaler simplement que si le contenu de tes listes est
un type natif du langage, (int, float, double, boolean, char, ...) tu as
intérêt à faire de simples tableaux. les listes que ce soit ArrayList ou
LinkedList contiennent des objets, éventuellement des wrappers comme
Integer, Boolean, ... et donc l'empreinte mémoire est beaucoup plus
importante.

Si ce n'est pas le cas, je te conseille de commencer avec des
ArrayList et quand ça marche tu peux facilement changer pour des
LinkedList puisque l'interface d'utilisation est la même.

L'avantage des List sur les tableaux natifs c'est surtout de pouvoir
ajouter des éléments sans avoir à gérer la taille du tableau. Si tu
connais à l'avance le nombre d'éléments et que tu cherches à gérer
efficacement des listes de grande taille, les tableaux sont peut-être la
meilleure solution.

Bon courage...

Le Sun, 14 Apr 2019 00:03:26 +0200, Elhwen Dico a écrit :

Je voulais te signaler simplement que si le contenu de tes listes est
un type natif du langage, (int, float, double, boolean, char, ...) tu as
intérêt à faire de simples tableaux. les listes que ce soit ArrayList ou
LinkedList contiennent des objets, éventuellement des wrappers comme
Integer, Boolean, ... et donc l'empreinte mémoire est beaucoup plus
importante.

C'est le cas. Mes éléments sont des int.

L'avantage des List sur les tableaux natifs c'est surtout de pouvoir
ajouter des éléments sans avoir à gérer la taille du tableau. Si tu
connais à l'avance le nombre d'éléments et que tu cherches à gérer
efficacement des listes de grande taille, les tableaux sont peut-être la
meilleure solution.

C'est ce que je commençait à me dire et c'est ce que je vais faire.

Bon courage...

Merci.

Le vendredi 12 Avril 2019 à 00:27 par jp : > Bonjour, > > J'ai un petit programme qui utilise un Vector et qui effectue beaucoup > d'opérations sur ce dernier. J'envisage de remplacer ce Vector par une > structure de données plus rapide. Je n'ai pas besoin qu'elle soit > Synchronized. > > Est-ce que quelqu'un peut me dire ce qui est le plus rapide entre une > LinkedList ou une ArrayList? > > Merci d'avance. Bonsoir , y a pas une qui est rapide de l'autre mais pour votre probleme en particulier il faut utiliser ArrayList c'est mieux https://snaptube.cam/ https://syncnet.onl/telegram-web/