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 ??:(
Version imprimable
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 ??:(
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.
:roll:
J’ai trouvé cette solution , mais je ne sait pas si c’est moins couteuse que si j’utilise un itérateur :
??:roll:Code:
2
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 :)
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:
Dans ce cas, ta recherche aura une complexité O(log² n).Code:
2
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).Code:
2
3
Merci:D .Code:int rank = Collections.binarySearch(sm.keySet(), price)
en effet, dans la javadoc j'ai trouver la phrase suivante (pour static int binarySearch(List list, Object key) ):
quel sont les List qui implément l'interface RandomAccess??Citation:
"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."
RandomAccess = comprendre acces en temps constant : tu possedes donc toutes les collections de type clé valeur
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).
Alors tu peux faire
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?Code:
2
Je pense pas que ça va étre plus optimiser que :Citation:
Envoyé par pongping
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.Code:int rank = Collections.binarySearch(sm.keySet(), price)
Thank you;)
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:int rank = Collections.binarySearch(sm.keySet(), price)
:DCode:int rank = Collections.binarySearch(new ArrayList(sm.keySet()), price);
Citation:
Envoyé par leyee
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;)
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:bug:
bof
:france:
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).Citation:
Envoyé par freakfm
tu as raison :king: . J'ai oublié qu'on peut faire des choses nous même avec java (à cause des énorme quantité de methodes qui existent):mouarf: .
see you:merci:
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.