recherche dans un tableau des indices d'un élément

**takout** · 30/05/2012, 16h08

Bonjour à tous,
J'ai écrit un programme qui recherches des éléments dans un tableau à deux dimensions par ordre croissant. Puis qui range les indices associés dans une file fifo. Mon souci c'est que l'algorithme que j'utilise parcours tout le tableau, il est de fait très lent.
Quelqu'un aurait t-il une autre idée d'algo plus rapide ?
J'ai mis une illustration de mon algorithme ci dessous :

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
39
 
 
  int main()
  {
   register  unsigned int i,j,k; 
   int nrow=4,ncol=4;
   unsigned int size_tab=nrow*ncol,size_tri;
   int *p_temp=NULL,p[2];
   double *tri=NULL,tab[4][4]={{1,2,4,6},{9,1,8,6},{3,2,1,5},{5,6,7,8}};
   Fifo *file;
 
 
  /* ranger les element du tableau dans un vecteur */
  tri=Malloc(size_I,double);assert(tri!=NULL);
  file=fifo_empty(); /*initialisation de la file */
 
 
   /* trier les éléments du vecteur par ordre croissant puis enlever les doublons */
   quicksort(tri,0,size_I-1);
   size_tri=suprime_doublon(tri,size_tab); /* tri est sans doublons */
 
 
   /* Parcour et recherche dans le tableau */
    for(k=0;k<size_tri;++k){ 
 
    	for(i=0;i<nrow;++i){
    	for(j=0;j<ncol;++j){   	
    	if(tab[i][j]==tri[k]){
 
 
    	   p[0]=i;p[1]=j; /* coordonnee du pixel courant */ 	  
   	   p_temp=Malloc(2,int);
      	   p_temp[0]=p[0]; p_temp[1]=p[1];
 	   fifo_add(&file,p_temp);
 
 	   }}}
   }   	 		
  return(1);	 
 }

**pythéas** · 30/05/2012, 17h20

Bonjour,

vu que tu fais un tri dichotomique, pourquoi ne pas faire une recherche dichotomique?

**Trademark** · 30/05/2012, 17h22

Une meilleure solution est d'utiliser une structure de la forme :

Code :

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

1
2
3
4
5
6
7
8
9
10
typedef struct
{
  int x,y;
} position;
 
typedef struct
{
  int value;
  position pos;
} data;

