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 !

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:

---

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)

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
}

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:

---

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:

---

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

---

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