List<T> ou Map<U,V> ?

Bonjour à tous !

Lors de mes développements, je suis souvent face à ce choix (Dois-je utiliser une Liste ou une Map ?). J'ai entendu dire que l'utilisation d'une Map est plus intéressante lorsqu'il y a un nombre d'entrées élevé. Sinon, il vaut mieux parcourir la collection. Par exemple, à partir de combien d'instances mieux vaut il utiliser le code 2 à la place du code 1 :

code 1 :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class A { Map<String,MyObj> myObjs = new HashMap<String,MyObj>();   public MyObj getObj(String key) { return myObjs.get(key); }   public void addObj(MyObj obj) { myObjs.put(obj.getKey(),obj); } }

---

code 2 :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class B { List<MyObj> myObjs = new ArrayList<MyObj>();   public MyObj getObj(String key) { for(MyObj obj : myObjs) if(obj.getKey().equals(key)) return obj; return null; }   public void addObj(MyObj obj) { myObjs.add(obj); } }

---

Du point de vue de la montée en charge (au niveau des getObj() ), quelle structure vaut il mieux privilégier ?
J'aimerais savoir s'il existe des études qui ont été faites, et qui permettent de déterminer quelles sont les paramètres à prendre en compte pour décider (genre taille de la collection, taille des objets, fréquence d'accès,...)

Je pense que je ne suis pas le seul à me poser ce genre de questions, aussi j'en fait part ici.

Citation:

---

J'ai entendu dire que l'utilisation d'une Map est plus intéressante lorsqu'il y a un nombre d'entrées élevé.Sinon, il vaut mieux parcourir la collection

---

Pas forcément.
Tu peux avoir des milliers d'objets à traiter stockés au sein d'une collection ou tableau.
Si tu dois traiter tous ces objets, sans exception, à quoi te servirait une map ?
Un tableau ou liste serait davantage pertinent et parlant.

Citation:

---

Du point de vue de la montée en charge (au niveau des getObj() ), quelle structure vaut il mieux privilégier ?

---

Une Map prendra généralement un petit plus plus d'espace en mémoire (clefs + valeurs + sceaux) qu'une List (valeurs).
Avec la mémoire embarquée sur les machines d'aujourd'hui, c'est vraiment négligeable.

Aussi, il y a peu d'intérêt à utiliser une List si sémantiquement un Map convient davantage tant pour l'intelligibilité du code, sa concision que les temps de traitement plus courts qu'une List puisque constants avec les Maps.

Citation:

---

J'aimerais savoir s'il existe des études qui ont été faites, et qui permettent de déterminer quelles sont les paramètres à prendre en compte pour décider (genre taille de la collection, taille des objets, fréquence d'accès,...)

Je pense que je ne suis pas le seul à me poser ce genre de questions, aussi j'en fait part ici.

---

Je m'avance un peu mais je ne pense pas qu'il y en est pour cette question avec les machines puissantes que l'on a à disposition aujourd'hui.
Il y a d'autres sujets plus problématiques quand il est question de montée en charge.

Citation:

---

Envoyé par guejo

Je pense que je ne suis pas le seul à me poser ce genre de questions, aussi j'en fait part ici.

---

Hélas non, mais ce serait bien qu'un peu moins de gens se la posent.

Une Map sert à garder une collection de valeurs associées à des clés.
Une List sert à garder des objets ordonnés, grosso-modo comme dans un tableau mais redimensionnable et avec des fonctionnalités en plus.

C'est tout. Le reste a été pris en compte depuis longtemps.

Merci pour vos réponses, et désolé thelvin si ce sujet est récurrent. J'ai essayé de faire une recherche, mais franchement, je n'ai eu que trop de résultats. Je n'ai pas réussi à filtrer suffisamment pour trouver ce que je cherchais.

Concernant le fait de récupérer toutes les instances ou seulement l'une ou l'autre instance au coup par coup, c'est assez difficile à estimer. On utilise les deux, forcément. Ce que je voulais justement savoir c'est la différence de coût entre un getObj() avec une liste et un getObj() avec une Map. Par exemple, si on a moins d'une dizaine d'instances dans cet ensemble, est-ce que l'utilisation de la Map sera plus rapide que le parcours de la List ? Et pour une centaine ?...

Enfin bon, si j'ai bien compris, je suis en train de couper le cheveu en quatre. Il y a plein d'autres manières d'optimiser le code, j'en suis conscient. Mais ce que je cherche aussi à faire c'est écrire du code propre et cohérent. J'aimerais trouver une règle qui me dit quand je peux mettre une Map, et quand je peux mettre une List. Si j'ai bien compris, on peut invariablement utiliser l'une ou l'autre c'est tout aussi propre et c'est un faux débat. Si c'est le cas, je peux effectivement déclarer ce sujet "résolu" et vous remercier encore tous les 2 pour votre rapidité et votre patience.

Citation:

---

Envoyé par guejo

Si j'ai bien compris, on peut invariablement utiliser l'une ou l'autre c'est tout aussi propre et c'est un faux débat.

---

Alors non tu n'as pas bien compris.

Le faux débat est le suivant : dois-je utiliser une Map ou une List pour que mon code soit le plus efficace.

La vraie question (qui n'est pas un débat) est la suivante : dois-je utiliser une Map ou une List pour que mon code soit le plus lisible, cohérent, propre, tout ce que tu veux.

La vraie réponse est celle que t'as donnée thelvin.

ton code 2 est erroné. Il suppose que les objets stockés aient conscience de leur clé, ce qui n'est pas souhaitable dans la plupart des cas. Tu peux vouloir stocker l'objet sous deux clés différentes dans 2 maps différentes;

Le débat sur la performance est tout aussi faux. Si ta map est petite, les différences de perfomances n'auront aucune influence (et à partir de 3,4 objet tu ne verra déjà plus de différence avec une bonne implémentation de Map). Si ta map est grande, les résultats avec la liste seront catastrophiques.

Donc l'utilisation est simple. T'as une association clé -> valeur, tu prend un Map
T'as juste besoin d'une liste sans clés -> tu prend un List

Après tu devra choisir l'implémentation de Map qui t'intéresse (les performances de la HashMap? Le tri de la TeeMap? L'ordre reproductible de la LinkedHashMap? etc)

Je vois que j'ai fait quelques erreurs de raisonnement. Il parait évident qu'une Map a son utilité, mais je ne sais pas pourquoi, je rechigne à l'utiliser (et je persiste parfois inutilement).

J'aime bien cette "règle" qui consiste à dire que si un objet peut renvoyer un identifiant, alors une collection d'objets de ce type a plus sa place dans une Map que dans une List.

Concernant le fait qu'il n'est pas sage de laisser l'objet connaître son identifiant, là je ne suis pas trop d'accord. S'il peut y avoir plusieurs objets qui peuvent avoir le même identifiant, alors ce c'est plus un identifiant mais un simple attribut. Et si un identifiant peut représenter plusieurs objets alors il brise une contrainte d'unicité. Et puis, dans les bases de données la règle consiste quand même à doter une clé primaire à une table, en général. Même si cette clé peut être répartie sur plusieurs colonnes.
Du coup, pourquoi ne pas utiliser cette clé pour stocker l'objet dans les 2 Map différentes ?

Là ou je suis assez d'accord c'est dans le cas ou la collection a propension à grandir. Mais je ne parlais justement pas de ce cas. Ce que je voulais savoir, c'est à partir de combien d'objets dans la collection le parcours de la collection prend plus de temps que la récupération de l'instance au travers des seaux de la Map. Mais effectivement, ce n'est pas une question d'efficacité, plus de clarté et de maintenabilité (et je pense que c'était ce que je cherchais comme réponse, au fond)

De toutes façons il y a encore bien du chemin à parcourir pour que notre code soit clair et bien organisé... Merci en tout cas de m'avoir fourni les arguments qui me manquaient lors de nos débats internes sur les structures de programmation.

Salut,

Citation:

---

Envoyé par guejo

Lors de mes développements, je suis souvent face à ce choix (Dois-je utiliser une Liste ou une Map ?). J'ai entendu dire que l'utilisation d'une Map est plus intéressante lorsqu'il y a un nombre d'entrées élevé.

---

une map<>:
-avantage : plus souple pour la gestion , code plus simple pour accéder à un élément

-inconvénient : peut-être plus lente qu'une list<> ( voir au niveau performances ) .
Pour une grosse collection demande plus de mémoire

une list<>
-avantage : plus rapide pour chercher et accéder un élément ,en théorie qu'une map<>
-inconvénient: bien plus compliqué et nécessite plus de code qu'une map<>

On peut faire l'analogie d'une map<> avec un dictionnaire de données par exemple un dico français-anglais.
Avec une map<> si tu as un élément après avoir initialisé le conteneur, il suffit de donner la clé ( par exemple "maison" pour trouver "house")
Inversement une list<> c'est linéaire ; si tu veux trouver un élément dans le conteneur de type list<> tu dois faire une boucle pour la parcourir et faire un test d'équivalence pour savoir si tu as trouvé l'élément...

donc une des différences majeures entre l'un des 2 conteneurs et l'autres c'est la nécessité d'avoir une boucle pour trouver un élément.
De plus une map<> fonctionne par pair de valeur, une liste non (il faut un itérateur )

Citation:

---

Envoyé par guejo

J'aime bien cette "règle" qui consiste à dire que si un objet peut renvoyer un identifiant, alors une collection d'objets de ce type a plus sa place dans une Map que dans une List.

---

On a jamais dit ça, la règle c'est "si tu a besoin de retrouver ton objet via une clé".

Ok, dans une BD t'as besoin d'identifiant, mais les objet avec un identifiant sont une goutte d'eau par rapport à la quantité d'objets existant pour lesquels tu peux avoir besoin d'une Map. Des Map<String,Integer> ou Map<String,List<....>> c'est très courant, pourtant on ne peux pas vraiment dire que Integer ou List peuvent renvoyer un identifier. Une Map n'est pas nécessairement une relation BiDirectionnel. Une valeur peux se retrouvé associée à plusieurs clés, entre autres.

Citation:

---

Du coup, pourquoi ne pas utiliser cette clé pour stocker l'objet dans les 2 Map différentes ?

---

Parce que ce n'est pas nécessairement à partir de cette information que tu as besoin de retrouver une valeur.

Citation:

---

Ce que je voulais savoir, c'est à partir de combien d'objets dans la collection le parcours de la collection prend plus de temps que la récupération de l'instance au travers des seaux de la Map.

---

Trouver un élément dans une List sur un critère (peut importe le critère): O(n), n étant le nombre d'éléments. Trouver un élément dans une HashMap: O(log(n)). Il n'y a pas à se poser plus de question. Comme je l'ai dit, considère qu'à partir de 2 à 3 éléments t'as déjà plus aucun avantage dans la list.

Citation:

---

Merci en tout cas de m'avoir fourni les arguments qui me manquaient lors de nos débats internes sur les structures de programmation.

---

Si vous pinaillez sur des détails pareils, vous n'êtes pas prêt de faire sortir le code.

Citation:

---

Envoyé par guejo

Du point de vue de la montée en charge (au niveau des getObj() ), quelle structure vaut il mieux privilégier ?
J'aimerais savoir s'il existe des études qui ont été faites, et qui permettent de déterminer quelles sont les paramètres à prendre en compte pour décider (genre taille de la collection, taille des objets, fréquence d'accès,...)

---

Comme le dit Tchize oui cela induit des développements d'un certain ordre O(log(n))

Citation:

---

Envoyé par guejo

Ce que je voulais justement savoir c'est la différence de coût entre un getObj() avec une liste et un getObj() avec une Map. Par exemple, si on a moins d'une dizaine d'instances dans cet ensemble, est-ce que l'utilisation de la Map sera plus rapide que le parcours de la List ? Et pour une centaine ?...

---

je vais faire une réponse bateau : à toi de faire des tests et tout dépend du problème que tu as à traiter...
ceci dit il vaut mieux préférablement prendre une map<> parce qu'avec une list<> tu vas avoir des boucles...
et les boucles c'est qu'il y a à éviter question performances.

Citation:

---

Envoyé par guejo

Ce que je voulais justement savoir c'est la différence de coût entre un getObj() avec une liste et un getObj() avec une Map. Par exemple, si on a moins d'une dizaine d'instances dans cet ensemble, est-ce que l'utilisation de la Map sera plus rapide que le parcours de la List ? Et pour une centaine ?...

---

A ce moment-là il vaut mieux prendre une map<> cela entraine moins de code à écrire.
Et puis avec une list<> tu risques d'avoir une grosse boucle de recherche.
Pour une map<> aussi mais c'est déjà précompilé dans la Java Virtual Machine...

Citation:

---

Envoyé par guejo

Je vois que j'ai fait quelques erreurs de raisonnement. Il parait évident qu'une Map a son utilité, mais je ne sais pas pourquoi, je rechigne à l'utiliser (et je persiste parfois inutilement).

---

Non je me répète encore une fois : tout dépend de ce que tu veux faire !
Dans certains cas une list<> sera plus appropriée qu'une map<> et vice-versa

Citation:

---

Et puis, dans les bases de données la règle consiste quand même à doter une clé primaire à une table, en général. Même si cette clé peut être répartie sur plusieurs colonnes.

---

là c'est une erreur d'appréciation : il ne faut pas substituer une map<> à l'emploi d'une base de donnée et d'un SGBDR !
Une map<> c'est pour charger un dictionnaire de données temporairement en mémoire pour un programme.
Donc dans ce cas-là l'intégrité des données est réduite au minimum..

Pour des traitements plus lourds, il faut prendre une base de donnée/SGBD ne pas utiliser une map<>

Citation:

---

Envoyé par tchize_

Trouver un élément dans une List sur un critère (peut importe le critère): O(n), n étant le nombre d'éléments. Trouver un élément dans une HashMap: O(log(n)). Il n'y a pas à se poser plus de question. Comme je l'ai dit, considère qu'à partir de 2 à 3 éléments t'as déjà plus aucun avantage dans la list.

---

En préambule : presque tout pareil que Tchize.

Maintenant le pinaillage : si ta List est ordonnée, tu peux faire une recherche en O(log(n)) (bien sûr, cela coûte le prix du maintien de l'ordre) ; et si ton hashCode n'est pas bien implémenté, tu te retrouves avec du linéaire sur la HashMap (et là aussi, normalement ça n'est pas censé arriver).

Citation:

---

Envoyé par Mat.M

Et puis avec une list<> tu risques d'avoir une grosse boucle de recherche.
Pour une map<> aussi mais c'est déjà précompilé dans la Java Virtual Machine...

---

D'ou tiens tu cette information qu'une Map est précompilé en JVM! alors la List est aussi "précompilé". explique nous cette phrase moi je n'ai pas bien saisi en tout cas

Je pense qu'il veut simplement dire que la fonction get de Map est déjà implémentée, alors qu'en utilisant une List tu dois à chaque fois ré-écrire la boucle de recherche de l'élément.

Citation:

---

Envoyé par hibour

D'ou tiens tu cette information qu'une Map est précompilé en JVM! alors la List est aussi "précompilé". explique nous cette phrase moi je n'ai pas bien saisi en tout cas

---

Je voulais dire qu'étant donner que la JVM est faite en partie en code natif donc compilé les algorithmes de traitement aussi bien d'un conteneur que d'un autre sont optimisés

Va falloir réviser tes connaissances. Le code des apis de base java est écrit en java, pas en code natifs, donc il n'a rien d'optimisé à ce niveau. Il a le même status que le code que tu écris toi même. De plus, la hotspot java se charge déjà, pour n'importe quelle classe, de convertir le code java en code machine afin d'optimiser les performances.

tchize_,

T'es trop fort :ccool:
J'adore lire tes posts, j'apprends pleins de trucs intéressants :zoubi:

Citation:

---

Envoyé par tchize_

Va falloir réviser tes connaissances. Le code des apis de base java est écrit en java, pas en code natifs, donc il n'a rien d'optimisé à ce niveau. Il a le même status que le code que tu écris toi même. De plus, la hotspot java se charge déjà, pour n'importe quelle classe, de convertir le code java en code machine afin d'optimiser les performances.

---

1-pour quelqu'un chargé de la modération je trouve la formulation manquant de politesse voire chargée de mépris et de dédain.
Mais bref passons...

2-j'ai bien écris : en partie et je n'ai pas dit en totalité la différence est là.
Je ne comprends pas pourquoi il y autant d'animosité sur un sujet aussi banal que celui-ci

1- Toutes mes excuses, là n'était pas l'intention.

Salut Tchize ok pareillement alors ;)
Est-ce que cela répond aux questions de Guejo alors ?

Citation:

---

Envoyé par Mat.M

1-pour quelqu'un chargé de la modération je trouve la formulation manquant de politesse voire chargée de mépris et de dédain.
Mais bref passons...

2-j'ai bien écris : en partie et je n'ai pas dit en totalité la différence est là.
Je ne comprends pas pourquoi il y autant d'animosité sur un sujet aussi banal que celui-ci

---

Désolé de te contre-dire encore une fois 8O aucune méthode de la classe HashMap, LinkedHashMap, TreeMap n'est native sur la JVM Sun et IBM. Donc à part l'algorithme optimisée aucune autre optimisation existe à ma connaissance (précompilation!).
A++

Citation:

---

Envoyé par Mat.M

Salut Tchize ok pareillement alors ;)
Est-ce que cela répond aux questions de Guejo alors ?

---

Euh, oui. Depuis le 21/06, en fait. ;)

Je n'ai pas reposté depuis car je n'avais pas grand chose à rajouter à ce qui a été dit. J'avais posé cette question car j'avais un a-priori sur les Map en général par rapport à leur lourdeur sur les traitements. Je souhaitais des réponses plutôt quantitatives ("peu de différence de perf au delà de 2-3 instances") que qualitatives ("plus souple pour la gestion", "code plus simple",...), mais il n'empêche que ça a tout de même répondu à la question.

Ensuite par rapport à tchize_, je trouve aussi que certaines interventions sont un peu limites ("code erroné", "pas prêt de faire sortir le code"), mais en même temps je me vois mal commencer à râler la-dessus alors que je demande quelque chose et qu'il me répond. Disons qu'il suffit de laisser reposer et de ne pas répondre à chaud ;)

Donc encore une fois, merci à tous les intervenants, pour moi ce sujet est clos.:ccool:

Citation:

---

Envoyé par hibour

Désolé de te contre-dire encore une fois 8O aucune méthode de la classe HashMap, LinkedHashMap, TreeMap n'est native sur la JVM Sun et IBM. Donc à part l'algorithme optimisée aucune autre optimisation existe à ma connaissance (précompilation!).
A++

---

ok si je me trompe alors peux-tu donner un lien qui le démontre ?

Citation:

---

Envoyé par Mat.M

ok si je me trompe alors peux-tu donner un lien qui le démontre ?

---

suffit d'ouvrir un IDE (netbeans ou eclipse) et lui demander d'afficher la source de HashMap ou ArrayList, et tu verra que c'est du code java tout ce qu'il y a de plus courant. Pas une seule méthode native.