tri d'une liste chainee

Salut a tous,

jessaye de trier une liste chainee avec ce code

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

int sort_in_list(t_list *begin) { char *str; t_list *i; t_list *j; t_list *b;   i = begin; while(i->next != 0) { j = begin; while (j->next != 0) { if (my_strcmp(j->next->data, j->data) < 0) { str =j->data; j->data = j->next->data; j->next->data = str; } j = j->next; } i = i->next; } return (0); }

---

le probleme c'est quand jappelle la fonction

Code:

---

1 2	sort_in_list(begin) j->next->data est vide et j->data contient le dernier element inserer dans la liste

---

Dou ma question comment remettre begin a son orirgine

Citation:

---

Envoyé par Pitou5464

le probleme c'est quand jappelle la fonction

Code:

---

1 2	sort_in_list(begin) j->next->data est vide et j->data contient le dernier element inserer dans la liste

---

Dou ma question comment remettre begin a son orirgine

---

Impossible. Il ne fallait pas modifier begin (modifier la valeur d'un paramètre est souvent le signe d'une erreur de codage).

Il faut laisser begin tranquille et utiliser un pointeur local (initialisé avec begin).

En relisant ton code, je vois que tu n'as en fait pas modifié begoin. Alors je ne comprend pas ta question. Tu as su faire une fois

Code:

---

i = begin;

---

et

Code:

---

j = begin;

---

Tu ne peux pas le refaire ?

jai essaye comme ca mais jai toujours un seg fault

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

int sort_in_list(t_list *begin) { char *str; t_list *i; t_list *j; t_list *b;   i = begin; while(i->next != 0) { j = begin; while (j->next != 0) { b = begin; if (my_strcmp(b->next->data, b->data) < 0) { str =b->data; b->data = b->next->data; b->next->data = str; } j = j->next; } i = i->next; } return (0); }

---

Jai l'impression que begin pointe sur le dernier element rentre dans la liste donc c'est normal qu'il n'y ai rien dans j->next->data car j = begin->data contient le dernier element dans la liste.
Que je reintialise un autre pointeur local fera la meme chose non?

Citation:

---

Envoyé par Emmanuel Delahaye

(modifier la valeur d'un paramètre est souvent le signe d'une erreur de codage).

---

Entièrement pas d'accord (mais on reste copains, hein !).

Modifier un paramètre peut être un très bon moyen pour écrire un code concis et souvent très lisible. La quasi entièreté des fonctions de ma librairie AVL, par exemple, sont écrites en modifiant les paramètres, et le résultat est souvent très surprenant en termes d'économie de variables, d'instructions, et d'identificateurs. Mais c'est sûr (et comme beaucoup de choses), si c'est utilisé dans de mauvais contextes, ça peut mener à des erreurs graves.

Citation:

---

Envoyé par InOCamlWeTrust

Modifier un paramètre peut être un très bon moyen pour écrire un code concis et souvent très lisible. La quasi entièreté des fonctions de ma librairie AVL, par exemple, sont écrites en modifiant les paramètres, et le résultat est souvent très surprenant en termes d'économie de variables, d'instructions, et d'identificateurs. Mais c'est sûr (et comme beaucoup de choses), si c'est utilisé dans de mauvais contextes, ça peut mener à des erreurs graves.

---

Si on sait ce qu'on fait, pourquoi pas... Les débutants savent rarement ce qu'ils font...

Oh... il ne faut pas être aussi catégorique non plus ! Il faut bien un jour se lancer et se mouiller un peu !

C'est une "astuce" que mon prof de TP de C m'avait apprise : ce mec sait réellement très bien coder en C. D'après lui, quand on peut s'en sortir en employant les paramètres comme variables, il faut le faire... et je trouve, avec le recul et un peu de pratique, qu'il n'a pas tort.

Citation:

---

(modifier la valeur d'un paramètre est souvent le signe d'une erreur de codage).

---

Dans ce cas particulier, ce ne serait pas une bonne idée de changer la valeur de begin. Mais, en général, quelles sont les raisons qui te poussent à estimer que modifier la valeur d'un paramètre est une erreur de codage?

