Comme M. Jourdain tu fais de la prose sans le savoir Michel …
Et ne plus avoir accès aux détails d'implémentation c'est l'encapsulation, la base d'un code C propre et aisément testable et maintenable (ce qu'on apprend apparemment plus aux apprenants).
- Edité par White Crow 22 novembre 2021 à 10:46:46
Si c'était une file, ça dépend des définitions, mais en général fifo, il y a une notion d'ajout d'un côté et retrait de l'autre, ce qui n'est pas le cas ici. Par contre on a un parcours.
Alors bon j'appellerais pas ça une file, si c'était moi.
Les "types abstraits" c'est à un niveau, les structures de données pour les implémenter, à un autre. Ne confondons pas usage et implémentation des types abstraits.
- Edité par michelbillaud 24 novembre 2021 à 23:30:12
Si c'était une file, ca dépend des définitions, mais en généra fifo, l i y a une notion d'ajout d'un côté et retrait de l'autre, ce qui n'est pas le cas ici. Par contre on a un parcours.
Les "types abstraits" c'est à un niveau, les structures de données pour les implémenter, à un autre. Ne confondons pas usage et implementation des types abstraits.
- Edité par michelbillaud il y a moins de 30s
Bah que tu appelles ça list_add ou deque_append c'est du pareil au même. Et si tu n'implémentes pas la totalité des primitives ça ne change pas grand chose …
Ce n'est meme pas une bonne base pour faire une dequeue, il faudrait que les cellules aient des pointeurs vers la précédente (chainage aller-retour) pour que le retrait du premier/dernier se fasse facilement en temps constant.
Ça ne me paraît pas une bonne idée d'appeler mobylette un vélo, avec l'idee qu'on pourrait y ajouter un moteur.
- Edité par michelbillaud 22 novembre 2021 à 11:05:28
Ce n'est meme pas une bonne base pour faire une dequeue, il faudrait que les cellules aient des pointeurs vers la précédente (chainage aller-retour) pour que le retrait du premier/dernier se fasse facilement en temps constant.
Ça ne me paraît pas une bonne idée d'appeler mobylette un vélo, avec l'idee qu'on pourrait y ajouter un moteur.
- Edité par michelbillaud il y a moins de 30s
Tu t'égares, …
Si tu l'as fait en le sachant alors c'est dommage d'avoir loupé l'occasion de mettre en avant toute la boîte à outil que nous donne l'algorithmique. Si tu entends un galop tu penses à des chevaux sauf si tu es au Serengeti.
Ici c'est pareil, si tu vois une liste dont l'implémentation permet des manipulations en tête et en queue de liste alors tu penses file ; si tu vois un algo qui utilises une liste mais qui ne fait que dépiler ou empiler tu penses pile …
On n'appelle pas non plus une mob ou un vélo une draisienne sous prétexte qu'on peut les chevaucher et les pousser avec les pieds.
Et quand tu vois un entier, tu penses decomposition en facteurs premiers.
Le but de l'exercice du monsieur, c'est de bidouiller avec les chainages, ce qui lui fait les pieds côté boucles.
L'assommer avec la boîte à outil bien remplie, c'est pas encore le moment.
---
> Ici c'est pareil, si tu vois une liste dont l'implémentation permet des manipulations en tête et en queue de liste alors tu penses file ;
D'une par ce n'est pas le cas, ici, d'autre part la file se pense en terme d'opérations dont on dispose dessus. C'est toute la notion de type de données abstrait Pas celles qu'on pourrait ajouter.
<< En informatique, une file dite aussi file d'attente (en anglais queuea) est une structure de données basée sur le principe « premier entré, premier sorti » ou PEPS, désigné en anglais par l'acronyme FIFO (« first in, first out ») : les premiers éléments ajoutés à la file seront les premiers à en être retirés. (Wikipedia). >>
La liste chainée est une structure de données dont on peut se servir comme base pour les files, mais ce n'est pas une file. Il ne faut pas sur-spécifier. Elle ne satisfait pas le cahier des charges du type abstrait file
<< En informatique, un type abstrait (en anglais, abstract data type ou ADT) est une spécification mathématique1 d'un ensemble de données2 et de l'ensemble des opérations qu'on peut effectuer sur elles. On qualifie d'abstrait ce type de données car il correspond à un cahier des charges qu'une structure de données doit ensuite mettre en œuvre. >>
Quand je vois un ensemble muni d'une opération binaire, j'appelle pas ça un monoïde, mais un groupoïde. Meme si on pourrait imaginer qu'il y ait un élément neutre et que l'opération pourrait être associative.
Pour pile file et tutti quanti, voir Knuth vol1, page 238 et suivantes ;-)
- Edité par michelbillaud 22 novembre 2021 à 12:43:45
houla … désolé d'avoir remarqué que tu utilises une sd de type pile ou file alors que tu considères que ce n'est qu'une «liste pure».
Mais bon … si ta liste est à l'envers à la fin c'est bien parce que c'est une pile que tu manipules … Et tu ne m'enlèveras pas l'idée que si tu ajoute en fin mais que tu peux accéder au début c'est une file ou un deque …
Après c'est comme tu veux … si tu préfères ne pas le dire, on va pas déclencher un wargame
mais tu aurais pu (dû?) en parler, rien que pour que le PO puisse voir les choses un peu autrement ; un peu comme introduire la récursivité lui a apparemment montré autre chose.
ah, "de type pile ou file", voila qui est précis :-) et si on en restait à "structure chainée" ?
Bon, sinon, c'était surtout pour illustrer la manière de parcourir une liste chaînée avec la tournure idiomatique
Cell *current = first;
while (current != NULL) {
Cell *this = current;
current = current -> next;
// faire quelque chose avec "this"
}
qui apparait deux fois et permet de "détacher" les éléments au besoin (par exemple pour les libérer), sans risquer de déréférencer un pointeur vers une cellule libérée, ou dont le next a été altéré.
------
A mon avis, la manière la plus standard d'implémenter, dans les conditions de l'exercice, c'est de construire la liste chainée des éléments à garder (avec pointeurs sur premier et dernier), comme si on avait eu la bonne idée de définir un type List correct.
Pourquoi c'est mieux ? Parce qu'on fait un seul parcours, ce qui a une meilleure influence sur le comportement du cache. Si on veut tenir compte de ce genre de choses.
Il faut aussi retoucher un peu le prototype : puisqu'on fait fait semblant de croire qu'un Cell* est une liste, la fonction qui enlève des trucs modifie la liste, donc c'est plus raisonnable de dire qu'on passe l'adresse du pointeur de début. Et comme ça on se la pète avec un "double pointeur"
void remove_values(Cell **start, int value) {
Cell *first = NULL, // résultat : liste avec pointeurs
*last = NULL; // sur le premier et le dernier
Cell * current = *start;
while (current != NULL) {
Cell *this = current;
current = current -> next;
if (this -> value == value) {
free(this); // on jette
} else {
this -> next = NULL; // on ajoute dans la liste des résultats
if (first == NULL) {
first = this;
} else {
last->next = this;
}
last = this;
}
}
*start = first;
}
J'imagine que quelqu'un a déjà donné ici cette solution, qui est on ne peut plus standard (la flemme de vérifier).
Les deux algos ont le même principe général, on fait une boucle et on met de côté les éléments qu'on veut garder dans une liste chaînée, et on balance les autres.
Sauf que l'ajout en tête n'est pas la solution idéale, parce qu'il faut repasser derrière pour remettre dans l'ordre voulu. Ce qui crée un problème auxiliaire, traité par une seconde boucle. Un rafistolage.
C'est plus intéressant de faire apparaître le pointeur sur le dernier élément pour ajouter directement à la fin, et donc construire directement le résultat dans le bon ordre.
- Edité par michelbillaud 22 novembre 2021 à 20:05:13
L'ajout à la fin a un autre avantage. La manipulation est minimale. On met le pointeur ssuivant du dernier déjà ajouté vers le nouveau, mais on se fiche du pointeur du nouveau. Et le nouveau devient le dernier. À la toute fin, on met ce pointeur à NULL.
Le Tout est souvent plus grand que la somme de ses parties.
Le coeur de l'algo, c'est parcourir et mettre de côté les trucs à garder.
Les mettre dans un truc qui ressemble à une pile dont il faut encore extraire le contenu c'est une maladresse.
Certes c'est mieux qu'utiliser une liste avec à chaque fois parcours pour ajouter a la fin. Mais ça peut être une étape pour se décider à trouver un moyen d'ajouter directement à la fin.
Le coeur de l'algo, c'est parcourir et mettre de côté les trucs à garder.
Les mettre dans un truc qui ressemble à une pile dont il faut encore extraire le contenu c'est une maladresse.
[...]
Pourquoi une maladresse ?
C'est juste un algo que tu as proposé. Mais si on s'en fout de l'ordre, il n'y a pas besoin de faire un reverse de la pile. Tu la laisse telle quelle et hop le tour est joué, de façon élégante. C'est effectivement l'algo classique de base quand on travaille avec des piles.
Le tout est de savoir qu'il existe, que l'on peut voir le problème de cette manière, etc … tout comme il est intéressant de rappeler la version récursive classique …
Absolument rien ne dit qu'on se fout de l'ordre. Avec des si.
C'est une maladresse parce qu'il y a une solution plus directe qui demande moins de travail. Si il y a un choix d'utiliser une pile pour faire le stockage des trucs à garder "parce que c'est plus simple'", et bien c'est un choix basé sur une mauvaise idée. (Mais à ce stade, l'apprenant n'en n'est pas à manipuler les listes avec suffisamment d'abstraction pour penser en terme de pile. Pour lui c'est des allocations et des pointeurs).
Pourquoi je l'ai montré alors ? Ben, c'est un truc que j'ai vu une fois, dans un paquet d'exercices à corriger. Ca m'est revenu. Probablement que l'étudiant qui m'a sorti ça avait été influencé par un exercice débile "comment faire pour transférer le contenu d'une pile p1 dans une autre p2 : spoiler = passer par une troisième". Ce genre d'exercice - qui ne sert à rien sinon à tripoter des piles - est dangereux, il donne des idées tordues, en plus de ne pas montrer à quoi servent vraiment les piles. En plus, pourquoi on fait pas p2 = p1 ? :-)
- Edité par michelbillaud 24 novembre 2021 à 23:43:31
Absolument rien ne dit qu'on se fout de l'ordre. Avec des si.
[...]
tout comme rien n'oblige à le préserver … pas la peine de faire un surplus inutile de travail lorsqu'on est arrivé à la solution
michelbillaud a écrit:
>[...] Probablement que l'étudiant qui m'a sorti ça avait été influencé par un exercice débile "comment faire pour transférer le contenu d'une pile p1 dans une autre p2 : spoiler = passer par une troisième". Ce genre d'exercice - qui ne sert à rien sinon à tripoter de piles - est dangereux, il donne des idées tordues. En plus, pourquoi on fait pas p2 = p1 ? :-)
Parce qu'il faut différencier l'algo et l'implémentation … et que d'avoir une vue un peu plus globale ne fait jamais de mal. Ne vaut-il donc pas mieux disposer de plusieurs angles d'approches en algo plutôt qu'une vision étriquée centrée sur le code C ?
Bon, tu as une vision orientée TP où tout est bien fixé (enfin normalement et du coup les solutions à la «baromètre de Bohr» sont considérées comme déviantes de la norme attendue) pour vérifier qu'un arc n'a qu'une corde. Mais bon, dans la vie pro c'est un atout que d'avoir plusieurs cordes à son arc … pour choisir la bonne, ou la moins mauvaise à défaut.
Edit sur l'edit de Michel :
Un apprenant qui n'arrive pas à lier les différentes connaissances entre différents cours suit sans doute une formation où les prof portent des œillères. Je ne suis pas un dinosaure, mais je me souviens qu'il était toujours de bon ton, lorsque je poursuivais mes études en fac, d'utiliser toute l'étendue de ce qu'on nous apprenait. On ne rendait pas un projet C sans avoir une modélisation, sans expliquer les choix des algos, etc. Sinon à quoi ça sert ?
- Edité par White Crow 24 novembre 2021 à 23:52:54
Là il n s''agissait de projets (dont il faut décrire la structure et l'idee de la realisation), mais de simples exercices de fin de séance "Et puis pour la semaine prochaine vous ferez aussi une fonction qui fait ceci, et une autre qui fait cela" Donc juste le code, ca suffit.
La solution produit le résultat attendu, avec la complexité asymptotique attendue (linéaire), donc c'était acceptable. L'impact sur les caches de faire deux parcours n'est pas pris en consideration.
Donc une vision tp parce que c'était des tp.
Par contre une solution plus simple etait à portée de main. Réfléchir avant de coder la première idée qui passe par la tête. Et penser à celui qui se gratter la tête en se demandant si il y avait vraiment une bonne raison de ne pas choisir la solution la plus simple.
- Edité par michelbillaud 25 novembre 2021 à 7:45:22
La simplicité a cette vertu qu'elle n'est pas simplement définissable lol
Bref, là où nous nous rejoignons est qu'il est important dans le cadre du forum de proposer plusieurs solutions (lorsque le sujet et le PO s'y prêtent) et qu'il est également important de parler un tout petit peu d'algo (mon interprétation de ton «Réfléchir avant de coder la première idée qui passe par la tête.»).
C'est pour ça que je l'ai montrée, avec les critiques qu'on peut en faire
> Simplicité non définissable
On peut toujours définir des métriques, Le Monde Professionnel Se Les Arrache, ça vaut ce que ça vaut.
Genre formule de perlimpinpin avec profondeur d'imbrication, longueur du code, etc.
Je regarde pour mes contributions
- 21/11 (récursive): 13 lignes, un if contenant un appel récursif et un autre if
- 21/11 ("pile") : 24 lignes : while/if + while
- 22/11 ("avec pointeur sur le dernier") : while/if/if , 22 lignes
la simplicité, un indicateur, c'est le nombre de lignes qu'on évite d'écrire pour contourner un petit problème qui se pose à cause d'un choix un peu prématuré.
Un autre point à voir, c'est le type de sujet, qui peut être
- à partir des opérations primitives machin truc sur la structure de données, écrire une fonction ceci-cela
- à partir des pointeurs et machins, définir directement une opération supplémentaire sur le type de données (sans faire appel aux autres opérations).
Les deux exercices ont leur mérite, à des moments différents de l'apprentissage. Et il s'y ajoute "on a fréquemment besoin d'une opération supplémentaire, que faut il changer'. Par exemple, si on a besoin de connaitre la longueur d'une liste, on stocke un compteur qu'on met à jour lors des ajouts/retraits. On n'écrit pas un parcours avec compteur :-)
- Edité par michelbillaud 25 novembre 2021 à 11:41:55
Tu sais, tu parles de simplicité et je ne sais pas de quelle simplicité tu parles …
Je parle souvent d'algo car je pense que c'est le point essentiel qu'il manque à la grande majorité des primopostants ici … tout comme leur manque essentiel de la compréhension du fait qu'il faut impérativement bien définir ses sd et toutes les primitives dont on peut avoir besoin …
effectivement je comprends mieux maintenant ton «non c'est pas une pile». Tu ne voyais que le coté «à partir de pointeiurs et machins …» ; j'essayais tant bien que mal d'aller un poil au-dessus.
C'est pas du tout que je ne vois que le côté pointeurs. Evidemment, si tu crois ça au départ, c'est normal que tu ne comprenne pas.
C'est que cet exercice est toujours donné dans le contexte de l'apprentissage de la manipulation des pointeurs et - plus généralement - de la réalisation de certaines structures de données classiques, pas celui du bon choix ou du bon usage des structures des données abstraites pré-définies (dont les opérations primitives sonbt posés au départ) pour faire quelque chose d'utile (comme analyser des expressions, parcourir des arbres, etc).
Voyons, si c'était le cas, ça ne parlerait pas du tout de pointeur, qui sont un détail de réalisation.
Enfin on peut espérer, quoi qu'on puisse avoir des doutes vu la "qualité" générale des cours du type "apprenez à programmer avec C" :-(
- Edité par michelbillaud 25 novembre 2021 à 15:35:36
C'est pas du tout que je ne vois que le côté pointeurs. Evidemment, si tu crois ça au départ, c'est normal que tu ne comprenne pas.
C'est que cet exercice est toujours donné dans le contexte de l'apprentissage de la manipulation des pointeurs et - plus généralement - de la réalisation de certaines structures de données classiques, pas celui du bon choix ou du bon usage des structures des données abstraites pré-définies (dont les opérations primitives sonbt posés au départ) pour faire quelque chose d'utile (comme analyser des expressions, parcourir des arbres, etc).
Voyons, si c'était le cas, ça ne parlerait pas du tout de pointeur, qui sont un détail de réalisation.
Enfin on peut espérer, quoi qu'on puisse avoir des doutes vu la "qualité" générale des cours du type "apprenez à programmer avec C" :-(
- Edité par michelbillaud il y a environ 1 heure
Ah ebn c'est toi le prof hein
Que ton cours soit meilleur je n'en doute pas un instant.
Je ne suis plus, les meilleures choses ayant une fin.
> Que ton cours soit meilleur
Je ne fais pas de cours "apprenez à programmer avec C" (*), chose qui conduit, sinon à la catastrophe, au moins à un usage sous-optimal du temps de formation pour des gens qui voudraient apprendre à programmer. Y compris en C, à terme. Notamment par ce que ça focalise les gens (à cause l'absence de conteneurs, par exemple - ou de chaînes) sur des détails techniques de bas niveau (**), au lieu de s'intéresser à la conception générale des programmes et des algorithmes. Certes il faut faire les deux (c'est pour ça qu'il y a des exercices sur les chaînages) mais les détails, c'est des détails.
(*) ce qui est différent de "apprenez C maintenant que vous savez un peu programmer."
(**) typiquement, on va reconnaître le C enseigné par des électroniciens/physiciens au fait que leurs élèves débarquent ici avec des types de données à la noix (unsigned char etc) pour représenter des entiers, au lieu d'écrire un bout de code qui a un sens, ou de décomposer leur truc en fonctions au lieu de tout coller dans le main.
Encore cet après midi, j'ai vu un support de cours C qui raconte qu'une pile chaînée c'est forcément plus efficace qu'une chaine dans un tableau alloué dynamiquement "parce que ça coûte cher d'ajouter un élément". #facepalm Ben Dugenou, faut allouer plus d'un élément quand ça déborde, stratégie de doublement etc...
- Edité par michelbillaud 25 novembre 2021 à 18:07:22
Je ne suis plus, les meilleures choses ayant une fin.
> Que ton cours soit meilleur
Je ne fais pas de cours "apprenez à programmer avec C" (*), chose qui conduit, sinon à la catastrophe, au moins à un usage sous-optimal du temps de formation pour des gens qui voudraient apprendre à programmer. Y compris en C, à terme.
(*) ce qui est différent de "apprenez C maintenant que vous savez un peu programmer."
J'ai peut être pas dit assez clairement qu'un cours de C pour apprendre la programmation me paraissait une idée pourrave, et quand j'y crois pas, je fais pas. That's it.
Ca serait à peu près pareil que de commencer la programmation par l'assembleur (un truc que j'aimais bien enseigner, mais qui n'a aucune chance de marcher correctement avec un public qui n'a pas déjà une idée claire de ce qu'est une boucle, un test, un sous-programme etc).
- Edité par michelbillaud 25 novembre 2021 à 22:05:52
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.