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

C++ Discussion :

Cross table ou tableau croisés


Sujet :

C++

  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 16
    Points : 9
    Points
    9
    Par défaut Cross table ou tableau croisés
    --Bonjour à tous et toutes,

    j'ai un problème à résoudre en C ou C++, je l'ai en partie résolu pour une petite quantité de
    données, mais çà plante dès que la taille du fichier augmente.
    Il s'agit de construire des tableaux croisés (ou table pivot)

    Voilà un exemple:

    contenu du fichier texte à traiter (ce n'est qu'un echantillon):

    librairies etiquettes scores
    GSM1 AAAAAAAAAA 17
    GSM1 AAAAAAATCA 1
    GSM1 AAAAAAATTT 1
    GSM1 AAAAACAAAA 1
    GSM10419 AAAAAAAAAA 54
    GSM10419 AAAAAAAAAC 2
    GSM10419 AAAAAACTAC 1
    GSM10419 AAAAAACTCC 2
    GSM10419 AAAAAACTGA 1
    GSM10419 AAAAAAGAAA 3
    GSM10419 AAAAAAGGCA 14
    GSM10424 AAAAACATAG 1
    GSM10424 AAAAACATCC 1
    GSM10424 AAAAACCAAA 1
    GSM10424 AAAAACCTAC 1
    GSM10425 AAAAAAAAAA 15
    GSM10425 AAAAAAAAAG 2
    GSM10425 AAAAAAAAAT 1
    GSM10425 AAAAAAAGAA 1
    GSM10425 AAAAAAAGAG 4

    format du fichier resultat a obtenir apres traitement:

    etiquettes GSM1 GSM10419 GSM10424 GSM10425
    AAAAAAAAAA 17 54 0 15
    AAAAAAAAAC 0 2 0 0
    AAAAAAAAAG 0 0 0 2
    AAAAAAAAAT 0 0 0 1
    AAAAAAAGAA 0 0 0 1
    AAAAAAAGAG 0 0 0 4
    AAAAAAATCA 1 0 0 0
    AAAAAAATTT 1 0 0 0
    AAAAAACTAC 0 1 0 0
    AAAAAACTCC 0 2 0 0
    AAAAAACTGA 0 1 0 0
    AAAAAAGAAA 0 3 0 0
    AAAAAAGGCA 0 14 0 0
    AAAAACAAAA 1 0 0 0
    AAAAACATAG 0 0 1 0
    AAAAACATCC 0 0 1 0
    AAAAACCAAA 0 0 1 0
    AAAAACCTAC 0 0 1 0

    je travaille sur une machine 64 bits, donc écrire du code 64 bits serait une optimisation.
    Si quelqu'un a déjà eu ce genre de problème à traiter, un petit coup de pouce serait le bienvenu, merci.

  2. #2
    Rédacteur
    Avatar de 3DArchi
    Profil pro
    Inscrit en
    Juin 2008
    Messages
    7 634
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2008
    Messages : 7 634
    Points : 13 017
    Points
    13 017
    Par défaut
    Salut,
    Quel est ton problème exactement : tu veux une correction à ton code existant (au quel cas il faut le poster) ou tu cherches une solution ?

  3. #3
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 16
    Points : 9
    Points
    9
    Par défaut cross table
    je suis à la recherche d'une solution plus rapide que ma ma solution empirique
    qui utilisent le stockage de valeurs dans des fichiers intermédiaires, du coup pour un nombre de données importantes çà rame à mort.

  4. #4
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 16
    Points : 9
    Points
    9
    Par défaut
    en premier je tri le fichier d'entrée suivant la première colonne(librairies) par:
    sort +0 -1 fichier1.txt > fichier2.txt

    ensuite je le tri suivant la deuxième colonne(etiquettes) par:
    sort +1 -2 fichier2.txt > fichier3.txt

    Ensuite affectation d'un numéro à chaque etiquette, récupèration du nombre d'etiquettes dans le fichier nb_tags.txt puis écriture de toutes les etiquettes distinctes dans le fichier tag.txt, ces fichiers seront utilisés par le programme C.
    Pour faire çà j'utilise sous Unix une ligne de commande en awk:

    awk '{if($2 != prev){prev=$2;cpt++;print $1,cpt,$3;liste_tag[cpt]=$2}else{prev=$2;print $1,cpt,$3}}END{for(i=1;i<=cpt;i++) {print liste_tag[i] > "tag.txt"};print cpt > "nb_tags.txt"}' fichier3.txt > fichier.txt

    je récupère le nombre de librairies differentes dans un fichier(nb_libs.txt):
    awk '{if(!($1 in gsms)){gsms[$1];cpt++}}END{print cpt > "nb_libs.txt"}' fichier2.txt

    enfin execution du programme C appelé matrice:
    ./matrice fichier2.txt


    code du programme C:


    Code C/C++ :
    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
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
     
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
     
    int main(int argc , char * argv[]) {
     
      FILE * pfile_matrice;
      FILE * pfile_nb_libs;
      FILE * pfile_gsm;
      FILE * pfile;
      FILE * pfile_nb_tags;
      FILE * pfile_libs;
      FILE * pfile_tag;
     
      int i ,freq, nb_libs, nb_tags, num_tag, num_lib, j;
      int ** frequences;
      char buffer_nom_lib[10];
      char compare[10];
      char * commande;
      char buffer_sequence[18];
     
     if (argc != 2 )
       {
        printf("il manque le nom du fichier à traiter!\n");
        exit(1);
       }
     
     //allocation de mémoire et initialisation des variables
     commande = (char *)malloc(100 * sizeof(char));
     strcpy(compare , "");
     num_lib = 0;
     num_tag = 0;
     j = 0;
     nb_libs= 0;
     
     //ouverture des fichiers 
     pfile = fopen(argv[1], "rb");
     pfile_libs = fopen("noms_libs.txt","w+");
      pfile_matrice = fopen("matrice.txt","w+");
     fprintf(pfile_matrice, "Tag_sequence " ) ;   //impression de l'entete
     
     //récupération du nombre de tags et du nombre des librairies
     pfile_nb_tags = fopen("nb_tags.txt", "rb");
      fscanf(pfile_nb_tags, "%d", &nb_tags);
      fclose(pfile_nb_tags);
      pfile_nb_libs = fopen("nb_libs.txt", "rb");
      fscanf(pfile_nb_libs, "%d", &nb_libs);
      fclose(pfile_nb_libs);
     
      //allocation de mémoire pour tableau d'entiers de dimension 2 qui va contenir la matrice
      frequences = (int ** )malloc(nb_libs*sizeof(int *));
      for (i =0; i <nb_libs; i++)
        {
          frequences[i] = (int *) malloc (nb_tags*sizeof(int)); 
        }
     
      //parcours du fichier de manière à reconnaitre les diffèrentes librairies
      while(!feof(pfile))
        {
          fscanf(pfile, "%s", buffer_nom_lib);     
          fscanf(pfile, "%s " ,buffer_sequence);      
          fscanf(pfile, "%d" ,&freq);
               //isolement de chaque librairies
          if(strcmp(buffer_nom_lib, compare))
    	{
    	 memset(commande,0,100);
    	 num_lib++;
     
    	 //recuperation des noms de lib et de leurs indices dans le fichiers noms_libs.txt	 
    	 fprintf(pfile_libs, "_%d ----> %s\n", num_lib, buffer_nom_lib);
    	 if( num_lib == nb_libs )
    	 fprintf(pfile_matrice, "_%d\n", num_lib );
    	 else 	 fprintf(pfile_matrice, "_%d ", num_lib );
     
    	 //recuperation d'un sous fichier contenant tous les tags se trouvant dans la librairies
    	 strcpy(commande, "grep -w ");
    	 strcat(commande, buffer_nom_lib);
    	 strcat(commande, " fichier.txt > gsm.txt");
    	 system(commande); //appel systeme de la commande grep : grep -w nom_lib fichier.txt > gsm.txt
     
    	 //initialisation de la ligne du tableau correspondant a la librairie à 0, cela permet d'avoir une frequence nulle pour les tags qui ne se trouvent pas dans la librairie  
    	 for(i = 0 ; i< nb_tags; i ++)
    	   {   
    	     frequences[num_lib-1][i]= 0; 
    	   }
     
    	 //ouverture du sous fichier et remplissage de la ligne du tableau corrspondant à la librairies
    	 pfile_gsm = fopen("gsm.txt", "rb");
     
    	  while(!feof(pfile_gsm))
    	    {
    	      fscanf(pfile_gsm,"%s", buffer_nom_lib);
    	      fscanf(pfile_gsm,"%d", &num_tag);
    	      fscanf(pfile_gsm,"%d", &freq);
     
    	      frequences[num_lib-1][num_tag-1] = freq; 
    	    }
    	  fclose(pfile_gsm);
    	}
     
          memset(compare, 0, 10);
          strcpy(compare, buffer_nom_lib) ;
        }
     
      //affichage du nb de lib et de tags
      printf("nb_libs : %d\n", nb_libs);
      printf("nb_tags : %d\n", nb_tags);
     
      // ecriture du tableau dans le fichier matrice.txt
     
      pfile_tag = fopen("tag.txt", "rb");
      for(i = 0; i < nb_tags; i ++)
        {
               fscanf(pfile_tag, "%s", buffer_sequence);
          fprintf(pfile_matrice, "%s ", buffer_sequence);
          for(j = 0; j < nb_libs-1; j++)
    	{
    	  fprintf(pfile_matrice,"%d ", frequences[j][i] );
     
    	}
          fprintf(pfile_matrice,"%d\n", frequences[nb_libs-1][i] );
        }
     
      //fermeture des fichiers et liberation de la mémoire
      fclose(pfile_matrice);
      fclose(pfile);
      fclose(pfile_libs);
      fclose(pfile_tag);
      for (i= 0 ; i < nb_libs; i++)
        {free(frequences[i]);}
      free(frequences);
     }

  5. #5
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 612
    Points : 30 612
    Points
    30 612
    Par défaut
    Salut,

    Déjà, le code que tu présente ici est exclusivement écrit en C...

    Si c'est une réponse C que tu souhaite, fais le nous savoir, car il faudra que nous déplacions la discussion (on peut le faire )

    Ensuite, tu n'a absolument pas besoin de passer par cinq ou six fichiers différents, tu peux tout à fait maintenir tes informations en mémoire le temps de les trier et ne les réécrire qu'une seule fois dans le fichier de destination, une fois qu'elles auront été complètement triées.

    L'idée générale (que ce soit en C ou en C++) est de créer une structure qui puisse représenter les différentes valeurs que tu retrouve dans le fichier.

    Visiblement, tu as besoin de trois informations particulières:
    1. une chaine de caractères
    2. un tableau d'entiers permettant de savoir de quel gsm on parle (ce qui, dans le fichier est représenté par GSM1, GSM10419 ou GSM10425) qui sera mis en relation avec
    3. un tableau d'entiers représentant le score.

    En C, il faudrait donc créer un structure supplémentaire regroupant les information (2) et (3).
    En C++, nous pourrions très bien envisager des classes proches de
    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
    class ScoreByGSM
    {
        typedef std::map<int, int> map;
        public:
            typedef typename map::const_iterator const_iterator;
            void addScore(int gsm, int score)
            {
                items.insert(std::make_pair(gsm,score));
            }
            const_iterator begin() const{return items.begin();}
            const_iterator end() const{return items.end();}
        private:
            map items;
    };
    class StringScoresMap
    {
        typedef std::map<std::string, ScoreByGsm> map;
        public:
            StringScoreMap():maxgsm(0){}
            typedef typename map::iterator iterator;
            typedef typename map::const_iterator const_iterator;
            bool stringExists(std::string const & str)
            {
                return items.find(str)!=items.end();
            }
            iterator findOrInsert(std::string const & str)
            {
                if(!stringExists(str))
                    items.insert(std::make_pair(str,ScoreByGsm());
                iterator it=items.find(str);
                return it;
            }
            const_iterator begin() const{return items.begin();}
            const_iterator end() const{return items.end();}
            /* si les numéro de gsm sont consécutifs et doivent tous apparaitre,
             * ce sera utile :D
             */
           void updateMaxGsm(unsigned int newval)
           {
               if(maxgsm<newval)
                   maxgsm=newval;
           }
           unsigned int maxGsmValue() const{return maxgsm;}
        private:
            unsigned int maxgsm;
            map items;
    };
    Nous aurions une fonction de lecture du fichier qui prendrait une forme proche de
    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
    /* fonction de lecture d'un fichier
     *  @in : nom du fichier à lire (pour le cas où il y en aurait plus d'un
     *  @in / ou : la structure à mettre à jour
     */
     
    void readFromFile(std::string const & filename, StringScoreMap & values)
    {
        /* ouverture du fichier */
        std::ifstream ifs(filename.c_str());
        /* Si l'ouverture ne se fait pas, on a un problème :P */
        if(! ifs)
            throw CantOpenFile(); // a définir par ailleurs :D
        /* nous avons besoin d'une chaine de caractère pour lire chaque ligne
         * du fichier
         */
        std::string temp;
        /* tant que nous arrivons à lire une ligne dans le fichier */
        while(std::getline(ifs,temp))
        {
            /* nous en supprimons les trois premiers caractères ("GSM") qui
             * ne nous intéressent pas
             */
           temp=temp.substr(3);
           /* nous créons un flux de conversion contenant le résultat */
           std::stringstream ss;
           ss<<temp;
           /* nous avons besoin de deux entiers (l'identifiant du GSM et le score)
            * et d'une chaine de caractères
            */
           int gsm;
           int score;
           std::string str;
           /* que nous lisons depuis le flux de conversion 
            * Si cela ne fonctionne pas, le fichier est corrompu
            */
           if(!(ss>>gsm>>str>>score)
              throw CorruptedFild(); // a définir par ailleurs
           /* nous cherchons la chaine parmi l'existant (si elle n'existe pas, 
            * fonction la crée et l'insere :D )
            */
          StringScoreMap::iterator it= values.findOrInsert(str);
          /* nous rajoutons le score correspondant au gsm */
          (*it).second.addScore(gsm,score);
          /* et nous mettons à jour le numéro maximum de gsm, s'il échoit */
          values.updateMaxGsm(gsm);
        }
    }
    Comme le but est quand même de créer un fichier de destination, nous aurions une fonction qui s'en chargerait... Elle prendrait une forme proche de
    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
    /* fonction d'écriture dans un fichier
     *  @in : nom du fichier à créer(pour le cas où il y en aurait plus d'un)
     *  @in : la structure à mettre à écrire
     */
    void writeToFile(std::string const & filename, StringScoreMap const & values)
    {
        /* ouvrons le fichier */
        std::ofstream ofs(filename.c_str());
        /* si l'ouverture échoue, on a un problème :P */
        if(! ofs)
            throw CantOpenFile();
        /* nous pouvons créer des "titres" pour les colones... */
        ofs<<std::setfill(12)<<valeur;
        for(unsigned int i=1;i<values.maxGsmValue();++i)
            ofs<<"GSM"<<std::setfill(6)<<i;
        ofs<<std::endl;
        /* pour chaque valeur à écrire */
     
        for(StringScoreMap::const_iterator it=values.begin();it!=values.end();
            ++it)
        {
            /* nous écrivons la chaine de caractères correspondante */
            ofs<<setfill(11)<<(*it).first;
            /* nous récupérons les scores... mais nous devons garder
             * l'identifiant du gsm du dernier score inscrit
             */
           unsigned int last=1;
           for(ScoreByGSM::const_iterator scoreit=(*it).second.begin();
               scoreit!=(*it).second.end(); ++scoreit)
           {
               /* si l'identifiant du gsm actuel ne suit pas directement 
                * celui du dernier score inscrit, nous écrivons la valeur 0
                * pour tous les identifiants qui séparent le dernier score inscrit
                * et le score en cours
                */
               if((*scoreit).first!=last+1)
               {
                   for(unsigned int i=last+1;i<(*scoreit).first;++i)
                       ofs<<std::setfill(9)<<'0';
               }
               /* nous écrivons le socre en cours */
               ofs<<std::setfill(9)<<(*scoreit).second;
               /* nous mettons l'identifiant du dernier score inscrit à jour */
               last=(*scoreit).second;
           }
           /* Si l'identifiant du gsm auquel correspond le dernier score inscrit
            * n'est pas celui du dernier gsm, nous écrivons 0 pour tous les
            * gsm restant
            */
          if(last!= values.maxGsmValue()
          {
              for(unsigned int i=last+1;i!=values.maxGsmValue()+1;++it)
                  ofs<<std::setfill(9)<<'0';
          }
          /* et nous passons à la ligne */
          ofs<<std::endl;
        }
    }
    La fonction principale pourrait alors prendre la forme simple de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    int main()
    {
        /* nous pourrions demander à l'utilisateur de préciser le nom des fichiers ;-)
         */
        StringScoreMap items;
        readFromFile("fichier_d_entree.txt",items);
        writeToFile("fichier_de_sortie.txt",items);
    }
    NOTA:
    1- il existe bien d'autres solutions, mais comme tu ne semble pas matriser ni C, ni C++, il ne me semble pas opportun d'aller chercher beaucoup plus loin
    2- Le code a été écrit "from scratch" et n'a pas été testé... quelques erreurs d'attention sont possibles
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  6. #6
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 16
    Points : 9
    Points
    9
    Par défaut déplacement dans le forum C
    tu as raison, autant déplacer cette discussion dans le forum C, çà sera plus
    approprié.
    Merci pour ton aide.

    PS: en fait dans le code inutile de supprimer "GSM", on en a besoin dans le résultat

  7. #7
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 612
    Points : 30 612
    Points
    30 612
    Par défaut
    Citation Envoyé par mslider Voir le message
    tu as raison, autant déplacer cette discussion dans le forum C, çà sera plus
    approprié.
    Merci pour ton aide.

    PS: en fait dans le code inutile de supprimer "GSM", on en a besoin dans le résultat
    A vrai dire, GSM est une chaine de caractères constante, qui n'intervient pour ainsi dire absolument pas dans le tri, et qui, au contraire, est de nature à poser problème lors du tri, seule la valeur numérique qui suit ces trois lettres étant significative.

    c'est la raison pour laquelle je prend, purement et simplement, l'option d'ignorer ces trois caractères, mais de les rajouter lors de l'écriture dans le fichier
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  8. #8
    Invité
    Invité(e)
    Par défaut
    Ton problème n'est pas un problème de tableau croisé, mais juste d'affichage. Chaque case de ton tableau est déjà calculée (ce sont les scores), mais le tableau est actuellement présenté "à plat" (c'est à dire chaque case dans une ligne indexée par son numéro de ligne et de colonne.

    Comme ton fichier a autant de lignes qu'il y a de cases dans le tableau, si toutes ces données ne tiennent pas en mémoire, la meilleure solution est effectivement de trier le fichier (ce que tu peux faire sans le charger en mémoire tout entier), selon l'ordre "index des lignes, index des colonnes".

    En écrivant correctement l'opérateur de comparaison, il n'y a qu'un tri à faire. Par exemple, tu pourrais commencer par echanger les deux premiers champs et les concaténer (avec awk par exemple). Un sort sur le résultat, et hop...

    Une fois le fichier trié, tu le lis dans l'ordre, d'abord, toutes les colonnes de la première ligne, puis la seconde, etc... Tu peux faire du C, du C++ ou de l'AWK à ce niveau... (à mon avis, awk suffit largement)

    Koala, ta méthode fondée sur des maps est juste en théorie, mais elle impose de charger toute la donnée en mémoire, et avec des insertions successives dans une map (indexée sur des paires de string). A vue de nez, c'est quadratique. Avec de gros fichiers, ca risque d'être un rien lent...

    Si toutes les données tiennent en mémoire, il vaut mieux les charger dans un vector<pair<pair<string,string>,int> (en inversant les colonnes pour que le "tri naturel" sur les paires fasse ce qu'on veut qu'il fasse...), et en appelant sort() sur celui ci... On sera alors log linéaire et certainement moins gourmand en mémoire.

    Francois
    Dernière modification par Invité ; 26/01/2010 à 21h59.

  9. #9
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 16
    Points : 9
    Points
    9
    Par défaut pas si facile que çà
    oui j'avais fais un programme en awk à l'époque pour résoudre ce problème, çà marche bien pour un
    petit fichier comme sample.txt(10000 entrées), mais pour plus gros il faut attendre, attendre et encore attendre, voir une journée de traitement.

    mon code AWK:

    #!/usr/bin/awk -f
    BEGIN { FS = " " ; ORS = "" }
    { if ( ! ($1 in gsms) )
    { gsms[ $1 ]
    gsm_seq[ ++gcount ] = $1
    }
    if ( ! ($2 in tags) )
    { tags[ $2 ]
    tag_seq[ ++tcount ] = $2
    }
    data[$2,$1] = $3
    }
    END {
    delete gsms
    delete tags
    for (i=0; i <= tcount; i++)
    { tag = tag_seq[i]
    print i ? tag : "etiquettes"
    for (j=1; j in gsm_seq; j++ )
    { gsm = gsm_seq[j]
    print " " (i ? (0 + data[tag,gsm]) : gsm )
    delete data[tag,gsm]
    }
    print "\n"
    }
    }

    Tiens voilà le temps de calcul pour traiter le fichier sample.txt:

    1.516u 0.024s 0:01.54 99.3% 0+0k 0+0io 0pf+0w

    mais que ce soit du code awk ou C l'algo c'est du n2 car on parcourt 2 boucles FOR imbriquées, donc le temps de traitement grimpe en flèche avec l'augmentation des données à traiter.
    Il faut penser autrement l'algo pour lever le verrou du n2.

    mslider.

  10. #10
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 16
    Points : 9
    Points
    9
    Par défaut fichier sample.txt
    oui j'ai oublié de vous dire que le fichier sample.txt est accessible ici:
    http://dl.free.fr/odeiETLzW

Discussions similaires

  1. Cross-table ou matrix
    Par zinabd dans le forum Designer
    Réponses: 0
    Dernier message: 19/10/2008, 13h20
  2. Copie de valeurs d'un tableau croisés dynamique
    Par Esteban79 dans le forum Macros et VBA Excel
    Réponses: 5
    Dernier message: 28/01/2008, 21h36
  3. tableau croissé dynamique
    Par andre55 dans le forum Excel
    Réponses: 1
    Dernier message: 12/10/2007, 05h44
  4. table des références croisés
    Par cyclone_yas dans le forum Oracle
    Réponses: 2
    Dernier message: 23/01/2007, 18h03
  5. Requete sur table avec Tableau
    Par Sichagadel dans le forum Langage SQL
    Réponses: 3
    Dernier message: 08/11/2005, 14h05

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