Piles et tableaux

Version imprimable

20/10/2016, 13h23
je viens du sud

Piles et tableaux

Bonjour,
pourquoi utiliser une pile chainée lorsque on a le type tableau ?
quelle sont les avantages ?
merci
20/10/2016, 19h56
DonQuiche

L'énoncé est trop imprécis pour se prononcer avec certitude (les types en question peuvent avoir différentes mises en œuvre et opérations selon les langages) mais je peux toujours hasarder :

* La sémantique est différente : un tableau peut certes faire office de pile, mais quand on voit "pile" on comprend tout de suite quel usage est fait de ces données.

* Concurrence : un tableau est typiquement mis en œuvre via structure mutable, alors qu'une pile chaînée est une structure persistante (immuable). Autrement dit on peut partager une pile chaînée avec d'autres threads et chacun sera libre d'en faire ce qu'il désire sans qu'aucune synchronisation soit nécessaire.
20/10/2016, 20h57
je viens du sud

merci pour ta réponse.
je commence à comprendre ;)
22/10/2016, 09h16
anapurna

salut,

comme on te l'a dis tout depend du langage
mais tu peut essayer de voir cela de façon plus pragmatique

une pile ... c'est un peu comme une pile d'assiete dernier entré premier sortie
pour un tableau tu as un acces direct a n'importe quelle cellule sans pour autant extraire la valeur
22/10/2016, 11h24
François DORIN

Citation:

Envoyé par DonQuiche

* Concurrence : un tableau est typiquement mis en œuvre via structure mutable, alors qu'une pile chaînée est une structure persistante (immuable). Autrement dit on peut partager une pile chaînée avec d'autres threads et chacun sera libre d'en faire ce qu'il désire sans qu'aucune synchronisation soit nécessaire.

D'une part, ce raisonnement est faux. En effet, ce n'est pas la pile chaînée qui est une structure persistante, mais l'implémentation utilisée qui peut l'être.

Ensuite, je suis d'accord que le côté immuable à l'énorme avantage d'apporter une sécurité dans un contexte multithread. Par contre, cela m'étonnerait fortement qu'une implémentation d'une pile chaînée puisse être immuable ! Comment faire sinon pour ajouter un nouvel élément ? Ou en retirer un ? La seule solution serait de copier l'intégralité de la pile existante en y apportant les modifications nécessaires, puis en utilisant cette nouvelle instance de pile chaînée. Mais dans ce cas, l'aspect "chaîné" de la pile perd tout son sens...
23/10/2016, 13h24
DonQuiche

Citation:

Envoyé par dorinf

D'une part, ce raisonnement est faux. En effet, ce n'est pas la pile chaînée qui est une structure persistante, mais l'implémentation utilisée qui peut l'être.

Ensuite, je suis d'accord que le côté immuable à l'énorme avantage d'apporter une sécurité dans un contexte multithread. Par contre, cela m'étonnerait fortement qu'une implémentation d'une pile chaînée puisse être immuable ! Comment faire sinon pour ajouter un nouvel élément ? Ou en retirer un ? La seule solution serait de copier l'intégralité de la pile existante en y apportant les modifications nécessaires, puis en utilisant cette nouvelle instance de pile chaînée. Mais dans ce cas, l'aspect "chaîné" de la pile perd tout son sens...

Dans la quasi-totalité des cas une pile chaînée n'est pas basée sur un tableau mais sur des objets indépendants (couple valeur + parent). On empile en créant une nouvelle tête qui référence l'ancienne (sans modifier celle-ci) et on dépile en remplaçant la valeur du champ local "tête" par le parent de la tête (sans modifier celle-ci). C'est presque la seule implémentation viable et elle est persistante/immuable.

Quant à baser une pile sur un tableau (ou zone mémoire contiguë), autant utiliser une pile non-chaînée !

La seule raison qui me vienne en tête pour baser une pile chaînée sur un tableau serait de vouloir stocker plusieurs structures de données dans le même tableau. Ce qui relèverait d'une gestion mémoire manuelle poussée, probablement due à un environnement exotique très contraint. Ca reste très marginal.
23/10/2016, 14h00
François DORIN

Citation:

Envoyé par DonQuiche

Dans la quasi-totalité des cas une pile chaînée n'est pas basée sur un tableau mais sur des objets indépendants (couple valeur + parent). On empile en créant une nouvelle tête qui référence l'ancienne (sans modifier celle-ci) et on dépile en remplaçant la valeur du champ local "tête" par le parent de la tête (sans modifier celle-ci). C'est presque la seule implémentation viable et elle est persistante/immuable.

Donc les éléments de la pile chaînée sont immuables. La dessus, on est d'accord. Par contre, l'entête de ta pile chaînée, qui contient le premier élément, est bien modifié, donc non immuable. Donc ta liste n'est pas immuable. Et avec une telle implémentation, l'ajout simultané de 2 éléments sans mécanisme de protection par deux threads différents peut résulter en une pile finale n'ayant qu'un seul des deux éléments !

Citation:

Envoyé par DonQuiche

Quant à baser une pile sur un tableau (ou zone mémoire contiguë), autant utiliser une pile non-chaînée !

Ca tombe bien, je n'ai jamais parlé d'implémentation utilisant un tableau ;) Car dans ce cas, effectivement, autant ne pas utilisé de pile chaînée.
23/10/2016, 15h29
picodev
Bonjour,