Les paramètres sont initialisés dès l'appel de la fonction en copiant leur valeur sur la pile et sont ensuite utilisés comme des variables locales. Le seul danger que je vois concerne les effets de bord lorsqu'on modifie la valeur pointée par un pointeur passé en paramètre. Je n'est pas l'expérience pour comprendre quels dangers cela peut entraîner de modifier un paramètre, pourrais-tu donner un exemple?

Thierry

est ce que je pourrai avoir un exemple pour mieux comprendre

Citation:

---

Envoyé par mujigka

Dans ce cas particulier, ce ne serait pas une bonne idée de changer la valeur de begin. Mais, en général, quelles sont les raisons qui te poussent à estimer que modifier la valeur d'un paramètre est une erreur de codage?

Les paramètres sont initialisés dès l'appel de la fonction en copiant leur valeur sur la pile et sont ensuite utilisés comme des variables locales. Le seul danger que je vois concerne les effets de bord lorsqu'on modifie la valeur pointée par un pointeur passé en paramètre. Je n'est pas l'expérience pour comprendre quels dangers cela peut entraîner de modifier un paramètre, pourrais-tu donner un exemple?

---

Déjà, le bon sens. Si on s'est KC le Q pour passer une valeur à la fonction, c'est pas pour la détruire... On vient d'en avoir un exemple frappant.

Il y a aussi le cas des fonctions genre strcpy(), qui retournent la valeur d'un des paramètres. (Le premier qui me dit qu'il suffit de sauvegarder la valeur se prend un coup de pied au Q virtuel).

Ensuite, un débutant croit souvent qu'en modifiant la valeur du paramètre, il va modifier l'original, ce qui est évidemment faux. Une telle tentative est donc une erreur de conception. Un const sur le paramètre protège de ce genre d'erreur.

Une fois le ménage fait, on constate que les cas où changer la valeur d'un paramètre est utile sont rares et doivent être, AMA, clairement justifiés (genre gagner 2 bytes en mémoire... Supair !).

Citation:

---

Envoyé par Emmanuel Delahaye

Une fois le ménage fait, on constate que les cas où changer la valeur d'un paramètre est utile sont rares et doivent être, AMA, clairement justifiés (genre gagner 2 bytes en mémoire... Supair !).

---

Je saisis clairement les dangers, et sur le fond il n'y a pas de problèmes... à ceci près que gagner quelques octets pour une fonction faisant de la récursivité non terminale... c'est gagner tout de même, au bout du compte, pas mal d'espace mémoire car économiser les variables automatiques qui se logent dans la pile peut, au bout de quelques centaines de milliers d'appels récursifs, être intéressant. Mais il y a aussi le gain en lisibilité, surtout pour les fonctions qui sont très courtes.

Citation:

---

Envoyé par InOCamlWeTrust

gagner quelques octets pour une fonction faisant de la récursivité non terminale...

---

La récursivité, c'est le Diable.

Le code d'origine a l'air correct sous réserve que my_strcmp fonctionne correctement et que beginsoit bien en début de la liste. Peut-il y avoir problème avec my_strcmp dans le cas où un des pointeurs passés en argument est malencontreusement NULL ?

Citation:

---

Envoyé par Emmanuel Delahaye

Une fois le ménage fait, on constate que les cas où changer la valeur d'un paramètre est utile sont rares et doivent être, AMA, clairement justifiés

---

Entièrement d'accord.
Question de lisibilité, ah oui, pour une fonction courte c'est clair que déclarer une variable de plus, cela va nous compliquer la vie...

Par contre, chacun son style, je ne le fais jamais par exemple, cela relève généralement de "hack" rapide qu'on fait et après on oublie et on aura des mauvaises surprises plus tard.

Citation:

---

(genre gagner 2 bytes en mémoire... Supair !).

---

Faux dans l'idée que déclarer une variable et s'en servir va forcément changer la facon dont le compilateur va voir le code. Je ne vois pas pourquoi ce code :

Code:

---

1 2 3 4 5 6 7 8 9 10

