Synthèse sur les structures de données / collections de Java 1.6

16 octobre 2008 at 15 h 08 min 1 commentaire

Un article plus technique que d’habitude aujourd’hui, dont le but va être d’avoir une vue globale des structures de type tableaux / listes en java.

Ma première expérience avec les structures de données remonte à l’époque des cours de MathSup où le cours d’informatique nous expliquait quand et pourquoi une liste chainée peut être plus efficace qu’un tableau. NOn nous demandait d’implémenter nous même nos propres algorithmes de tri / insertion / recherche en langage CAML, en priant Knuth, Stirling et leurs amis pour ne pas faire d’erreur😉
Avec les l’évolution des langages modernes, proposant de nombreuses librairies il vaut mieux aujourd’hui bien savoir choisir ses structures de données plutot que de les implémenter soi même.

Bien choisir ses structures de données, donc avoir un aperçu clair des types de tableaux fournis par le langage, est primordial pour bien implémenter ses programmes. Voici une synthèses des notes de SUN intitulées « Introduction to the collection Framework » sur le thème des collections, disponibles ici:

Tutoriel de Sun

Des interface et des implémentations:

Le framework Collections propose des interfaces (elles permettent de standardiser les méthodes même pour des structures différentes). Intéressons nous à ces interfaces: il en existe 3 différentes:

Le Set

Collection, doublons non autorisés

La List

Collection, doublons autorisés, et systeme d’index implémenté pour accès rapide aux données

La Map

Ensemble de paires (par opposition à la collection), donc collections de données composées clé/valeur

Les implémentations disponibles sont les suivantes:

Interface Implémentation Historique
Set HashSet TreeSet
List ArrayList LinkedList Vector

Stack

Map HashMap TreeMap Hashtable

Properties

Méthodes disponibles pour trier / insérer / rechercher

Voici la liste des méthodes mises à disposition par l’interface Collection:

Ajouter / supprimer:
add(Element) et addAll(Collection)
clear()
remove(Element), removeAll(Collection), retainAll(Collection)
retainsAll se comporte comme l’intersection d’après le terme ensembliste

Rechercher / parcourir
contains(Element)
containsAll(Collection)
iterator() (retourne un objet itérateur qui permet de parcourir la collection avec hasNext())

Dénombrer
size()

Voir la javadoc

Les implémentations de Set

Hash Set et TreeSet sont disponibles.
Si vos données ne doivent pas avoir de doublon, utilisez un HashSet (temps constant).
Si elle doit en plus etre triée, prenez un TreeSet (insertions suppressions et recherches en Log(n))

Les implémentations de List

La liste permet d’avoir des données ordonnées et accepte les doublons.
Le choix doit être fait entre une liste chainée LinkedList et un tableau ArrayList.
Si de nombreuses insertions sont réalisées, alors la liste chainée est plus efficaces (temps constant contre temps linéaire pour la ArrayList). En revanche, l’accès aux données en fonction de l’index (méthode get()) est constant pour l’ArrayList et linéaire pour la liste chainée (obligation de parcourir tous les éléments…).

Les implémentations de Map

Les données ne sont pas ordonnées. L’insertion et l’accès aux valeurs se font grace a une clé.
Deux implémentations encore sont proposées. La hashMap et la TreeMap. La hash map réalise les opérations get et put en temps constant, mais le parcours (méthode contain) a une complexité linéaire. En revanche pour la treemap, l’insertion, le parcours, et l’accès aux données est réalisé aec une complexité de log(n).

Synthèse, que choisir ?

Les questions à se poser sont donc:
– ai-je des doublons ?
– dois-je privilégier le parcours ou l’inserstion suppression ?
– mes données doivent elles être ordonnée ?

Références:
Penser en java / Thinking in java de Bruce Eckel

Tutoriel de Sun

Entry filed under: java. Tags: , , , .

Tutoriel GWT : Création d’un service distant Comment convertir un fichier ISO en UTF-8 ?

Un commentaire Add your own

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Articles récents


%d blogueurs aiment cette page :