en fait c'est pas super compliqué. Une pile reste toujours une pile, ensuite il y a des avantages/inconvénients inhérents à chaque implémentation :
- liste chaînée sans récupération
  Il y a beaucoup d'allocation/libération ce qui peut entraîner une fragmentation de la mémoire. Les données peuvent être réparties un peu partout en mémoire. Il n'y a pas de limitation arbitraire au nombre d'éléments.
- liste chaînée avec récupération
  On réduit les allocations/libérations mais en contre partie on utilise plus de mémoire. Il n'y a pas de limitation arbitraire au nombre d'éléments.
- tableau à taille statique
  On met d'office une limite au nombre maximum d'éléments contenu dans la pile. La mémoire utilisée est constante et les données locales.
- tableau à taille variable
  Les données restent locales mais pour garder un temps amorti comparable à une implémentation à base de tableau statique la capacité de la pile doit croître exponentiellement ce qui peut amener à une grande consommation de mémoire. Les données sont locales.Il n'y a pas de limitation arbitraire au nombre d'éléments.
Ensuite pour un type pile on peut en général avoir une implémentation aussi bien à base de mutex ou lock free si on passe à l'aspect multi-threading.
24/10/2016, 02h53
DonQuiche

Citation:

Envoyé par dorinf

Donc les éléments de la pile chaînée sont immuables. La dessus, on est d'accord. Par contre, l'entête de ta pile chaînée, qui contient le premier élément, est bien modifié, donc non immuable. Donc ta liste n'est pas immuable. Et avec une telle implémentation, l'ajout simultané de 2 éléments sans mécanisme de protection par deux threads différents peut résulter en une pile finale n'ayant qu'un seul des deux éléments !

Sauf que ta liste en question se résume à un seul champ de 4 ou 8 octets. Tu peux très bien passer ça par valeur (aucun surcoût, accès plus rapide) ou créer un clone (coût d'une seule instanciation). D'ailleurs dans les langages modernes qui distinguent des types valeurs et références, c'est presque toujours un type valeur.

Citation:

Ca tombe bien, je n'ai jamais parlé d'implémentation utilisant un tableau

A vrai dire je crois que tu n'avais rien de précis en tête. Une liste chaînée c'est l'implémentation standard que j'ai décrite et ses variantes, sauf cas exceptionnel et anecdotique.
24/10/2016, 08h27
François DORIN

Citation:

Envoyé par DonQuiche

Sauf que ta liste en question se résume à un seul champ de 4 ou 8 octets. Tu peux très bien passer ça par valeur (aucun surcoût, accès plus rapide) ou créer un clone (coût d'une seule instanciation). D'ailleurs dans les langages modernes qui distinguent des types valeurs et références, c'est presque toujours un type valeur.

Et si tu utilises un type valeur tu n'auras effectivement aucun problème, puisqu'il sera tout simplement impossible d'utiliser la même pile dans deux threads distincts. Ce sera toujours deux piles avec les mêmes éléments où la modification de l'une n'affectera pas l'autre. La situation est la même si tu utilises des références en créant un clone de ta pile à chaque modification.

Si on se replace dans le contexte que tu as toi-même décrit, à savoir "partager une pile chaînée avec d'autres threads", ta pile chainée doit être de type référence et non de type valeur, et ne peut pas être basée sur une solution utilisant le clonage. Tu n'as pas le choix sur ces points. Et donc, pour garantir le bon fonctionnement de ta pile, tu as besoin de recourir à un mécanisme de synchronisation.

Citation:

Envoyé par dorinf

Si on se replace dans le contexte que tu as toi-même décrit, à savoir "partager une pile chaînée avec d'autres threads", ta pile chainée doit être de type référence et non de type valeur, et ne peut pas être basée sur une solution utilisant le clonage. Tu n'as pas le choix sur ces points. Et donc, pour garantir le bon fonctionnement de ta pile, tu as besoin de recourir à un mécanisme de synchronisation.

Soit il y a méprise sur le sens du mot "partager", soit tu ne comprends pas la mise en oeuvre.

Par partager je voulais simplement dire qu'on pouvait gratuitement fournir à chaque thread une copie de la pile sans aucun coût de copie (du moins pas plus que le coût d'un passage par référence). La pile elle-même est de type valeur, propre à chaque thread, mais ses noeuds internes sont de type référence, immuables et partagés.

Le fait de n'avoir aucun coût de copie est ce qui rend cette structure si utile pour la programmation concurrente, ou pour les algorithmes nécessitant la préservation de plusieurs captures temporelles de la pile (par exemple recherche de chemin).
Code:

1 2 3 4 5 6 7 struct Stack<T> { class Node { readonly Node parent; readonly T item; } Node head; void Push(T item) { head = new Node(head, item); } T Pop() { var item = head.item; head = head.parent; return item; } }

24/10/2016, 13h46
François DORIN

Citation:

Envoyé par DonQuiche

Soit il y a méprise sur le sens du mot "partager", soit tu ne comprends pas la mise en oeuvre.

Effectivement, notre désaccord vient de là ;)

Pour toi, partager ces fournir une copie à chaque thread. Pour moi, c'est fournir la pile (la même) à chaque thread.
25/10/2016, 15h27
DonQuiche

Citation:

Envoyé par dorinf

Pour toi, partager ces fournir une copie à chaque thread. Pour moi, c'est fournir la pile (la même) à chaque thread.

La confusion vient du fait qu'en général quand on manipule ce genre de pile, on manipule directement les noeuds (références partagés). Le plus souvent il n'y a pas de structure "pile" (valeur non-partagée) pour les encapsuler.