Tu passes à quicksort une fonction de comparaison pour pouvoir comparer des structures de type data (sur l'élément value).

Ensuite en fonction de ce que tu veux faire, ton tableau trié sera ta file. En effet à l'indice 0 se trouve l'élément qui va sortir. A l'indice size-1 se trouve l'élément qui vient de rentrer. Maintenant il faut voir l'usage que tu fais de cette file.

**takout** · 30/05/2012, 17h35

En fait, j'ai pensé à la recherche dichotomique mais le problème c'est que je veux conserver les indices des éléments et j'ai en plus beaucoup de doublons dans mon tableau.

Ça peut être une bonne idée d'utiliser un tableau de structure, mais après je veux rechercher des éléments dans ce tableau le plus rapidement possible. Par exemple trouver les indices de tous les éléments qui ont la valeur 13 et les mettre dans la file. Cette file me sert après pour modifier un autre tableau.

voici ce que je fais après avoir mise dans ma file tous les éléments qui ont la valeur 13 :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
 int nbre_element_13;
int tableau2[4][4];
compte=1;
 
for(i=0;i<nbre_element_13;++i)
{    p=fifo_delete(&file);
      tableau2[p[0]][p[1]]=compte;
}
compte++;

après je recommence pour que par exemple à la valeur 14 tableau2 aux indices associés sera égale à 2. (si l'élément le plus petit est 13)

**Neckara** · 30/05/2012, 17h47

Dans ta structure tu peux enregistrer la position initiale avant de trier tes éléments.

**Trademark** · 30/05/2012, 18h24

Je ne sais pas si c'est un exercice ou pour le travail, mais ne peux-tu pas nous donner un énoncé pour qu'on s'y retrouve dans tout ce cirque ? Il se peut qu'une solution plus élégante soit possible.

**takout** · 30/05/2012, 20h28

Ce n'est pas un exercice, c'est pour en quelque sortes pour ma culture générale car je ne suis pas informaticien.
J'ai implémenté l'algorithme watershed de vincent et soille. Mon code fonctionne mais je cherche à l'optimiser.
Voici un lien sur le pseudo code :
http://www.google.com/url?sa=t&rct=j...tGCmCw&cad=rja
L'algorithme que j'ai codé est celui du paragraphe 4.1, je cherche une manière élégante de codé les lignes 13 à 18.

**Neckara** · 30/05/2012, 21h36

Je ne comprend pas tout ce que tu veux faire.

Je pense que tu pourrais utiliser une liste de liste.

La première liste contiendrait des maillons qui auraient pour information la valeur (13 par exemple). Tu insèreras chaque élément en triant sur la valeur (Sinon au lieu de faire une liste, tu peux faire un tableau contenant (max -min) cases ).

Code :

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

1
2
3
4
5
6
7
8
9
 
 
typedef struct maillon
{
        maillon * suivant;
        maillon * precedant;
        Contenu liste;
        int valeur;
} Maillon

Ensuite, si il te faut que la valeur, Contenu sera un int que tu incrémentera/décrémentera.

Si tu as besoin d'autres information, Contenu sera une pile.

Code :

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

1
2
3
4
5
6
 
typedef struct m
{
          struct m * suivant;
          maStruct * informations;
}M, * Contenu;

Si tu fait un tableau de pile :
Accès : O(1)
Suppression : O(1) (ou Accès 2 en O(nlogn) si tu veux supprimer un élément spécifique)
Insersion : O(1)
Ajout d'une valeur maximale : nécessite un realloc, le reste étant une insersion en O(1)
Diminution de la valeur minimale : nécessite un realloc ainsi que le déplacement de tout le tableau

Si tu fait une liste doublement chaînée de pile :
Accès : O(nlogn) -si je ne dit pas de bêtises-
Suppression : Accès (ou Accès + Accès2 si tu veux supprimer un élément spécifique)
Insertion : Accès

Diminution de la valeur minimale : O(1)
Augmentation de la valeur maximale : O(1)

**Trademark** · 31/05/2012, 09h02

Comme dit dans le papier, cette algorithme doit fonctionner en O(n) où n est le nombre de pixels, par conséquent être très rapide. (Bien que le tri soit forcément en O(nlog(n)), mais passons).

Toi tu es déjà en O(n²) avec ta triple boucle. Il faut alors que tu stockes, d'une part, les valeurs de gris et la position du pixel avec la structure que je t'avais conseillé, et d'autre part, garder ton tableau à 2 dimensions (que tu peux coucher pour n'avoir plus qu'une dimension).

Ainsi la première partie de l'algo pourrait être traduite comme ça:

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
int pixel[n];
int lab[n];
int dist[n];
int im[n]
 
int h[n]; // contient les indices des pixels trié par niveau de gris.
 
// Mettre pixel dans h mais trié sur les valeurs de gris (du plus petit au plus grand).
// ...
// NOTE : il ne faut pas supprimer les doublons ...
 
for(int i=0; i < n; ) 
{
  int grey_value = pixels[h[i]];
  for(; pixels[h[i]] == grey_value; ++i)
  {
    lab[h[i]] = MASK
    for(int j = 0; j < 4; ++j) // les voisins
    {
       // Tu peux accéder en temps constants aux voisins car ils sont implicites, il y en a maximum 4, faire attention à ne pas sortir de "l'image".
    }
  }
}

Et si tu veux que ça soit plus rapide, il faut arrêter d'utiliser des malloc partout. Une allocation mémoire coûte chère ! (Et en plus tu as des fuites mémoires car tu ne fais pas de free).

**takout** · 31/05/2012, 10h31

Je vous remercie, ça me parrait une bonne idée je vais essayer votre méthode Trademark.

Pour l'allocation dynamique j'y suis un peu obligé car je ne connais pas à l'avance la taille des images. Et même si j'avais un moyen de l'obtenir
je ne pourrais pas définir mon tableau de cette manière :

Code :

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

1
2
3
4
5
 
 
void toto(int nrow, int ncol){
 int image[nrow][ncol];
}

mon compilateur plante dans ce cas là.

**Trademark** · 31/05/2012, 13h51

Je parlais par exemple de ça :

Code :

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

 p_temp=Malloc(2,int);

Et pour ce qui est de l'algo, tu devrais peut-être suivre plus à la lettre le pseudo-code décrit

**olivier_u** · 05/06/2012, 11h27

Envoyé par takout

Code :

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

1
2
3
void toto(int nrow, int ncol){
 int image[nrow][ncol];
}

mon compilateur plante dans ce cas là.

A mon avis, tous les compilateurs du monde plantent dans ce cas-là

.
L'allocation statique, en C, ne peut être faite qu'avec des constantes.
Dans cet ordre d'idée, l'exemple que te montre Trademark peut se remplacer facilement par une déclaration :

Code :

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