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??

[leyee]

RandomAccess = comprendre acces en temps constant : tu possedes donc toutes les collections de type clé valeur

[freakfm]

donc dans notre cas la complexité ne va pas etre O(log n). car la Set retourné par "sm.keySet()" n'est pas sous forme de (clef, valeur).

[pongping]

Alors tu peux faire

Code :

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

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

Je pense que ceci sera alors O(log n) mais je ne sais pas si ça sert à quelque chose car le fait de créer une nouvelle ArrayList prend aussi du temps... Quelqu'un sait si ça prend beaucoup d'instructions?

[freakfm]

Alors tu peux faire

Code :

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

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

Je pense que ceci sera alors O(log n) mais je ne sais pas si ça sert à quelque chose car le fait de créer une nouvelle ArrayList prend aussi du temps... Quelqu'un sait si ça prend beaucoup d'instructions?

Je pense pas que ça va étre plus optimiser que :

Code :

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

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

mais bon, je ne suis pas sûr. Je propose à mettre ce sujet on état (résolu) car il n'y pas grand chose à dire en plus.
Thank you

[freakfm]

Code :

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

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

retourn une cast exception. Car elle prend en parametre une List et pas une Set. Donc en fin de compt je vais faire l'autre solution:

Code :

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

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

[freakfm]

RandomAccess = comprendre acces en temps constant : tu possedes donc toutes les collections de type clé valeur

En fait quand j'ai vu la javadoc, j'ai trouvé que les seul class qui implemente cette interface sont ( ArrayList, Vector et Stack). ce n'est pas vraiment tous les collections de type clé valeur

[freakfm]

En fait, j'ai deux TreeMap, une qui est trié et l'autre trié dan l'ordre inverse. Donc pour celle qui est inversé je doit la réinversé pour aplliqué le "Collections.binarySearch" et apres la réinversé pour la métre dans l'ordre normale, ce qui va étre un autre O(n). Donc en fin de compte je pense que ce "Collections.binarySearch" ne va pas me servir à grand chose
bof

[pongping]

En fait, j'ai deux TreeMap, une qui est trié et l'autre trié dan l'ordre inverse. Donc pour celle qui est inversé je doit la réinversé pour aplliqué le "Collections.binarySearch" et apres la réinversé pour la métre dans l'ordre normale, ce qui va étre un autre O(n). Donc en fin de compte je pense que ce "Collections.binarySearch" ne va pas me servir à grand chose
bof

Mais personne t'as dit qu'il fallait utiliser Collections.binarySearch(), tu peux aussi coder ta propre implémentation. La recherche dichotomique (oui, ça s'apelle comme ça en Français ) est facile à implémenter. En tout cas, si tu as beaucoup de valeurs, la recherche sera beaucoup plus rapide que la recherche séquentielle (un par un).

[freakfm]

tu as raison . J'ai oublié qu'on peut faire des choses nous même avec java (à cause des énorme quantité de methodes qui existent) .

see you

[pongping]

Tu avais raison de poser la question car il est souvent plus utile d'utiliser une méthode de la libraire Java. Pourquoi réinventer la roue? De plus, ces méthodes sont souvent optimisés au maximum.