Discussion :

[freakfm]

Bonjour,

J’ai une TreeMap, que ces éléments sont triés selon leur prix ( par exemple). Comment à partir d’un clefs (par exemple) je peut avoir la position de l’élément dans la TreeMap ??

[freakfm]

Je peut par exemple crée un itérateur qui va parcourir tous les clefs jusqu’à arriver à celui qu’on veut sa position, et comme cela avec un simple int qu’on incrémentera chaque fois qu’on fait next, on peut avoir la position.

Mais cette méthode me pares un peut lente et je ne sait pas si on peut faire mieux.

[freakfm]

J’ai trouvé cette solution , mais je ne sait pas si c’est moins couteuse que si j’utilise un itérateur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
ArrayList al = new ArrayList (sm.keySet() );
int rank = al.indexOf(price);

??

[leyee]

Le indexof n'est pas magique : il parcours forcement l'arraylist jusqu'a trouvé l'objet que tu lui demande : je pense cependant que c'est un peu plus rapide que de le faire à la main sachant que les méthodes, notamment celles des collections sont fortement optimisées

[pongping]

Je pense que tu dois utiliser le fait qu'une TreeMap est déjà triée. Ce que tu peux faire est une recherche binaire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
int rank = Collections.binarySearch(sm.keySet(), price)

Dans ce cas, ta recherche aura une complexité O(log² n).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
ArrayList al = new ArrayList (sm.keySet() );
int rank = al.indexOf(price);

est moins rapide car une ArrayList est par définition non triée, donc une complexité O(n), ce qui est moins rapide que O(log² n).

[freakfm]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int rank = Collections.binarySearch(sm.keySet(), price)

Merci .
en effet, dans la javadoc j'ai trouver la phrase suivante (pour static int binarySearch(List list, Object key) ):

"If the specified list does not implement the RandomAccess and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons."

quel sont les List qui implément l'interface RandomAccess??