Discussion :

[inddzen]

Je dois implémenter un algorithme pour la mémorisation d'une matrice sous la forme d'un vecteur, pour l'assemblage de la matrice de rigidité en element finis pour les connaisseurs.
Le fait est que je ne connais pas exactement la taille finale du vecteur, bien sur je peux prendre une valeur max , mais je prefere explorer l'idée de la liste, tout en sachant que mon interet est autant la vitesse d'exécution que la mémoire.

J'aimerais donc avoir votre avis sur ces deux structures, spécialement en ce qui concerne la vitesse de parcours et le cout de l'ajout d'un element quelque part au milieu de la liste par rapport a une simple affectation dans un vecteur.

Merci d'avance

[ToTo13]

Bonjour,

ce problème fut déjà traité sur le forum, cherche un peu.

Mais en résumé cela dépend du type de matrice dont tu disposes :
- pleine => tableau.
- Creuse, diagonale => liste
- triangulaire => tableau adapté (triangulaire).

[inddzen]

Je m'intéresse uniquement a la complexité d'un Vecteur comparée a celle d'une Liste et non des solutions possibles, j'ai parlé du type de problème que je traite juste pour donner une idée.

[mchk0123]

Si j'ai bien compris les points critiques dans ton exemple sont : l'ajout et le recherche du nième éléments (la suppression étant marginale).

De mémoire :

- en moyenne la performance de l'ajout est la même pour Array & List, la seule différence étant que Array alloue la mémoire par "grappe" (moins de fragmentation)

- la recherche d'un élément (accès aléatoire), en revanche, est de loin beaucoup plus rapide avec les Array (en O(1)) que les List (en O(n))

[souviron34]

par contre, pour un très grand nombre variable d'éléments , une liste est préférable, à moins de connaître le maximum que l'on peut avoir et de disposer de la mémoire suffisante pour tout allouer.

En effet, si on ne dispose pas (ou qu'on ne veuille pas) dimensionner une très grande zone, si l'on se base sur array, il faudra la réallouer. Et cela créera des trous de plus en plus gros, et donc le programme grossira avec le temps (en général, sauf cas très particuliers, une libération d'un tableau ne libère pas vraiment la mémoire, mais l'accès à la zone).

Si on se base sur une liste, on n'alloue qu'un seul élément à la fois, et donc la place est minimum, et si on en détruit un, il y a de fortes chances pour que le suivant à allouer occupe la même place...


Et en termes de vitesse d'accès, si les 2 facteurs sont conjugués, on peut dans certains cas arriver à avoir presque (pas vraiment, mais on peut s'en approcher) les avantages d'une array avec une liste en accès aléatoire :

On peut faire un tableau des adresses de certains éléments de la liste, et partir de ces éléments là... (si il y a un critère qu'on connait dans le remplissage, par exemple le temps).

Donc il faut connaître le problème à résoudre, et en fonction de ce problème choisir la solution la plus adaptée.