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

Algorithmes et structures de données Discussion :

Meilleur algorithme pour trier de très grandes quantités de chaînes de caractères


Sujet :

Algorithmes et structures de données

  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    38
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Novembre 2004
    Messages : 38
    Par défaut Meilleur algorithme pour trier de très grandes quantités de chaînes de caractères
    Voilà, tout est dit dans le titre. Je voudrais savoir selon vous quel est le meilleur algorithme pour trier un nombre conséquent de chaînes de caractères (2 à 4 millions, mettons) dans l'ordre lexicographique.
    Merci

  2. #2
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Tri par fusion, non ?

  3. #3
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Bonjour,

    quel est le taille de tes chaines de caractères ?

    Si elles ne sont pas tres longues...
    une méthode valable dans cette situation est de trier caractère par caractères :
    - Tu choisis un algo de tri (quicksort par exemple) et tu tries tous les mots en ne regardant que le caractère i dans la chaine de caractère.
    - Tu répètes cette opération en commencant par la fin du mot pour que le tri fonctionne.
    - Il faut juste penser à gérer ne fait que les mots n'ont pas la même taille.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  4. #4
    Membre émérite

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2006
    Messages
    450
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Avril 2006
    Messages : 450
    Par défaut
    Si tu ne dois juste que trier, prends le quicksort. Si tu dois trier et garder trier (insérer, enlever des chaînes, etc.) utilises un arbre binaire (mais je ne pense pas que ce soit le cas ici).

  5. #5
    Modérateur
    Avatar de gangsoleil
    Homme Profil pro
    Manager / Cyber Sécurité
    Inscrit en
    Mai 2004
    Messages
    10 150
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Manager / Cyber Sécurité

    Informations forums :
    Inscription : Mai 2004
    Messages : 10 150
    Par défaut
    Bonjour,

    Comme l'ont dit les autres personnes, il faut que tu te bases sur un algo comme quicksort.

    Ensuite, tu peux chercher non pas à améliorer l'algo, mais à l'appliquer sur tout ou partie de la chaine.

    Par exemple si tes chaines ont de très nombreuses différences dans les premiers caractères, il vaut mieux essayer de trier en se bassant d'abord sur les premier caractères.
    En revanche, si tu as des chaines ayant une grande probabilité d'avoir le même début, il ne sera pas intéressant de tester systématiquement tous les caractères en commencant par le début.

    Il faut donc que tu cherches des points communs ou des différences à tes chaines, pour pouvoir en tirer des heuristiques, qui te permettront d'améliorer le temps de traitment au final.
    "La route est longue, mais le chemin est libre" -- https://framasoft.org/
    Les règles du forum

  6. #6
    Expert confirmé Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Par défaut
    Bonjour,

    Pour trier simplement, un algo de sort comme indiqué dans les réponses précédentes.

    Par contre, si on doit faire des recherches et des insertions, je préconiserais un arbre comme celui de l'exemple ci-dessous (plutot qu'un arbre binaire) :

    Avec les les mots :
    • A
    • AME
    • AMI
    • AMOUR
    • BUT
    • CE
    on aurait la structure suivante :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    #
    |
    A------------B-------C
    |            |       |
    *-M          U       E
       |         |       |
       E--I--O   T       *
       |  |  |   | 
       *  *  U   *
             |
             R 
             |
             *
    Le caractère * indique la fin du mot.

  7. #7
    Membre émérite
    Avatar de panda31
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Juin 2003
    Messages
    670
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : Juin 2003
    Messages : 670
    Par défaut
    J'avoue que c'est beau ! Mais un arbre binaire peut faire l'affaire à mon sens. En effet, si tu as un grand nombre de mots comme indiqué dans la requête
    de Cecilka, tu vas avoir un nombre inquiétant de branches non ? Ton arbre binaire de recherche pourra quant à lui se limiter en largeur...
    Michaël Mary
    Consultant PLM dans une société de conseil toulousaine
    Auditeur CNAM-IPST depuis septembre 2008
    "Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live."
    John F. Woods
    mon cv et mon domaine et mon blog
    Aucune question technique par MP, svp

  8. #8
    Expert confirmé Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Par défaut
    Bonjour,

    Mais un arbre binaire peut faire l'affaire à mon sens. En effet, si tu as un grand nombre de mots comme indiqué dans la requête de Cecilka, tu vas avoir un nombre inquiétant de branches non ?
    Le nombre de fils d'un noeud est au maximum égal au nombre de symboles de l'alphabet. En pratique, chaque noeud aura un nombre de fils de l'ordre de 1 à 10 et la profondeur des branches correspond à la longueur des mots. Donc, en se basant sur une moyenne de 6 fils par noeud, la recherche/insertion d'un mot de 10 lettres se fera en 10 x 6/2 = 30 comparaisons de noeuds, ce qui represente, à vue de nez, 2 à 4 fois plus que pour un arbre binaire équilibré (AVL). Mais, c'est pas cher payé par rapport au "couts" d'équilibrage de l'AVL lors des insertions/suppressions.

  9. #9
    Membre émérite
    Avatar de panda31
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Juin 2003
    Messages
    670
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : Juin 2003
    Messages : 670
    Par défaut
    Et bien merci pour ton explication grâce à ce beau calcul de complexité !
    Michaël Mary
    Consultant PLM dans une société de conseil toulousaine
    Auditeur CNAM-IPST depuis septembre 2008
    "Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live."
    John F. Woods
    mon cv et mon domaine et mon blog
    Aucune question technique par MP, svp

  10. #10
    zul
    zul est déconnecté
    Membre chevronné Avatar de zul
    Profil pro
    Inscrit en
    Juin 2002
    Messages
    498
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2002
    Messages : 498
    Par défaut
    Pour ameliorer un peu la structure proposé par graffito, tu peux utiliser ce qu'on appelle des arbre de patricia ( patricia tree / radix tree ) ce qui revient a "paquer" ensemble esl branches communes ( cad au lieu d'avoir -b-u-t, tu as un noeud but ) : ca reduit la complexite spatiale.

    Si la complexite spatiale n'est pas importante, dans chaque noeud, tu peux stocker un tableau de 26 caractères. La recherche se fait alors en O(n) n longueur de la chaine ou O(1) si tu considere que les chaines sont bornées.

Discussions similaires

  1. Surcharge de l'opérateur / en c++ pour les entiers très grands
    Par marbouchi dans le forum Mathématiques
    Réponses: 1
    Dernier message: 05/05/2009, 00h08
  2. Surcharge de l'opérateur / pour les entiers très grands
    Par marbouchi dans le forum Débuter
    Réponses: 5
    Dernier message: 04/05/2009, 21h28
  3. [Javascript][XSLT] Meilleur solution pour trier des données ?
    Par buzzkaido dans le forum XSL/XSLT/XPATH
    Réponses: 1
    Dernier message: 11/10/2006, 13h26
  4. Algorithme pour trier trois nombres
    Par legosam dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 17/01/2005, 21h47
  5. Une unité pour gérer des très grands nombres
    Par M.Dlb dans le forum Langage
    Réponses: 2
    Dernier message: 09/09/2003, 12h07

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