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 :

Quelle structure de données ? Analyse des occurrences d'un trigramme


Sujet :

Algorithmes et structures de données

  1. #41
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Tidus159 Voir le message
    je n'ai pas compris pourquoi tu splittais les trigrammes en 256 fichiers ? Et ce que tu appelles un hashcode ? (après une recherche, cela semble être un identifiant d'un objet ?)
    J'ai splitté dans des fichiers en utilisant le hashcode pour 2 raisons:

    1. Le hascode répartit a peu près uniformément les trigrammes dans les fichiers. Chaque fichier fait a peu près 2Mo ce qui me permet de pouvoir traiter chaque fichier en mémoire, en utilisant une hashmap pour compter les occurences des trigrammes.

    2. Je suis sur que les fichiers sont disjoints, c'est a dire qu'un trigramme "a|b|c" ira toujours dans le meme fichier. Donc quand j'aurais compté les occurences de "a|b|c" dans ce fichier, je peux directement ajouter une entrée dans le fichier final.

    Voila ce que j'ai fait:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    Fonction pass1(fichier_source)
     
      Créer les 256 fichiers: partfile[i] pour i=0...255
     
      Pour chaque trigramme dans fichier_source
        calculer le hashcode du trigramme
        prendre l'octet de poids faible : num=(hash & 0xFF)
        ecrire le trigramme à la fin du fichier partfile[num]
      Fin Pour
     
    Fin Fonction
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    Fonction pass2(fichier_final)
     
      Créer fichier_final 
      Créer une HashMap<String, Integer>
     
      Pour chaque fichier partfile[i] avec i=0...255
     
        vider la HashMap
     
        Pour chaque trigramme dans le fichier partfile[i]
          Créer/Incrémenter la valeur correspondant à la clé "trigramme" dans la HashMap
        Fin Pour
     
        Pour chaque entrée dans la HashMap
          ecrire la clé + l'occurence dans fichier_final
        Fin Pour
     
      Fin Pour
     
    Fin Fonction
    Tiens tu as codé en java, tu sais peut être quel est l'objet qui pourrait remplacer mon tableau pour stocker les mots ? (ce que tu ne fais pas je crois...)
    Non, je ne créé pas d'index pour les mots. Je n'en ai pas besoin et ca necessiterait une 3eme passe dans mon algo.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #42
    Membre actif
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    311
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 311
    Points : 257
    Points
    257
    Par défaut
    Merci pour cet algorithme.

    Je viens de finir de l'implémenter et en le lançant sur le petit texte horla.txt (100Ko) mon programme met 1 min...
    Programme de test.
    Durée de création des fichiers: 145 millisecondes.
    Durée de pass1 : 52656 millisecondes.
    Durée de pass2 : 317 millisecondes.
    Durée total du programme: 52975 millisecondes.
    Obtiens tu la même chose ?
    Je lance le programme sur les livres de Jedai, j'édite après....

    @+,
    Tid.

  3. #43
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par Tidus159 Voir le message
    Merci pour cet algorithmique.

    Je viens de finir de l'implémenter et en le lançant sur le petit texte horla.txt (100Ko) mon programme met 1 min...

    Obtiens tu la même chose ?
    Tu manques de sens des proportions...

    Tu mets 50s pour la première passe de l'algorithme sur 100ko, Pseudocode met 150s = 2m30s (3x) pour la même passe sur 260Mo (2600x)... Or cette passe est définitivement de complexité linéaire par rapport à la taille du texte au minimum.

    Donc ton code mettra au moins 2600x50 = 130000s = 36h6m40s pour traiter 260Mo.

    Il est donc évident qu'il y a quelque chose qui cloche sérieusement dans ton implémentation.

    --
    Jedaï

  4. #44
    Membre actif
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    311
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 311
    Points : 257
    Points
    257
    Par défaut
    Depuis le début c'est cette parti qui semble tout me ralentir...... pourtant mon implémentation semble correct !

    La voici (c'est en java) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    	public void pass1(String s) throws IOException{
     
    		long time1 = System.currentTimeMillis();
    File f = new File("C:/Users/Emilien/Desktop/eclipseWorkspace/complexite/parts"+s+"/partfile");
    		File p = f.getParentFile();
    		if (!p.exists())
    			  p.mkdirs();
    		for (int i=0; i<256; i++){
    			File f2 = new File("C:/Users/Emilien/Desktop/eclipseWorkspace/complexite/parts"+s+"/partfile"+i);
    			if (!f2.exists())
    			f2.createNewFile();
    		}
     
    		long time2 = System.currentTimeMillis();
    		System.out.println ("Durée de création des fichiers: "+ Long.toString ((time2 - time1)) + " millisecondes.");
     
    //fin creation fichiers
    		BufferedReader LecteurBufferise = null;
    	    String ligneDonnee;   
    	    String Mot1="", Mot2="", Mot3="";
    		int hashCodeTrigramme=-1, octetPoidsFaible=-1;
    		boolean eof = false, debut1erMot=true, debut2emeMot=true;
    		MotMotMot m = new MotMotMot(Mot1, Mot2, Mot3);
        	ArrayList<String> part = new ArrayList<String>();
    	    try {
     
    	      //Ouverture du Fichier // le chemin est a modifier dans FileReader
    	      LecteurBufferise = new BufferedReader(new FileReader(s)); //s chemin
     
    	      while (eof != true) {
    	      //Lecture de la ligne
    	        ligneDonnee = LecteurBufferise.readLine();
    	        if (ligneDonnee != null) {
    	        	// on split chaque ligne en utilisant une regex
    	        	String[] part1=ligneDonnee.split("[ \t\n]");
     
    	        	int longueurPart1 = part1.length;
    	        	for (int i=0; i<longueurPart1; i++){
    	        		if(!part1[i].equals("")) part.add(part1[i]);
    	        	}
    	        	int longueurPart = part.size();
     
    	        	// pour chaque mot de la ligne
    	        	for (int k=0; k<longueurPart; k++ ){
     
    	        		// premier cas : on est au debut du fichier
    	        		if (debut1erMot) {
    	        			Mot1 = part.get(k);
    	        			debut1erMot = false;
    	        		}
    	        		// on est au deuxieme mot
    	        		else if (debut2emeMot) {
    	        			Mot2 = part.get(k);
    	        			debut2emeMot = false;
    	        		}
    	        		else {
    	        		// dans tous les autres cas
    	        			Mot3 = part.get(k);
    	        			m.setMot1(Mot1); m.setMot2(Mot2); m.setMot3(Mot3);
    	        			hashCodeTrigramme = m.hashCode();
    	        			octetPoidsFaible = hashCodeTrigramme&0xFF;
    	        			ecrireDansFichier(s, octetPoidsFaible, m);
    	        			Mot1 = Mot2;
    	        			Mot2 = Mot3;
    	        			Mot3= "";
    	        		}     			
    	        	}
    	        	part.clear();
    	        }
    	        else {
    	          eof = true;
    	        }
    	      }
    	    }
    	    catch (FileNotFoundException ex) {
    	      System.out.println("Fichier non trouvé !!");
    	    }
    	    catch (IOException ex) {
    	      System.out.println("Erreur lecture ligne fichier !!");
    	    }
    	    finally {
    	      try {
    	        LecteurBufferise.close();
    	      }
    	      catch (IOException ex1) {
    	        System.out.println("Erreur fermeture fichier !!");
    	      }
    	    }
    	}
     
    public void ecrireDansFichier(String s, int numFichier, MotMotMot trig) throws IOException{
    		PrintWriter sortie =  new PrintWriter(new BufferedWriter(new FileWriter("C:/Users/Emilien/Desktop/eclipseWorkspace/complexite/parts"+s+"/partfile"+numFichier, true)));
    		sortie.println(trig); 
    		sortie.close();
    	}
    Je ne vois pas du tout ce qui peut clocher...
    Le pire c'est que depuis le début, je n'ai pas beaucoup changer la structure de cette lecture du fichier

    [EDIT] Après 2 h de traitement du programme sur le fichier des 22 livres, je l'arrête...... J'comprends vraiment pas...

  5. #45
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Bon déjà ouvrir/refermer un fichier à chaque écriture est peu susceptible d'aider niveau vitesse... D'autre part la partie lecture est horriblement et probablement inutilement compliquée, je suspecte qu'elle est aussi fort inefficiente mais j'avoue ne pas avoir eu le courage de me plonger dans la masse...

    Note que toute ta partie lecture est globalement équivalente à :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    main = do trigramsList <- liftM (trigrams . words) getContents
     
    trigrams (a:b:ws) = go a b ws
      where
       go a b (c:ws) = (a,b,c) : go b c ws
       go _ _ _ = []
    trigrams _ = []
    en Haskell...

    Il doit donc y avoir moyen de faire plus simple en Java aussi, non ?

    --
    Jedaï

  6. #46
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Bon déjà ouvrir/refermer un fichier à chaque écriture est peu susceptible d'aider niveau vitesse...
    +1. Les I/O sont plutot long en Java, donc il vaut mieux ouvrir les 256 fichiers avant d'entrer dans la boucle principale (en sockant les BufferedWriter dans un tableau), et en les fermant tous en sortant de la boucle.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #47
    Membre actif
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    311
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 311
    Points : 257
    Points
    257
    Par défaut
    Bonsoir,

    résultat :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Programme de test.
    Durée de création des fichiers: 216 millisecondes.
    Durée de pass1 : 166882 millisecondes.
    Durée de pass2 : 91655 millisecondes.
    Et voici le trigramme vainqueur avec le plus d'occurrences : 225316|229476|164156=>155874
    :-) !
    Super, merci à tous de votre aide !
    J'ai compris et expérimenté plein de choses grâce à vous, et finalement obtenu un résultat plus que satisfaisant !

    C'était mon premier exercice sur un "projet industriel" et c'est très enrichissant !

    @+,
    Tid.

    [résolu]

+ Répondre à la discussion
Cette discussion est résolue.
Page 3 sur 3 PremièrePremière 123

Discussions similaires

  1. Quelle structure de données pour mon projet ?
    Par stallaf dans le forum Langage
    Réponses: 4
    Dernier message: 13/04/2010, 17h12
  2. [MySQL] Quelle structure choisir pour commentaires des articles
    Par Happy dans le forum PHP & Base de données
    Réponses: 5
    Dernier message: 17/11/2008, 16h41
  3. Quelle structure de données ?
    Par SebSplo dans le forum Développement 2D, 3D et Jeux
    Réponses: 5
    Dernier message: 27/01/2008, 03h52
  4. quelle structure de donnée par un arbre?
    Par rdh123 dans le forum C#
    Réponses: 1
    Dernier message: 31/12/2007, 15h27
  5. [C++] quelle structure de donnée utiliser pour stocker des vertices ?
    Par johnnyjohnny dans le forum Développement 2D, 3D et Jeux
    Réponses: 14
    Dernier message: 14/07/2007, 21h44

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