int myrec(int a) { int b = 4*a+3; if(b>0) return 0; else { myrec(b); } }

---

serait vu différemment que :

Code:

---

1 2 3 4 5 6 7 8 9 10

int myrec(int a) { a = 4*a+3; if(a>0) return 0; else { myrec(a); } }

---

voici ce que j'obtiens :

Citation:

---

$ ls -al
105 Nov 9 14:17 rec1.c
690 Nov 9 2006 rec1.o
101 Nov 9 14:17 rec2.c
690 Nov 9 14:17 rec2.o

---

entre les deux, mon choix est fait.

Jc

Citation:

---

Envoyé par fearyourself

voici ce que j'obtiens

---

Je parlais du code compilé en éxécution, pas du code source (on s'en tape du code source).

Une variable locale en plus, ça peut utiliser quelques bytes en plus dans la mémoire automatique... (ou 0 si elle est en registre...)

Citation:

---

Envoyé par Emmanuel Delahaye

Je parlais du code compilé en éxécution, pas du code source (on s'en tape du code source).

Une variable locale en plus, ça peut utiliser quelques bytes en plus dans la mémoire automatique... (ou 0 si elle est en registre...)

---

Hmm je parlais surtout des .o, les .c cela m'est égal aussi.

Mon point était de dire que le compilateur n'est pas idiot non plus. Les 2 fichiers .o ont la même taille et cela va de soit. Généralement (et surtout en O2 ou O3), en interne, il va réutiliser le registre contenant le paramètre dès que celui-ci n'est plus utile.

Le faire dans le code C ne changera pas grand chose. Donc la question est plus d'ordre esthétique et on ira dans un troll.

Jc

Ensuite, c'est non seulement une question esthétique, mais aussi une question sémantique. Il peut être pertinent (ou paraitre pertinent à quelqu'un, l'auteur en premier) qu'un paramètre soit directement réutilisé:

Code:

---

1 2 3 4 5 6 7 8 9 10

struct dblchn * GetLast(struct dblchn * pElem) { if(pElem==NULL) return NULL; while(pElem->pNext != NULL) { pElem = pElem->pNext; } return pElem; }

---

Dans cette fonction (qui retourne le dernier chaînon d'une liste doublement chaînée), j'aurais pu créer une variable locale pour l'utiliser à la place de pElem dans la boucle, mais quel intéret ?

Edit: Ici, je me demande même si ajouter une variable n'aurait pas nuit à la lisibilité ou à la simplicité du code...

Citation:

---

Envoyé par fearyourself

Hmm je parlais surtout des .o, les .c cela m'est égal aussi.

---

Arf, j'avais pas vu les .o. Normal que ça ne change rien. La mémoire automatique n'apparait pas dans le code !

Citation:

---

Envoyé par Emmanuel Delahaye

Arf, j'avais pas vu les .o. Normal que ça ne change rien. La mémoire automatique n'apparait pas dans le code !

---

Oui mais la taille du .o est la même et il n'y a aucune différence entre les .o donc le code est le même (j'ai vérifié à coup de diff mais je ne l'ai pas mis donc c'est ma faute, je n'ai pas été assez explicite).

Tu ne vas pas me dire que si le code binaire est le même, la mémoire automatique entre les deux versions peut différer, si ? :aie:

Jc

Citation:

---

Envoyé par fearyourself

Oui mais la taille du .o est la même et il n'y a aucune différence entre les .o donc le code est le même (j'ai vérifié à coup de diff mais je ne l'ai pas mis donc c'est ma faute, je n'ai pas été assez explicite).

Tu ne vas pas me dire que si le code binaire est le même, la mémoire automatique entre les deux versions peut différer, si ?

---

Je ne pense pas, mais ça dépend de l'implémentation...

http://fr.wiktionary.org/wiki/botter_en_touche

Attention quand même, dans un .o, il n'y a pas que du code...

Citation:

---

Envoyé par Médinoc

Ensuite, c'est non seulement une question esthétique, mais aussi une question sémantique. Il peut être pertinent (ou paraitre pertinent à quelqu'un, l'auteur en premier) qu'un paramètre soit directement réutilisé:

Code:

---

1 2 3 4 5 6 7 8 9 10

struct dblchn * GetLast(struct dblchn * pElem) { if(pElem==NULL) return NULL; while(pElem->pNext != NULL) { pElem = pElem->pNext; } return pElem; }

---

Dans cette fonction (qui retourne le dernier chaînon d'une liste doublement chaînée), j'aurais pu créer une variable locale pour l'utiliser à la place de pElem dans la boucle, mais quel intéret ?

Edit: Ici, je me demande même si ajouter une variable n'aurait pas nuit à la lisibilité ou à la simplicité du code...

---

Oui mais ma remarque et mon arrivée dans cette discussion est de dire que le compilateur ne verra pas de différence avec ta solution ou la version avec une variable supplémentaire.

Une des premières choses que le compilateur fait est mettre le code en forme SSA. De ce principe, tu peux mettre autant de variables locales ou utiliser les paramètres, si tu fais la même chose, le compilateur devrait générer le même code au final.

Jc

Citation:

---

Envoyé par Emmanuel Delahaye

La récursivité, c'est le Diable.

---

Nous ne sommes pas d'accord sur ce point. La récursivité existe. Le Diable, la preuve en reste encore à faire.

Tu vas me parler de la taille limitée de la pile. En pratique, chaque fois que la pile a explosé sous mes yeux, il y avait un bug qui aurait fait aussi exploser le tas. En fait, avec la taille limitée de la pile, le problème arrivait plus vite. Les seuls cas où j'ai vu des problèmes dus à la taille limitée de la pile, il n'y avait pas de récursivité présente...

Je suis prêt à publier quelques croustillantes fonctions tout récursives qu'il est très difficile de concurrencer en programmant de façon tout impérative en termes de performances (et en termes de lisibilité, oublions !).

De plus, comme le dit Jean-Marc, du moment où le tas est le plus souvent sauvegardé dans la pile, on peut avoir un stack overflow (ou un segfault, tout dépend) sans faire de récursivité... c'est comme ça que je me suis fait baiser l'autre jour parce que j'avais alloué en automatique un tableau de 1 000 000 de int dans le main !

Citation:

---

Une des premières choses que le compilateur fait est mettre le code en forme SSA. De ce principe, tu peux mettre autant de variables locales ou utiliser les paramètres, si tu fais la même chose, le compilateur devrait générer le même code au final.

---

Je ne sais pas ce qu'est la "forme SSA", (l'informatique a tendance à engendrer plus de sigles ésotériques que tout autre discipline de façon que les Béotiens (dont je suis, puisque je ne comprends pas) trouvent le discours abscons,(ce qu'il finit par être effectivement) )mais , en langage Béotien, les paramètres sont des variables locales au même titre que les autres mais qui sont simplement initialisées .

Je ne suis pas sûr que le posteur soit très avancé par ces considérations qui débordent largement du problème qui a motivé sa question

Citation:

---

Envoyé par diogene

Je ne suis pas sûr que le posteur soit très avancé par ces considérations qui débordent largement du problème qui a motivé sa question

---

Lui peut être pas, mais moi je suis plutôt content d'en apprendre un peu ! et rien n'oblige le posteur à lire...

Sinon tu me donnes l'occasion de pester contre les sigles :) Moi aussi ça me saoule quand j'arrive dans une nouvelles boîte d'entre de nouveaux sigles que je dois toujours assimiler et autant je peux comprendre qu'on utilise ça dans un texte, autant je ne comprends pas qu'on utilise des sigles à l'oral (c'est si difficile de dire "procédure stockée" à la place de "PS" ???). Je n'ai pas l'impression que ce soit une tendance informatique, mais que c'est général et que ça fait bon genre voire "in" de connaître 2-3 sigles.

bon je crois que j'ai besoin de dormir. Soyez sage les enfants.

Citation:

---

Envoyé par diogene

Je ne sais pas ce qu'est la "forme SSA", (l'informatique a tendance à engendrer plus de sigles ésotériques que tout autre discipline de façon que les Béotiens (dont je suis, puisque je ne comprends pas) trouvent le discours abscons,(ce qu'il finit par être effectivement) )mais , en langage Béotien, les paramètres sont des variables locales au même titre que les autres mais qui sont simplement initialisées .

Je ne suis pas sûr que le posteur soit très avancé par ces considérations qui débordent largement du problème qui a motivé sa question

---

Désolé, SSA -> Static Single Assignement

En gros une variable ne peut que prendre une valeur.

Donc lorsqu'on écrit :

Code:

---

1 2 3

x = 10 x++;

---

le compilateur le transforme en :

Code:

---

1 2 3

x_0 = 10 x_1 = x_0 + 1

---

Pourquoi ? Parce que c'est plus facile à optimiser.

Jc

Citation:

---

Envoyé par benhoeil

Citation:

---

Envoyé par diogene

Je ne suis pas sûr que le posteur soit très avancé par ces considérations qui débordent largement du problème qui a motivé sa question

---

Lui peut être pas, mais moi je suis plutôt content d'en apprendre un peu ! et rien n'oblige le posteur à lire...

---

En ce qui me concerne aussi, je trouve ce post très intéressant...

Thierry

Citation:

---

Envoyé par fearyourself

Désolé, SSA -> Static Single Assignement

En gros une variable ne peut que prendre une valeur.

---

Une variable n'est assignée qu'a un endroit (si c'est dans une boucle, elle va l'etre plusieurs fois).

Citation:

---

Envoyé par Jean-Marc.Bourguet

Une variable n'est assignée qu'a un endroit (si c'est dans une boucle, elle va l'etre plusieurs fois).

---

Exact, mauvais choix de mots de ma part.

Chaque variable a le droit d'avoir une seule instruction d'affectation.

C'est une des premières passes du compilateur. Cela facilite (voir même permet) aux autres optimisations de fonctionner.

C'est d'ailleurs la raison pourquoi déclarer une variable locale ne change rien au code. Puisque de toute facon, lorsqu'on écrit ceci :

Code:

---

1 2	int b = a * 4;

---

ou directement :

Code:

---

1 2	a = a * 4;

---

le compilateur va de toute facon renommer la variable a en :

Code:

---

a_1 = a_0 * 4;

---

Jc

Citation:

---

Envoyé par fearyourself

C'est une des premières passes du compilateur. Cela facilite (voir même permet) aux autres optimisations de fonctionner.

---

Il y a des optimisations qui sont plus faciles sous cette forme, d'autres qui sont plus faciles sous d'autres formes. Je doute que tous les compilateurs aient exactement le meme comportement en la matiere; je ne suis meme pas sur du tout que tous les compilateurs optimisant utilisent une forme SSA. GCC utilise trois ou quatre formats dont SSA; je ne sais pas dans quel ordre.

Citation:

---

Envoyé par Jean-Marc.Bourguet

Il y a des optimisations qui sont plus faciles sous cette forme, d'autres qui sont plus faciles sous d'autres formes. Je doute que tous les compilateurs aient exactement le meme comportement en la matiere; je ne suis meme pas sur du tout que tous les compilateurs optimisant utilisent une forme SSA. GCC utilise trois ou quatre formats dont SSA; je ne sais pas dans quel ordre.

---

Certes, mais je crois que si on regarde et, ce que j'en sais, cette passe permet juste un renommage des variables ce qui permet de simplifier énormément la complexité des autres passes.

Je suis convaincu qu'il existe des compilateurs qui ne le font pas. Mais généralement, cela facilite énormément les passes du compilateurs (enlever le code inutile par exemple, ou l'allocation des registres).

Enfin, effectivement, cela dépend du compilateur comme toujours, mais un compilateur bien réglé devrait générer le même code pour l'exemple que j'ai donné au-dessus.

Jc

C'est entre autres pour celà que l'on dit que les langages fonctionnels sont plus faciles à optimiser ?

Citation:

---

Envoyé par InOCamlWeTrust

C'est entre autres pour celà que l'on dit que les langages fonctionnels sont plus faciles à optimiser ?

---

L'absence d'effet de bord est aussi un facteur.