Discussion :

[Stillbogus]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

[Bktero]

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.

[kwariz]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Stillbogus]

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!

[kwariz]

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.

[edgarjacobs]

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.