Discussion :

[takout]

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]

Bonjour,

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

[Trademark]

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]

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]

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

[Trademark]

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]

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.