Maps, Lists et performances
Bonjour,
Je développe une application possédant ces quelques caractéristiques:
- Je suis amené a gérer des ensembles d'environ 18000 éléments uniques,
- J'effectue beaucoup d'insertion,
- Je dois pour chacun des éléments parcourir toute la liste pour vérifier un certain critère avec les autres éléments: je fais une recherche sur tout l'ensemble un grand nombre de fois.
On va dire qu'en gros, je récupère sans arrêt de nouveaux éléments, que je les stocke uniquement si je ne les ai pas déjà. A partir de chacun de ces éléments, je cherche celui le plus proche, et il me permet d'obtenir de nouveaux éléments, et ainsi de suite.
Selon ces considérations, j'hésite à utiliser des ArrayList, HashMap ou TreeMap.
Les HashMap me permettraient d'avoir un accès en O(1) aux éléments. Mettre la valeur en clé me permettrait aussi de savoir en O(1) si un élément est déjà dans la liste puisqu'un get(Key) sera a priori plus rapide qu'un contains(value).
En revanche, lorsque je dois parcourir toute la liste pour vérifier le critère, j'ai peur que l'itérateur sur les valeurs de la HashMap soit long, comparer à une boucle for introduite par Java 5 sur un ArrayList. L'ArrayList l'emporterait à ce niveau.
Je n'ai pas besoin que les éléments soient triés, mais s'ils le sont, avec une TreeMap, je n'ai pas besoin de faire un parcours entier pour vérifier le critère, la rehcerche serait plus simple mais l'insertion se ferait en O(log(n)).
Bref j'ai du mal à voir quelle structure de données serait la plus rapide dans mon cas. J'ai fais quelques tests et à l'insertion de 18000 éléments, ArrayList semble plus lent que la HashMap. Ca me parait bizarre.
Pouvez vous m'aider à me décider sur la structure de données à utiliser ?
Merci d'avance,
Cordialement
Répondre avec citation
Partager