stack ou queue ?

Version imprimable

26/04/2018, 11h20
Legro

stack ou queue ?

Bonjour,

J'ai besoin d'utiliser un conteneur et je m'interroge au niveau de la rapidité de traitement. Lequel serait le meilleur ?

A la base j'hésitais entre stack et queue en ayant l'impression que stack serait plus rapide.

Mais après réflexion je me demande si les deux ne sont pas en fait tout aussi lents puisqu'ils ne sont que des adaptateurs et non pas en eux mêmes des conteneurs.
Et alors tant qu'a faire autant utiliser un vector...

Je précise que le seul paramètre qui me préoccupe est la rapidité de traitement et qu'un LIFO ou FIFO ou autre forme d'accès m'est (dans ce cas) indifférent.

Merci.
26/04/2018, 11h26
Bousk

Salut,

vector devrait toujours être le container par défaut.
Cela dit il faudrait au moins décrire ce traitement pour savoir lequel serait mieux ou comment le faire mieux.
26/04/2018, 13h39
dalfab

stack<> est par défaut implémenté au dessus de vector<>, alors que queue<> est au dessus de deque<>.
Celui qui ira le plus vite, c'est celui qui correspond à ton besoin. Et si tu as besoin d'une queue<>, utiliser une queue<> ou un deque<> sera aussi optimum, et il faudra vraisemblablement éviter le vector<> dans ce cas.
26/04/2018, 13h48
koala01
Salut,

Si la seule chose qui t'intéresse, c'est la rapidité d'accès aux éléments, sans ajouts, sans retraits, alors, la question ne se pose pas: il te faut un tableau.

Cela pourrait cependant impliquer une certaine baisse (et même une baisse certaine dans le pire des cas) des performances au moment de remplir ta collection. Il vaut donc mieux en être conscient ;)

De même, la recherche peut, dans le meilleur des cas, se faire en O(log(N) ), si les éléments sont correctement tirés, mais pourrait s'étendre à du O(N) dans le cas contraire, et l'unicité des éléments n'est absolument pas garantie.

Si tu passe ton temps à ajouter / retirer des éléments (sans commencer à les chercher), la liste sera sans doute pour toi.

Si tu passes d'avantage de temps à chercher un élément particulier parmi "tant d'autres", le tableau trié est l'idéal, mais, à défaut de pouvoir garantir le tri, les structures basées sur les arbres binaires seront tes amies.

Pile et file (stack et queue) posent de très sérieux problèmes en terme d'accès aux éléments, ce qui justifie d'ailleurs leur nom:
- dans une pile, tu ne peux pas accéder à un élément avant d'avoir retiré tous les éléments qui ont été ajoutés après celui auquel tu veux accéder
- dans une pile, tu ne peux accéder à un élément qu'après avoir retiré ceux qui ont été ajouté avant celui auquel tu veux accéder.
LIFO et FIFO ne sont donc pas que des concepts! Ce sont bel et bien des notions qui viennent avec des notions dont il faut tenir compte. Il est particulièrement rare de se trouver dans une situation dans laquelle l'ordre dans lequel tu accèdes à tes données n'a absolument aucune importance ;)
26/04/2018, 18h46
Legro

Merci à tous de votre participation,

En fait mon besoin est le suivant : ayant un programme avec un certain nombre de fonctions qui peuvent se renvoyer les une aux autres, il y a une forme de désordre qui s'installe, des appels nombreux et incontrolés. Qui plus est, je crains de que l'application ne tombe un jour dans une boucle infinie. Je cherche donc à neutraliser cette liberté qu'ont les fonctions à s'appeler, et à créer à la place une "liste d'attente". De telle sorte qu'une fonction lorsqu'elle devrait en appeler une autre, inscrive au lieu de cela sa demande dans la liste d'attente, et le programme 'main' se chargera plus tard de faire les appels.
Notons que l'ordre de traitement des données n'a pas d'importance, pour peu qu'elles soient toutes bien traitées.
La vitesse de traitement, elle par contre, est cruciale.
Je cherche donc quel est le meilleur moyen de créer cette liste, sachant que je vais devoir très souvant y ajouter et en retirer des éléments (et que même lorsque je suis en train d'en retirer, d'autres vont s'y ajouter) , mais que l'ordre n'a aucune importance.
26/04/2018, 19h32
koala01
Oui, donc, tu vas passer ton temps à ajouter et à supprimer des éléments...

A priori, les tableaux ne sont donc pas pour toi :P

Par contre, pile, file, liste et éventuellement std;;deque s’avéreront sans doute intéressante. Pile, file et liste proposent l'ajout et la suppression en temps constant, alors que deque ne fourni cela que pour les éléments qui se trouve "en fin de collection".

J'aurais même tendance à dire que la file (d'attente) serait sans doute l'idéal étant donné:
- que l'on ajoute les éléments d'un coté
- que l'on retire les éléments de l'autre
- que l'ordre des éléments est maintenu (FIFO)
parce que,tu m'excuseras,mais, quand tu dis

Citation:

Notons que l'ordre de traitement des données n'a pas d'importance, pour peu qu'elles soient toutes bien traitées.

hé ben, j'ai le plus grand mal à te croire :P

Je peux en effet me tromper, mais, généralement, l'ordre d'exécution de différentes fonctions va grandement influer sur le résultat final et il est même possible d'envisager des circonstances où un ordre d'exécution erroné peut carrément empêcher certaines actions d'être entreprises.

Le seul cas où l'ordre pourrait effectivement n'avoir aucune importance, serait que chaque fonction appelée travaille sur des données strictement différentes et sans aucun lien entre elles. C'est envisageable, mais relativement rare :D

Ceci étant dit, je crois que tu fais fausse route en voulant placer tes fonctions en file d'attente.

A mon sens, cela ne résoudra rien, du moins, pour le problème que tu essaye de gérer: si A fait appel à B, que B fait appel à C et que C fait appel à A, tu auras beau mettre tes fonctions en file d'attente, C finira toujours par faire appel à A, quoi qu'il arrive, et la boucle sera bouclée.

Tu aurais intérêt réfléchir à ton problème comme à un cas de récursivité; c'est à dire, en définissant le cas de base: qu'est ce qui pourra faire, dans ma boucle A, B, C, que la "fonction suivante" ne sera pas appelée, et que la boucle s'arrête :question: Ensuite, il faudra tout faire pour "tendre" vers ce cas particulier.

Maintenant, si chaque fonction ne doit jamais être appelée plus d'une (ou de X ) fois (mais est-ce le cas :question: ) tu peux envisager d'avoir un "élément extérieur" qui pourrait s'occuper de "garder une trace" des différentes fonctions qui ont été appelées.

