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

Java Discussion :

Le tri Burst Sort


Sujet :

Java

  1. #1
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    40
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 40
    Par défaut Le tri Burst Sort
    Bonjour,
    Je suis en train d'étudier une nouvelle façon de trier les String, appelée Burtsort.
    J'ai vu qu'il y avait déjà des bibliothèque en C++ qui avaient été développées, aussi je voudrais savoir si quelqu'un l'a implémenté en Java.

    Merci

  2. #2
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    40
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 40
    Par défaut Informations supplémentaires
    Bon, je vois que ça ne tente personne le burstSort, alors je vais voir si vous pouvez m'aider en vous donnant plus de précisions.

    Donc un BurstTrie consiste en 3 composants :

    Records : qui contient la String que l'on gère, des informations supplémentaires utiles à l'application qui utilise ce Sort (comme "word location" par ex.), et un pointer sur le son conteneur(container).

    Containers : c'est donc plusieurs "Records" rangées dans une liste ou dans un arbre binaire. Pour un container de profondeur k, les String de chaque record ont au moins une longueur k et ces k caractères sont identiques pour tous les "Records" de ce "container" (par ex : auteur, automobile, autopsie). le container contient aussi une en-tete pour les statistiques.

    Puis
    Acces Trie : un arbre dont les feuilles sont des containers et les noeuds sont des tableaux p de pointeurs, de longueur équivalent à la taille de l'alphabet (ici 26 bien sur! ). chacun de ces pointeurs pointe donc vers un autre noeud ou vers un container. Et chaque case du tableau est la lettre de l'alphabet correspondant à son index.


    Voilà je sais que ça fait beaucoup, mais si quelqu'un a le courage de m'aider, je l'en remercie d'avance.

  3. #3
    Modérateur
    Avatar de dinobogan
    Homme Profil pro
    ingénieur
    Inscrit en
    Juin 2007
    Messages
    4 073
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France

    Informations professionnelles :
    Activité : ingénieur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 4 073
    Par défaut
    Mais ?!?!?
    Tu as l'algorithme complet, alors ou est le problème pour le codage ?
    Tu ne chercherais tout de même pas ici un poireau pour te coder ton algo ?
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
    Que la force de la puissance soit avec le courage de ta sagesse.

  4. #4
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    40
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 40
    Par défaut re
    non mais merci de ton sarcasme !

    Le problème c'est que les mots que je traite sont en minuscule comme en majuscule et qu'il y a encore les accents à prendre en compte.
    Donc je voulais déjà savoir pour les tableaux de chaque nœud si je dois agrandir sa taille ou si je dois le faire à 2 dimensions avec les différents variantes de chaque lettre.

    Ensuite pour ce qui est des arbres, c'est pas mon fort, je sais que chaque feuille d'un arbre est un arbre sans fils (ou un noeud sans fils) mais je sais pas comment faire pour que les feuilles soient de type différents des noeuds

  5. #5
    Modérateur
    Avatar de dinobogan
    Homme Profil pro
    ingénieur
    Inscrit en
    Juin 2007
    Messages
    4 073
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France

    Informations professionnelles :
    Activité : ingénieur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 4 073
    Par défaut
    Citation Envoyé par fanzyride Voir le message
    non mais merci de ton sarcasme !
    Je ne cherchais pas du tout à être sarcastique !
    Relis bien les posts, et met-toi à ma place : tu demandes une API pour le tri, personne ne réponds. Et j'imagine que tu as cherchés aussi. Ensuite, tu sors l'algo détaillé sans aucune autre info, on ne connais pas l'état d'avancement de ton dev, ni tes difficultés algorithmiques. Mais maintenant, avec ta réponse, c'est plus clair
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
    Que la force de la puissance soit avec le courage de ta sagesse.

  6. #6
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2008
    Messages
    43
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 43
    Par défaut
    Pour le problème des accents, majuscule ... tu recense l'ensemble de ton alphabet et tu dimensionnes tes tableaux en fonction.

    Pour les feuille et noeud, tu n'utilise qu'une seule classe (Noeud) qui est dont les instances sont des feuilles si elles n'ont ni fils gauche ni fils droit.

    Pour le reste, je te laisse faire

  7. #7
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    40
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 40
    Par défaut
    Désolé je m'emporte un peu, je galère dessus depuis hier aprem.
    C'est assez compliqué à expliquer c'est un tri par préfixe et la taille du préfixe dépend de la profondeur dans l'abre.
    Si tu veux bien regarder le schéma de la page 7 (ou 9) du pdf suivant :

    http://goanna.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf

    Il y a aussi les algorithmes pour l'insertion l'éclatement (burst) et la recherche, mais sans la structure de mon arbre j'arrive pas trop à les coder.

  8. #8
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    40
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 40
    Par défaut BurstSort sur fichier
    Bonjour,
    Bon je suis bien arrivé à coder cet algorithme, mais le problème c'est lors de la segmentation d'un texte de 100 Mo Il y a trop de String à stocker donc cela me génère une erreur de outOfMemory. Il faut donc que je puisse sauvegarder le contenu des containers dans un ou des fichiers de façon à pouvoir y accéder constamment pour ajouter modifier ou éclater (burst) son contenu dans des nouveau fichiers/containers (container étant l'équivalent d'un vecteur d'objet ou chaque objet contient la string la liste d'offsets d'occurrences ).

    Pour l'instant j'ai fait en sorte que chaque fichier soit un container, et chaque ligne de ce fichier soit un String que l'on peut retransformer en objet (String + offsets d'occurrences). Mais le problème c'est qu'à chaque mot trouvé, je lis un fichier pour en faire un vecteur d'objet, j'ajoute mon mot s'il y est pas sinon j'ajoute les offsets, puis je réenregistre tout le vecteur dans le fichier.
    Donc ce n'est pas performant(un texte de 100mo prend minimum 7heures).

    Je voudrais savoir comment je peux faire pour améliorer cela ?
    Merci

  9. #9
    Membre éclairé
    Inscrit en
    Décembre 2005
    Messages
    50
    Détails du profil
    Informations forums :
    Inscription : Décembre 2005
    Messages : 50
    Par défaut
    en changeant les propriete au lancement de ta machine virtuelle par :

    java -Xmx 256m monProg

    En mettant le nombre de MB dont tu as besoin.

  10. #10
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    40
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 40
    Par défaut re
    Euh, Je fais tourner mon programme via éclipse, je dois mettre ça où.

  11. #11
    Membre éclairé
    Inscrit en
    Décembre 2005
    Messages
    50
    Détails du profil
    Informations forums :
    Inscription : Décembre 2005
    Messages : 50
    Par défaut
    dans eclipse il faut aue tu fasses :
    click droit sur ton projet
    --> properties
    --> Run/Debug settings

    puis que tu configures les differents champs pour que ton application s'execute suivant ta volonte.

    Dans l'onglet arguments tu as un chanmp VMarguments c'est la qu'il faut mettre la commande.

  12. #12
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2008
    Messages
    43
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 43
    Par défaut
    Peut-être qu'en utilisant la classe "RandomAccessFile" tu peux faire une gestion plus fine de tes fichiers (avec la fonction seek(long) tu peux simuler des pointeurs) et ne pas être obligé de lire et d'écrire complètement un fichier à chaque nouveau mot.
    Entre autres, si tes fichiers reflètent la structure du "burst tree".


    Si ça peut être une piste

  13. #13
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    40
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 40
    Par défaut
    Merci baos
    ça fait longtemps que je ne suis pas passé, je n'avais pas encore vu ta réponse.

    Le problème c'est que je dois testé si le mot que je veux entrer est déjà dans le Fichier et dans ce cas le trouver pour ajouter les offsets de début et fin de ce mot à sa liste d'occurrences.

    Je suis encore sur ce problème en ce moment car l'argument à mettre dans la VM java -Xmx 256m monProg ne suffisait pas pour le texte de 100Mo que je dois essayer de traiter

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

Discussions similaires

  1. [Free Pascal] [TList] Tri avec Sort
    Par Neuromancien2 dans le forum Free Pascal
    Réponses: 0
    Dernier message: 21/05/2010, 17h16
  2. Tri avec sort par date et heure
    Par oumokhtar dans le forum Shell et commandes GNU
    Réponses: 4
    Dernier message: 08/09/2009, 01h22
  3. tri (fonction Sort)
    Par RéviAT dans le forum Macros et VBA Excel
    Réponses: 6
    Dernier message: 25/03/2008, 11h24
  4. help fonction tri bubble sort
    Par Invité dans le forum C
    Réponses: 10
    Dernier message: 22/12/2005, 20h54
  5. Pb de tri avec "sort"
    Par blueice dans le forum Langage
    Réponses: 2
    Dernier message: 20/10/2005, 12h19

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