Optimiser une liste chainee lente

Quelqu'un pourrait-il m'aider à optimiser ce bout de code, je ne comprends pas pourquoi il est si lent à l'exécution:

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 27 28 29 30 31 32 33 34 35 36 37 38

#include <stdio.h> #include <string.h> #include <stdlib.h>   struct node { char *data; int i; struct node *next; };   static struct node *new(char *elt) { struct node *n = (struct node *) malloc(sizeof(struct node)); n->data = elt; n->i = 0; n->next = NULL; return n; }   static void print(struct node *n) { fprintf(stdout, "%p %s\n", n->next, n->data); }   static struct node *append(struct node *n, char *elt) { for(; n->next != NULL; n = n->next); n->next = new(elt); return n; }   int main(void) { int i = 0; struct node *n = new(NULL); while(i++ < 100000) { print(append(n, "sring")); } return 0; }

---

/* 0.171u 0.019s 0:00.24 75.0% 0+0k 0+0io 0pf+0w */

Des solutions?

Le programme tourne en 33s chez moi. Si je ne fais pas l'affichage, le programme s'exécute en 17s. Les printf() sont très couteux.

Je pense que tu devrais changer tes char* en const char*, vu l'utilisation que tu en as. Il y a d'ailleurs un warning dans le main. Sinon, il serait plus logique de faire un malloc() pour le champ data dans new, et de copier la chaine passée en paramètre dedans.

Bonjour,

Ce qui est très couteux est l'append. Tu reparcours toute la liste pour en trouver la fin. Une optimisation serait de créer une structure liste qui se souvienne du dernier noeud :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

struct node { char *data; int i; struct node *next; };   struct list { struct node* head; struct node* tail; }

---

Lors de l'append tu sais directement où insérer ton neud sans avoir à parcourir toute la liste ....
Il faudra évidemment créer les fonction d'accès à struct list, VÉRIFIER les retour de malloc, etc ...

Pour info, quand tu cherches à optimiser un code tu as des profiler. Par exemple avec gcc tu as l'outil gprof.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

$> gcc -pg -o list list.c $> ./list .... .... .... $> gprof list Flat profile:   Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls us/call us/call name 100.98 29.34 29.34 100000 293.43 293.43 append 0.03 29.35 0.01 main 0.00 29.35 0.00 100001 0.00 0.00 new 0.00 29.35 0.00 100000 0.00 0.00 print

---

Tu trouveras toutes les infos grâce à google.

Bon alors je croyais qu'en ajoutant un pointeur local (*last_pos) dans la fonction append le problème serait résolu, car il me permettrait de tenir la structure de base simple tout en réduisant le temps d'itération... Kwariz y voit une source d'erreur grossière! merci à lui de nous éclairer une fois de plus! :P

Cela peut être une source d'erreur simplement car d'autres fonctions peuvent modifier la position de la fin de la liste. Un delete de la dernière position et ton pointeur global devient invalide d'où un risque de plantage, par exemple.

Cela fait longtemps que j'utilise des listes simplement ou doublement chaînées. Ce que j'implémente, c'est UNE fonction qui append, et UNE fonction qui delete (qui sont en général dans un module séparé)

Bien sur, cela impose:
- soit d'avoir les pointeurs first et last en global (pas joli pour les puristes)
- soit de les passer (par adresse) à toutes les fonctions susceptibles d'insérer/supprimer un élément de la liste (pas toujours pratique)

Pour moi, les deux options se valent suivant la complexité de l'application.

La solution proposée par kwariz est simple, propre et efficace.

Elle a de plus l'avantage de différentier la représentation de la liste de celle d'un noeud de la liste ce qui clarifie beaucoup l'écriture et la lecture du code.