Pour chaque fonction à laquelle tu ferait appel, tu commencerais par vérifier si la fonction a déjà été appelée (aussi souvent qu'elle le pouvait) ou non, et tu n'y ferais appel que... si ce n'est pas le cas.

Seulement, une telle vérification "prendra du temps"... Peut-être pas "énormément", mais sans doute assez pour ressentir une baisse de performances :P

Au final, si j'étais toi, j’achèterais sans doute une grande nappe en papier, et je commencerais à tracer le diagramme d'appel des fonctions dessus: si A appelle B, je tracerais une flèche partant de A allant jusqu'à B.

Une fois que j'aurais ce diagramme, je regarderais où se situent les éventuelles boucles, et je verrais comment je peux faire pour les supprimer ;)
26/04/2018, 20h41
Bousk

Des tableaux utilisés intelligemment peuvent faire l'affaire.
Si tu reserve ton vector avec une taille suffisante, sans être abusive, push dessus depuis plusieurs threads (avec un lock bien sûr), et swap son contenu dans un autre sur le thread qui va faire les opérations, ca te fait une FIFO efficace et un cache-miss limité puisque tableau et tu évites l'inconvénient de retirer un élément en tête, ce qui est le plus gros piège et l'opération la plus lente du vector imo.
26/04/2018, 23h24
Legro

@Bousk

Citation:

push dessus depuis plusieurs threads (avec un lock bien sûr), et swap son contenu dans un autre sur le thread qui va faire les opérations

Très bon, je n'avais pas pensé à avoir recours au multi threading, mais bon le gain n'est peut être pas énorme... A vérifier.

Citation:

ca te fait une FIFO efficace

Vous voulez dire une LIFO, non ?

@Koala01

Citation:

Au final, si j'étais toi, j’achèterais sans doute une grande nappe en papier, et je commencerais à tracer le diagramme d'appel des fonctions dessus: si A appelle B, je tracerais une flèche partant de A allant jusqu'à B.

C'est justement après avoir fait ça (bon, pas sur une nappe, je me suis modestement contenté d'une feuille A4, mais avec les flèches et tout le reste) que je suis arrivé à cette conclusion.
L'idée est que toutes les fonctions travaillent dans le même but, mais en employant des moyens différents, quand l'objectif est d'arriver à un certain résultat.
C'est un programme compliqué à expliciter, mais imaginons l'équivalent dans un jeu : il y a un méchant monstre qu'il faut tuer, on peut le frapper à l'épée, l'étrangler, ou même par exemple bruler l'oxygène de la pièce pour qu'il ne respire plus etc...
Chaque coup infligé a des répercussions directes et indirectes, si par exemple je lui ai donné un coup de poing, à part le coup qui l'affaiblit, sa respiration devient également un peu plus difficile, et si paralellement il ne reste plus assez d'oxygène dans la pièce, cela peut être fatal, ou pas . Ou bien plus subtil, il peut d'ores et déjà ne plus avoir la force de supporter le coup d'épée qu'il avait reçu au tour précédent.
Donc quand dans le "main" un coup lui est donné, tout un engrennage (plus complexe et surtout avec une quantité beaucoup plus grande d'éléments que ce que je viens de décrire) se met en marche. Ce sont les fameuses fonctions qui vont ici calculer si le coup est fatal ou non.
Le principal est la réponse à cette question (coup fatal ou pas), l'ordre de traitement n'importe pas puisque tout est le résultat d'un seul et même coup.
Par contre il faut vite calculer, avant le coup suivant... Et il ne faut pas non plus épuiser la pile dans laquelle les fonctions s'inscrivent les unes derière les autres...

C'est la raison pour laquelle j'ai pensé à cette file d'attente.

Citation:

A mon sens, cela ne résoudra rien, du moins, pour le problème que tu essaye de gérer: si A fait appel à B, que B fait appel à C et que C fait appel à A, tu auras beau mettre tes fonctions en file d'attente, C finira toujours par faire appel à A, quoi qu'il arrive, et la boucle sera bouclée.

C'est à dire que les fonctions ne font plus d'appel direct (et donc automatique), mais inscrivent leur appel dans la liste, et là bas il est plus facile d'installer un "controleur" qui décide si oui ou non donner suite à cet appel, en fonction de ce qui aura déjà été fait.
27/04/2018, 00h06
Bousk

Hmm, si tu n'as pas plusieurs threads, je pense que tu as juste une mauvaise architecture alors..

Citation:

Envoyé par Legro

l'équivalent dans un jeu : il y a un méchant monstre qu'il faut tuer, on peut le frapper à l'épée, l'étrangler, ou même par exemple bruler l'oxygène de la pièce pour qu'il ne respire plus etc...
Chaque coup infligé a des répercussions directes et indirectes, si par exemple je lui ai donné un coup de poing, à part le coup qui l'affaiblit, sa respiration devient également un peu plus difficile, et si paralellement il ne reste plus assez d'oxygène dans la pièce, cela peut être fatal, ou pas . Ou bien plus subtil, il peut d'ores et déjà ne plus avoir la force de supporter le coup d'épée qu'il avait reçu au tour précédent.

Oui mais ce n'est pas le coup d'épée qui déclence la mort par manque d'oxygène.
Le coup d'épée il fait son truc, met à jour l'état du machin, puis tu exécutes la mise à jour de la pièce, puis tu passes à l'application du process de l'oxygène, puis tu vérifies sa mort. Et chaque étape est indépendante, et surtout chaque étape ne déclenche pas l'étape suivante, c'est juste une suite de processus indépendants. Ca évite, entre autre, ton problème initial.
27/04/2018, 17h16
koala01

Citation:

Envoyé par Legro

@Bousk
Vous voulez dire une LIFO, non ?

Tout dépend de l'ordre dans lequel tu traitera les différents éléments :
si tu les traites dans l'ordre "premier arrivés, premiers traités" c'est FIFO, si tu les traites dans l'ordre "dernier arrivé, premier traité", c'est LIFO :D

Citation:

Le principal est la réponse à cette question (coup fatal ou pas), l'ordre de traitement n'importe pas puisque tout est le résultat d'un seul et même coup.

Oui, mais non... Je suis tout à fait d'accord avec Bousk sur ce coup là...: ce n'est pas au coup de poing ou au coup d'épée de décider de virer l'oxygène de la pièce: c'est à ... un sors qui aura cet effet là, et donc, il appartiendra à... celui qui connaît ce sort de l'invoquer...

De plus, mettons que cinq personnes attaquent ton super-méchant en même temps.

Chaque attaque peut être fatale "à elle seule"... ou pas... Et donc, il y a une question qui se pose:

Mettons que la deuxième attaque portée (comprends: prise en compte) soit fatale, que va-t-il se passer au niveau des attaques n° 3, 4 et 5 (celles qui n'ont pas encore été prises en compte) :question: Vont-elles être lancées sur le corps de notre défunt ennemi "parce qu'elles étaient programmées" ou vont-elle "simplement" être annulées, parce que, ben, il est mort, on ne pourra pas le tuer une deuxième fois :question:

Et nous en revenons toujours au même point: la deuxième attaque prise en compte n'a peut-être été fatale que... parce que la première avait déjà fortement (ou du moins: suffisamment) diminué la résistance de l'ennemi. S'il n'y avait eu que la deuxième attaque, elle aurait tout aussi bien pu ne pas être fatale!

Maintenant, je ne fais que suivre la logique de l'exemple que tu me donnes, car je ne suis pas capable de regarder au dessus de ton épaule pour voir dans quelle situation réelle tu te trouves. Peux être que si tu nous expliquais exactement le projet sur lequel tu travailles, nous aurions plus facile à t'orienter vers une solution adéquate ;)

Mais, quelle que soit la manière dont tu tournes les choses, telles que tu nous les as présentées, je reste sur mon point de vue: tu fais fausse route du tout au tout pour l'instant :P