IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut [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 !

  2. #2
    Membre chevronné
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    258
    Détails du profil
    Informations personnelles :
    Âge : 46
    Localisation : France, Bas Rhin (Alsace)

    Informations forums :
    Inscription : Juillet 2006
    Messages : 258
    Par défaut
    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.

  3. #3
    Expert confirmé
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Par défaut
    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 ..."

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

  4. #4
    Membre chevronné
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    258
    Détails du profil
    Informations personnelles :
    Âge : 46
    Localisation : France, Bas Rhin (Alsace)

    Informations forums :
    Inscription : Juillet 2006
    Messages : 258
    Par défaut
    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
    que mettre une macro.

    Citation Envoyé par PRomu@ld
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  5. #5
    Expert confirmé
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Par défaut
    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 !

    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.

    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.

  6. #6
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    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.

  7. #7
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 54

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    exact! on peut songer a passer des paires aux triplets, mais on perd: 5*n/3, moins bon que 3*n/2

  8. #8
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    Merci à tous pour vos réponses !
    Je vais tâcher de me procurer ce livre .

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Gestion min/max/moyenne des éléments d'un tableau d'integer
    Par billybobbonnet dans le forum VB.NET
    Réponses: 3
    Dernier message: 30/06/2014, 12h30
  2. min et Max dans un requete
    Par peppena dans le forum Langage SQL
    Réponses: 2
    Dernier message: 06/06/2006, 09h11
  3. Fonction MIN et MAX résultat improbable
    Par UNi[FR] dans le forum SQL Procédural
    Réponses: 7
    Dernier message: 24/04/2006, 11h38
  4. taille min et max d'un div
    Par grinder59 dans le forum Général JavaScript
    Réponses: 2
    Dernier message: 10/02/2006, 17h46
  5. min et max
    Par sorinexp dans le forum Access
    Réponses: 6
    Dernier message: 28/11/2005, 19h37

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo