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

Java Discussion :

Fonction recherche affinée (TreeMap)


Sujet :

Java

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    94
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2010
    Messages : 94
    Par défaut Fonction recherche affinée (TreeMap)
    Bonjour,

    J'ai conçu une application qui comporte une classe qui possède une TreeMap<Intervalle,Double> où intervalle = [ borneInf, borneSup ]

    Je souhaite obtenir le plus de performance pour obtenir le double associé à un intervalle.

    J'ai exécuté un parcours (avec iterator) mais je trouve cela coûteux et long.
    Par exemple si j'ai un intervalle [100,101] en premier dans la liste et que je souhaite obtenir la valeur qui se trouve dans l'intervalle [0,1] je dois tout parcourir.. Comment faire pour obtenir directement l'intervalle à partir d'un nombre? (biensûr en entrée je n'envoie pas l'intervalle)

    i.e si j'ai valeur 5.4 je veux trouver l'intervalle dans ma collection auquel appartient le nombre 5 pour renvoyer un double associé à ce nombre sans parcourir toute la treemap.

    Dois-je moi même programmer cette fonction recherche ou a t'elle déjà été implémentée pour des objets ? (car si j'avais une treemap(integer, string) je balance l'entier et j'ai la valeur associé, mais comment cela fonctionne t'il avec un objet que j'ai crée (ici intervalle) si je lui lance juste un entier ?

    Merci beaucoup d'avance !

  2. #2
    Membre Expert
    Inscrit en
    Août 2009
    Messages
    1 073
    Détails du profil
    Informations forums :
    Inscription : Août 2009
    Messages : 1 073
    Par défaut
    L'intérêt d'avoir une TreeMap<Intervalle, Double> c'est bien de faire une recherche par des objets instance de la classe Intervalle.

    Maintenant, tu dois pouvoir t'en sortir avec quelques hypothèses sur ce que va contenir ta Map, et les fonctions equals et compareTo de ta classe Intervalle.

    Vu la façon dont tu poses le problème, j'ai l'impression que tu n'auras jamais dans ta map deux intervalles qui se recouvrent (sinon pour un entier quelconque tu aurais plusieurs Intervalles correspondants). Dans ce cas, tu peux définir la comparaison de telle façon que si tu compares deux Intervalle, dont l'un est inclus dans l'autre, il sont égaux. Attention, cette définition casse le contrat standard de la comparaison, puisque tu auras des choses du genre :
    [0,10] = [1,2], [0,10] = [2,3] mais [1,2] < [2,3] (enfin je ne sais pas trop comment tu as implémenté la notion d'ordre, mais ça doit y ressembler).
    Comme c'est un ordre "bizarre", autant le définir dans un comparateur et construire ta map avec ce comparateur, ça fait que ta classe continue à être raisonnable par ailleurs.

    Toujours est-il qu'avec ce mode de fonctionnement, tu peux si tu cherches le double associé à l'intervalle contenant le double d, faire :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    map.get(new Intervalle(d,d));
    (en assumant un constructeur idoine pour Intervalle, et que tu n'imposes pas une stricte différence entre les deux extrémités de l'intervalle)

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    94
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2010
    Messages : 94
    Par défaut
    cela donne donc:

    protected TreeMap<Intervalle,Double> values = new TreeMap<Intervalle,Double>;

    public double getValuesAssocie(d){
    Intervalle intervalle = new Intervalle(d,d)
    Intervalle observee;
    Iterator it = values.entrySet.iterator();
    while(it.hasNext())
    observee = (Intervalle) it.next()
    if(observee.compareTo(intervalle) == 0)
    isFOund = true; }
    return values.get(observee);

    }

    Dans classe intervallle
    private int compareTo(Intervalle inmap){
    traitement de compare
    renvoyer 0 si inclus, -1 sinon
    }

  4. #4
    Membre Expert
    Inscrit en
    Août 2009
    Messages
    1 073
    Détails du profil
    Informations forums :
    Inscription : Août 2009
    Messages : 1 073
    Par défaut
    Non L'intérêt de jouer sur la comparaison, c'est que ta map est déjà triée, et que la recherche se base sur la fonction compareTo (ou sur le comparator que tu auras créé pour l'occasion, ce qui est une meilleur option si tu as besoin de te servir de ta classe dans un autre contexte).

    Ça ressemblerait plus simplement à :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    public double getValuesAssocie(d){
       Intervalle intervalle = new Intervalle(d,d)
       return values.get(intervalle);
    }
    Et ta méthode compareTo doit être bien faite, sinon il n'y a pas d'ordre et avoir une TreeMap ne sert à rien voire est contre-productif. Si tu ne veux pas d'un comparator, je te suggère pour la classe Intervalle :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    Double min;
    Double max;
     
    public int compareTo(Intervalle otherIntervalle) {
       if (this.min >= otherIntervalle.min) {
          if (this.max <= otherIntervalle.max) return 0; // cas de l'inclusion
          return 1;
       }
       if (this.max >= otherIntervalle.max) return 0; // cas de l'inclusion
       return -1;
    }

  5. #5
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    94
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2010
    Messages : 94
    Par défaut
    la solution que tu m'as proposé est bien celle que j'ai implémenté au final (à force de chercher :p)

    Merci pour ton aide

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

Discussions similaires

  1. Fonction Recherche(google) et liens morts
    Par cyrille_ dans le forum Mode d'emploi & aide aux nouveaux
    Réponses: 4
    Dernier message: 06/01/2006, 12h43
  2. Réponses: 3
    Dernier message: 15/11/2005, 18h50
  3. [fonction] recherche de methode inutilisée
    Par frouge dans le forum Eclipse Java
    Réponses: 1
    Dernier message: 12/03/2005, 13h37
  4. fonction Recherche
    Par pingoui dans le forum Débuter avec Java
    Réponses: 16
    Dernier message: 31/08/2004, 17h44

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