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

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:

---

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); }

---

Bonjour,

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

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

Code:

---

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.

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:

---

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)

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

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.

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.

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:

---

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:

---

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)

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:

---

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).

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:

---

1 2 3 4 5

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

---

mon compilateur plante dans ce cas là.

Je parlais par exemple de ça :

Code:

---

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 ;)

Citation:

---

Envoyé par takout

Code:

---

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à :mouarf:.
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:

---

int p_temp[2];

---

Citation:

---

Envoyé par olivier_u

A mon avis, tous les compilateurs du monde plantent dans ce cas-là :mouarf:.
L'allocation statique, en C, ne peut être faite qu'avec des constantes.

---

Depuis la norme C99 on peut déclarer un tableau avec un entier calculé lors de l'exécution du programme