IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

API standards et tierces Java Discussion :

Complexité Spacio-temporelle des listes


Sujet :

API standards et tierces Java

  1. #1
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Mai 2007
    Messages
    4
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France

    Informations forums :
    Inscription : Mai 2007
    Messages : 4
    Par défaut Complexité Spacio-temporelle des listes
    Pour un projet d'étude, j'aurais besoin d'utiliser les listes. Le but est de modéliser un réseau de transport d'une grande ville et donner le plus court chemin. On pourra modifier le réseau (ajouter, supprimer une station). J'hésite entre les ArrayList, les LinkedList et les Vector. Existe-t-il d'autres listes dans l'API de Java ?

    Ma question est : quelle est là meilleure classe à utiliser ? Je pense que la différence se fait au niveau des compléxités spaciales et temporelles de ces listes ? Pouvez-vous me rappeler les compléxités pour les ajout/suppression d'élements et les parcours ?

    D'avance, merci

  2. #2
    Membre expérimenté
    Profil pro
    Inscrit en
    Février 2006
    Messages
    238
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2006
    Messages : 238
    Par défaut
    Salut,

    Alors pour faire très simple (et surtout parceque je n'en sais pas plus ), les ArrayList sont plus performantes lorsque tu les parcours grâce à un entier :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    for (int i = 0 ; i < taListe.size () ; ++i) {
        taListe.get (i);
    }
    Et tu peux atteindre un objet de la liste en connaissant sa position dans la liste.

    Et inversement les LinkedList sont plus efficaces avec un iterateur.
    Les vectors ne sont plus a utiliser.

    voila a+

  3. #3
    Membre éprouvé
    Profil pro
    Inscrit en
    Mai 2007
    Messages
    116
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2007
    Messages : 116
    Par défaut
    Salut,
    j'avais fais un projet du meme genre que le tient. Le truc donnait les plus court chemin par dijkstra enfin je ne me rapelle plus tres bien et j'arrive plus a retrouver ce truc. Je peux te dire j'avai utiliser des ArrayList<Noeud>.
    Noeud contenait elle meme 2 arraylist(preecesseurs et sucesseurs). Si je trouve des infos la dessus je te les file.

  4. #4
    Membre éclairé Avatar de Razgriz
    Profil pro
    Professeur / chercheur en informatique / mathématiques
    Inscrit en
    Avril 2006
    Messages
    391
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations professionnelles :
    Activité : Professeur / chercheur en informatique / mathématiques

    Informations forums :
    Inscription : Avril 2006
    Messages : 391
    Par défaut
    Il existe trois structures de données clés pour ce cas :

    Les tableaux : accès en O(1) , ajout et suppression n'impote où en O(n)

    Les listes chainées ( java.util.LinkedList<E> ): accès et ajout dans la liste en O(n/2), ajout et supression et début et fin de liste en O(1).

    Les ArrayList (qui sont en fait des listes chainnées de tableaux) et qui sont un bon compromis entre les deux.

    Il fauit analyser ton problème et savoir quelle opération va être fortement utilisée, et choisir la structure de donnée en fonction de cela.

  5. #5
    Membre éclairé Avatar de Razgriz
    Profil pro
    Professeur / chercheur en informatique / mathématiques
    Inscrit en
    Avril 2006
    Messages
    391
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations professionnelles :
    Activité : Professeur / chercheur en informatique / mathématiques

    Informations forums :
    Inscription : Avril 2006
    Messages : 391
    Par défaut
    J'ai oublié de dire : les listes ont une complexité mémoire en 3n (3 références par élément), les tableaux en 1 (une référence par taleau quel que soit sa taille) et les ArrayList c'est intermédiaire, cela dépend de la taille des tableaux.

  6. #6
    Membre émérite Avatar de remika
    Profil pro
    Inscrit en
    Septembre 2004
    Messages
    806
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France

    Informations forums :
    Inscription : Septembre 2004
    Messages : 806
    Par défaut


    Sinon tu as aussi la FAQ sur les listes qui résume un peu le truc :
    Listes
    Il serait pas mal d'ajouter tes précisions à celle-ci Razgriz

Discussions similaires

  1. Représentation intervallaire des listes arborescentes
    Par PMAR dans le forum Décisions SGBD
    Réponses: 1
    Dernier message: 05/11/2004, 09h35
  2. [servlet] gestion des listes d'erreurs ?
    Par MatMeuh dans le forum Servlets/JSP
    Réponses: 8
    Dernier message: 27/10/2004, 10h19
  3. [html:text][indexed]Valeurs des liste null...
    Par thibaut dans le forum Servlets/JSP
    Réponses: 13
    Dernier message: 08/09/2004, 09h36
  4. [glut] de l'intérêt des listes
    Par khayyam90 dans le forum OpenGL
    Réponses: 3
    Dernier message: 26/07/2004, 10h35
  5. [langage] probleme avec les listes dans des listes
    Par pqmoltonel dans le forum Langage
    Réponses: 7
    Dernier message: 27/04/2004, 12h32

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo