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

Langage Delphi Discussion :

Quel algorithme pour insertion d'objets "triés" da


Sujet :

Langage Delphi

  1. #1
    Membre habitué Avatar de phplive
    Profil pro
    Inscrit en
    Avril 2003
    Messages
    179
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2003
    Messages : 179
    Points : 150
    Points
    150
    Par défaut Quel algorithme pour insertion d'objets "triés" da
    Bsr,

    J'ai un TList dans laquelle je souhaite ajouter n Objects. (avec n < 100000 soyons raisonnable)

    Ces objets possèdent une propriété ID (elle même composée de x champs mais peu importe).
    Je ne désire pas retrouver les objets par leur index, ni leur adresse, mais bien par leur ID.

    J'aimerais insérer ces objets dans ma liste de telle sorte qu'ils
    soient en permanance triés sur leur ID.

    Quel algorithme utiliser pour retrouver l'index d'insertion mais aussi la position d'un objet tant qu'on y est ?


    D'autre part l'emploi d'une liste est-il judicieux ?

    Sur le net plusieurs sites parlent d'arbre binaire équilibré ?
    Comment ca marche et de quoi s'agit-il exactement ?

    Merci

    @+
    Php
    @+
    Php

    D7 Enterprise - XP sp2
    The Truth is Out There

  2. #2
    Membre averti
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    298
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 298
    Points : 318
    Points
    318
    Par défaut
    Déjà une TList de base ne suffit par car on doit coder pour inserer l'objet à la bonne place. Dans un liste triée on travaille par dichotomie.

    Si tu connais le nombre d'objet à l'avance, tu peux spécifier la Capacity de la tlist au départ, cela évitera les realloctions mémoire.

    J'aurai tendance à dire qu'un arbre binaire est plus performant, mais il faudrait le tester (surtout si tu ne connais pas le nombre d'objet au préalable).

    Pour ce qui est des algo, un tour dans google devrait faire l'affaire.

  3. #3
    Membre émérite Avatar de edam
    Homme Profil pro
    Développeur Delphi/c++/Omnis
    Inscrit en
    Décembre 2003
    Messages
    1 894
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Développeur Delphi/c++/Omnis
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 1 894
    Points : 2 771
    Points
    2 771
    Par défaut
    utilise plutot une Tstringlist si votreID de type string si non converti le enstring avec une lengeur fixe en ajoutant des 0 au début:
    pax example 1-->00001, 2--->00002, et insi de suite ,
    tstringlist a une otion qui trie les odnnées entrée, pour le réste de tes odnnée tu peut les ajouter normalement comme dans une Tlist avec

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    var  t&#58;^votrerecord;
    begin
       new&#40;t&#41;;
       t.id&#58;=4;
       ....  
       TStringList.additem&#40;formatFloat&#40;'000000',t.id&#41;,object&#40;t&#41;&#41;;// a vérifier 
    end;
    PAS DE DESTIN, C'EST CE QUE NOUS FAISONS

  4. #4
    Membre habitué Avatar de phplive
    Profil pro
    Inscrit en
    Avril 2003
    Messages
    179
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2003
    Messages : 179
    Points : 150
    Points
    150
    Par défaut
    Bjr,

    Merci,

    J'ai donc au final utilisé la dichotomie et ca marche tès bien sur 10 000 items !

    A condition de penser à retrier ma liste dès que l'ID d'un objet est modifié.

    Pour les arbres binaires je verrais plus tard.


    @+
    Php
    @+
    Php

    D7 Enterprise - XP sp2
    The Truth is Out There

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. quel algorithme pour trouver le plus grand sous arbres commun à des arbres?
    Par iwky911 dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 20/05/2009, 22h08
  2. [phpBB] Script pour insertion d'objets
    Par Lorely dans le forum EDI, CMS, Outils, Scripts et API
    Réponses: 1
    Dernier message: 30/12/2006, 19h15
  3. Réponses: 7
    Dernier message: 12/10/2006, 02h23

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