[Rapidité]Min et Max de 6 éléments

Bonjour tout le monde,
Dans un algorithme que j'ai, il me faut, pour chaque bloc de 3*3 pixels, déterminer le minimum et le maximum parmi 6 valeurs. Le fait est que je sais le faire, mais je cherche à le faire de manière optimale...
Lorsque l'on souhaite avoir le minimum entre 2 valeurs, on fait, en C, une macro.
Je travaille, en l'occurence, en C++, mais j'aimerais savoir s'il existe un algo optimal pour déterminer le minimum (et le maximum) dans un ensemble de n valeurs ?

Merci d'avance de vos réponses !

Citation:

---

Envoyé par progfou

Bonjour tout le monde,
Dans un algorithme que j'ai, il me faut, pour chaque bloc de 3*3 pixels, déterminer le minimum et le maximum parmi 6 valeurs. Le fait est que je sais le faire, mais je cherche à le faire de manière optimale...
Lorsque l'on souhaite avoir le minimum entre 2 valeurs, on fait, en C, une macro.

---

Ou une fonction, c'est tellement plus propre et pas forcément plus lent.

Citation:

---

Envoyé par progfou

Je travaille, en l'occurence, en C++, mais j'aimerais savoir s'il existe un algo optimal pour déterminer le minimum (et le maximum) dans un ensemble de n valeurs ?

---

Tu n'as pas vraiment le choix dans les algorithmes : il te faut appliquer n fois ton critère de comparaison pour une séquence de n éléments. Puisque tu travailles en C++, regarde donc du côté de min_element (http://dinkumware.com/manuals/?manua...ml#min_element)
Ce n'est pas forcément le plus rapide, mais ça t'évite de ré-inventer la roue.

Citation:

---

Ou une fonction, c'est tellement plus propre et pas forcément plus lent.

---

Pour un Min ou un Max, une macro suffit, ça n'est pas forcement plus "sale ..." ;)

Citation:

---

mais j'aimerais savoir s'il existe un algo optimal pour déterminer le minimum (et le maximum) dans un ensemble de n valeurs ?

---

Soit tu prends la solution toute faite, soit tu le codes toi même. En l'occurence, il faut tester tous les éléments donc tu auras entre 8 et 16 tests :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

soit M ta matrice 3x3 indéxée à partir de 0.   Min <- M[0][0] Max <- M[0][0]   pour i allant de 1 à 8 faire val <- M[ i mod 3 ][ i / 3 ] si ( val < Min ) alors Min <- val sinon si ( val > Max ) alors Max <- val fin si fin si fin pour

---

mod est le reste de la division euclidienne.
/ est la division euclidienne.

Voilà, je ne crois pas que l'on puisse faire mieux ...

Citation:

---

Envoyé par PRomu@ld

Pour un Min ou un Max, une macro suffit, ça n'est pas forcement plus "sale ..." ;)

---

Question de goût. Pour m'être arraché les cheveux sur une erreur de compilation due à une macro pendant plusieurs heures, je préfère les éviter. Si on ne peut vraiment pas utiliser std::min et std::max, je préfère encore faire un

Code:

---

1 2

(a<b)?a:b

---

que mettre une macro.

Citation:

---

Envoyé par PRomu@ld

Code:

---

1 2 3 4 5 6 7 8 9 10

soit M ta matrice 3x3 indéxée à partir de 0.   Min <- M[0][0] Max <- M[0][0]   pour i allant de 1 à 8 faire val <- M[ i mod 3 ][ i / 3 ] <des choses coupées ...> fin pour

---

---

En traitement d'images, on représente très souvent les images (2d ou 3d) comme un tableau à une dimension, ce qui permet de s'affranchir des multiples modulo et divisions entières quand on peut et de n'y avoir recours que lorsqu'on n'a pas le choix (en général des opérations portant sur un voisinage donné).

Dans le cas de la recherche d'extrema, ces coordonnées ne sont pas nécessaires pendant le traitement : en représentant ton image 3x3 comme un tableau de taille 9, tu auras uniquement deux conversions index->coordonnées, une pour le min, une pour le max.

Citation:

---

Question de goût. Pour m'être arraché les cheveux sur une erreur de compilation due à une macro pendant plusieurs heures, je préfère les éviter.

---

Oui, je comprend ta position, mais pour un min ou un max, ça n'est pas forcément plus dur tout de même !

Citation:

---

En traitement d'images, on représente très souvent les images (2d ou 3d) comme un tableau à une dimension, ce qui permet de s'affranchir des multiples modulo et divisions entières

---

Oui, je sais mais comme progfou faisait état de blocs de 3*3 pixels, je suis parti du principe d'une matrice, mais avec un tableau 1D ça ne pose pas de problème.

Citation:

---

Dans le cas de la recherche d'extrema, ces coordonnées ne sont pas nécessaires pendant le traitement : en représentant ton image 3x3 comme un tableau de taille 9, tu auras uniquement deux conversions index->coordonnées, une pour le min, une pour le max.

---

Oui, nous sommes d'accord, le tout est de savoir quel est la représentation d'origine, si elle se fait sous forme de tableau 1D ou si elle est sous forme de matrice.

D'ailleurs, d'une manière interne, un tableau 2D est la plupars du temps un tableau 1D.

Citation:

---

Envoyé par progfou

j'aimerais savoir s'il existe un algo optimal pour déterminer le minimum (et le maximum) dans un ensemble de n valeurs ?

---

Trouver le minimum demande au moins n-1 comparaisons. Trouver le maximum demande au moins n-1 comparaisons. Mais on peut trouver le maximum ET le minimum simultanément avec 3n/2 comparaisons (au lieu des 2n-2 qu'on pourrait croire).

Pour cela, on parcourt le tableau en maintenant le minimum et le maximum trouvé mais, au lieu de regarder les éléments 1 par 1 on regarde les éléments par pair.
On a déjà parcouru le 2i premiers éléments et on a pour l'instant trouvé le min et le max sur ces 2i éléments. On compare alors les éléments 2i+1 et 2i+2. Si le premier et plus petit que le second, il est candidat pour être min et le second est candidat pour être max (et inversement). On traite donc ces 2 éléments avec seulement 3 comparaisons au lieu de 4 si on avait considéré ces 2 éléments comme éligibles pour être min et max. Il me semble qu'on ne peut pas fait mieux en nombre de comparaisons.

Pour plus d'info, c'est dans "Introduction à l'algorithmique" de Cormen et al.

exact! on peut songer a passer des paires aux triplets, mais on perd: 5*n/3, moins bon que 3*n/2:)

Merci à tous pour vos réponses !
Je vais tâcher de me procurer ce livre ;).