optimisation d'une file fifo

Version imprimable

Bonjour à tous,

j'ai implémenté une fonction qui ajoute un élément dans une file, j'aimerais optimiser cette fonction mais je ne sais pas comment le faire.
Pouvez vous m'aidez s'il vous plaît ?

voici ma fonction :

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
39
40
 
typedef int bool;
#define False 0
#define True  1
 
typedef struct Fifo
{
    int *donnee;
    struct Fifo *suivant;
} Fifo;
 
void fifo_add( Fifo **p_fifo, int *val)
{
  Fifo *new_fifo, *p_courant;
 
  /* on créer un nouvel élément de la file */
  new_fifo=Malloc(1,Fifo);
  assert(new_fifo != NULL); 
 
  /* on fait pointer l'élément vers null */
  new_fifo->suivant=NULL;
 
  /* on assigne aà l'élément la donné que l'on veut ajouter*/
  new_fifo->donnee=val;
  /* si la file est vide, alors on fait pointer la file vers l'élément que l'on vient de créer */
  if(fifo_isempty(*p_fifo))
  { 
   *p_fifo=new_fifo;
  }
  else
  {
     p_courant=*p_fifo;
    while(p_courant->suivant!=NULL)
    {
      p_courant=p_courant->suivant;
    }
     p_courant->suivant=new_fifo;
  }
return;  
}

Cordialement,
Takout

31/05/2012, 16h13
Bousk

Bonjour,

si tu ne vois pas comment le faire, peut-être est-ce parce que tu ne peux pas. :mrgreen:
Une liste, si tu ne possèdes que son élément de tête à manipuler, tu n'as pas grand choix : tu parcours chaque élément jusqu'à arriver en fin de file et ajouter le nouveau.
Soit ce que tu fais.;)

Par contre, pourquoi utiliser un int* en données ? Fourni par l'utilisateur qui plus est : risque de passer un pointeur qui causera un crash parce que libéré entre temps.
Et le return à la fin est inutile.

Pour ta file, tu peux avoir deux pointeur : l'un sur le début de la file et l'autre sur la fin pour éviter de devoir parcours l'ensemble de ta file à chaque insertion.

Si tu n'as qu'un seul pointeur tu peux remplacer :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 if(fifo_isempty(*p_fifo)) { *p_fifo=new_fifo; } else { p_courant=*p_fifo; while(p_courant->suivant!=NULL) { p_courant=p_courant->suivant; } p_courant->suivant=new_fifo; }
Par :
Code:

1 2 3 4 5 6 7 Fifo ** p_courant= p_fifo; while(fifo_isempty(*p_courant)) { p_courant = &(*p_courant)->suivant; } *p_courant = new_fifo;
En gros tu fait un parcours indirect, ainsi tu parcours toute ta liste indépendamment du fait que le maillon soit premier ou non.
Par contre je me suis peut-être trompé dans l'écriture à vérifier tout de même.

31/05/2012, 16h24
takout

Le int * c'est parce que j'utilise des tableaux en valeur dans ma file.
Le reurn c'est par habitude on m'a toujours appris qu'une fonction doit retourner quelques choses.

Neckara je pense que ta solution peut me faire gagner du temps.
31/05/2012, 16h32
Neckara

Disons qu'avec 2 pointeurs, tu ne rajoute qu'une affectation lors de l'insertion et pour toutes les autres opérations, tu n'as aucune ou pratiquement aucune modification.

Avec 1 seul pointeur tu as un parcours complet de la liste (donc plusieurs affectations etc...). Si ta liste est grande on va dire 10 000 maillons, la différence va se faire sentir.

Après, tu peux utiliser une liste simplement chaînée ou doublement chaînée.
La liste doublement chaînée simplifiera l’algorithme des insertions suppressions et te permettra aussi de parcourir ta liste en sens inverse.
Mais si tu utilise une file, je suppose que tu ne fait que des insertions en queue et suppression en tête, dans ce cas là avoir des maillons doublement chaîné ne sert pas trop.

J'y pense que maintenant mais tu peux aussi avoir qu'un seul pointeur et utiliser une file circulaire.
Ton pointeur (= ta liste) pointerais sur le dernier élément et le dernier élément pointe sur le premier élément.
31/05/2012, 16h33
Bousk

Citation:

Envoyé par takout

Le reurn c'est par habitude on m'a toujours appris qu'une fonction doit retourner quelques choses.

Une fonction qui retourne void ne retourne.. rien.
return sert à sortir de la fonction.
Quand le programme rencontre l'accolade fermante, il sort de la fonction.
31/05/2012, 16h38
Neckara

On met le return si un jour on veut éventuellement changer le type de retour de la fonction (mettre un booléen par exemple) pour voir très rapidement où mettre la valeur de retour et pour ne pas a avoir à réécrire le 'return' ?

De toute façon mettre return; ne coûte rien et ce n'est en soit pas faux, je pense que c'est plus une raison de lisibilité du code qu'autre chose, même si je ne vois pas vraiment l'utilité d'écrire le return.

Voilà j'ai fais ajout d'un élément avec deux pointeurs :

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
 
 
void fifo_add( Fifo **p_fifo,Fifo **fin,int *val)
{
  Fifo *new_fifo;
 
  /* on créer un nouvel élément de la file */
  new_fifo=Malloc(1,Fifo);
  assert(new_fifo != NULL); 
 
  /* on fait pointer l'élément vers null */
  new_fifo->suivant=NULL;
 
  /* on assigne aà l'élément la donné que l'on veut ajouter*/
  new_fifo->donnee=val;
  /* si la file est vide, alors on fait pointer la file vers l'élément que l'on vient de créer */
  if(fifo_isempty(*p_fifo))
  { 
   *p_fifo=new_fifo;
   *fin=new_fifo; 
  }
  else
  {
     (*fin)->suivant=new_fifo;
     *fin=new_fifo;
  }
return;  
}

On préfèrera souvent faire ceci :

Code:

1
2
3
4
5
6
 
  if(fifo_isempty(*p_fifo))
      *p_fifo=new_fifo;
  else
       (*fin)->suivant=new_fifo;
*fin=new_fifo;

31/05/2012, 20h15
takout

oui c'est vrai c'est plus clair.
01/06/2012, 13h31
matafan

La plus grosse optimisation est celle que t'as donné Neckara.

Après, si fais de nombreuses insertion, il peut aussi être intéressant d'éviter de faire un malloc() à chaque fois en allouant tout un bloc d'éléments en une fois. Lors d'une insertion, tu regardes si tu as déjà un élément alloué. Si c'est le cas, tu l'utilises. Sinon, tu alloues, mettons, un bloc de 100 éléments.
05/06/2012, 10h32
olivier_u

Citation:

Envoyé par Neckara

De toute façon mettre return; ne coûte rien et ce n'est en soit pas faux, je pense que c'est plus une raison de lisibilité du code qu'autre chose, même si je ne vois pas vraiment l'utilité d'écrire le return.

Dans certains projets, c'est demandé explicitement en tant que règle de codage.