Tableaux croisés

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010 - 25 janv. 2010 à 12:30
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 - 25 févr. 2010 à 16:23
--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.

142 réponses

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
25 janv. 2010 à 16:56
Bonjour,

Si ça se plante, c'est qu'il y a une erreur dans un dimmensionnement ou une allocation de mémoire.

Montre donc ton code si tu veux te le faire corriger.

Mais tu auras du mal à trouver une bonne âme pour te donner une solution toute crue.


thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
25 janv. 2010 à 17:56
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:

#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);
 }
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
25 janv. 2010 à 18:55
Ce n'est donc pas que du C !

Remarque : pour compter le nombre de mot différent, tu peux extraire une colonne, en pipe sur sort -u | wc -l > ton fichier contenant le compte.

tu peux aussi l'éviter en lisant ton fichier 2 fois, sans trier avec un fonction de recherche dans le tableau (ça va pour des petites quantités de lignes); la 1ere lecture pour obtenir les tailles max des mots et le nombre.

Après lecture de ton code, je ne vois que tu ne fais rien en else de
if(strcmp(buffer_nom_lib, compare))

Ca se plante comment ?
- résultat erroné
- bus error ...
...

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
25 janv. 2010 à 21:06
j'utilise des tris avant de lancer mon programme C car les listes sont longues.
les sort en eux mêmes ne plantent pas que ce soient des fichiers de 10000 lignes ou plus.
Par contre le programme C plante dès que le nombre de lignes devient important.
Pour un fichier de 10000 lignes çà marche bien, par contre pour 1000000 de lignes:

> segmentation fault et generation d'un fichier core.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
26 janv. 2010 à 10:21
Si le programme fonctionne pour des "petits" nombre alors on va dire que l'algorithme est bon.
Reste alors les débordements de mémoire (avec ou sans corruption de variables) et dépassement de capacité.
Entre 10 000 et 1 000 000 il y a le classique 32768
Ton int est 64 bits non ?
Combien valent nb_tags et nb_libs quand ça se plante ?
Sais-tu à quel endroit ça se plante ? pour un même fichier en entrée, systèmatiquement dans la même partie de programme ou un peu n'importe où ?
Tu as bien vérifié que tes buffers sont assez bien dimensionnés ? (valeur maxi des tailles de texte)

Dans le fichier de 1 000 000 il y a peut-être des saletés qui n'existe pas dans les plus petits.

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
26 janv. 2010 à 10:50
je sais pas exactement, je vais regarder çà de plus près.
je laisse un echantillon de fichier à traiter ici: http://dl.free.fr/odeiETLzW

pour ceux qui auraient une autre approche et qui voudraient essayer de résoudre le cross table.
Je vais aussi regarder sur le site de Microsoft, le cross table existe dans excel, il se peut que l'algo existe
en VBA.

à tout
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
26 janv. 2010 à 11:18
Tu peux aussi mettre ça dans une base MySQL ou Access et faire une requête SQL


thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
26 janv. 2010 à 11:27
déjà essayer: beaucoup trop long, le SQL c bien mais en terme de rapidité c pas encore çà.
le but c'est de faire le cross table en premier sur un fichier à plat puis d'incorporer le résultat dans une table de BD.
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
26 janv. 2010 à 12:00
Le fichier test comporte une ligne blanche vers le milieu : ton code ne dois pas apprécier.

thip
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
26 janv. 2010 à 12:30
je ne trouve que :
fscanf(pfile, "%s " ,buffer_sequence);
l'espace est en trop dans le format : 17 caractères en entrée (dans le sample.txt), +espace + \0 = 19 caractères et ton buffer est à 18

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
26 janv. 2010 à 12:31
oui en effet.
j'ai supprimé la ligne blanche et çà marche bien avec mon code, mais comme je le disais ce n'est qu'un echantillon d'un fichier qui à la base est plus gros. 10000 lignes c'est rien à traiter.
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
26 janv. 2010 à 16:42
Si c'est le résultat de ton C que tu veux mettre dans une base, tu risques d'avoir des soucis : ça fait beaucoup de champs.
Avec ton sample.txt, j'en compte déjà 312. Dont tu ne connais pas a priori le nom de colonne (à moins que la liste soit connue).
Tu es certain que c'est ce que tu veux ?

thip
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
26 janv. 2010 à 17:31
Plutôt qu'en C, essaie :

awk '{ lib[$2]; tag[$1]; c[$2,$1] = $3 }
END {
printf "etiquettes "
for (j in tag ) printf " %s", j
print ""

for (i in lib) {
  printf "%s", i
  for (j in tag) {
    printf " %d", c[i,j]
  }
  print ""
}

}' ./sample.txt


thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
26 janv. 2010 à 21:08
17 caractères en entrée, oui c vrai.
Mais parfois il peut y en avoir moins, des fois plus, bref la longueur de la ligne est variable.
Et c vrai aussi que je ne connais pas à l'avance le nombre de champs(de colonnes), mais c pas un souci, le problème réside en la construction de la matrice issue du cross table.
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
27 janv. 2010 à 08:00
As-tu assayé le awk ? il fonctionne bien avec ton sample.txt et permet de s'affranchir des contraintes du c. Mais je ne sais pas ce que ça peut donner avec de gros volumes. En tous cas, il évite de faire les sort et awk initiaux.

Pour le C : dimensionne tes buffers plutôt gros dès le départ, par exemple à 512. Un majorant absolu pour tes fichiers. Trop juste, c'est risquer la ruine du programme.

Sinon, tu reprends la conception de l'ensemble du code avec le principe du awk précédent.
En lisant le fichier en une passe :
- tu remplis un tableau char* des "etiquette" en évitant les doublons (donc fonction de recherche dans le tableau), en allouant au passage la mémoire nécessaire
- idem avec les "tag"
- un tableau int 2 dimensions, avec comme index ceux des 2 précédents tableaux,
et quand tu as terminé la lecture, tu affiche le tout.

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
27 janv. 2010 à 12:00
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, 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à les temps de calcul pour traiter le fichier sample.txt:

ton code awk: 1.252u 1.140s 0:02.39 100.0% 0+0k 0+0io 0pf+0w
le mien: 1.516u 0.024s 0:01.54 99.3% 0+0k 0+0io 0pf+0w
le code C: 1.280u 0.020s 0:01.30 100.0% 0+0k 0+0io 0pf+0w

mais que ce soit ton code ou le mien 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. Idem pour le code C.
Il faut penser autrement l'algo je pense pour booster le code.

mslider.
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
27 janv. 2010 à 14:31
Oui c'était mon inquiétude. Je pensais tout de même que mon awk ferait mieux que ça. Surtout par la suppression des sort/awk du départ. comme ton awk finalement. Awk doit utiliser des fichiers temporaires qui sont pénalisant (j'imagine, je n'en sait rien).
Le paquet de grep sur un gros fichier ne me parait pas performant.

Bon, en C je ferai comme indiqué dans mon message précédent, mais il faut optimiser les fonctions de recherche dans les tableaux.
En triant avec sort avant le C, tu économises une recherche. Après, il faut faire la recherche de colonne avec un hash, c'est rapide.

310 colonnes/10000 lignes = 10000 recherches parmi 310 valeurs. Si le nombre de colonne n'augmente pas trop pour le million de recherche, un btree peut être performant (tableau trié avec insertion des valeurs inconnues là où on aurait dû la trouver, comme d'hab) et tu trouves en 9 coup maxi chaque valeur (hash doit faire mieux)

Au fait, ton C se plante toujours ?


thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
27 janv. 2010 à 14:35
oui çà plante toujours et même s'il plantait pas çà serait trop long.
Il faut que je repense à une autre approche au niveau algo et que je code tout çà en C, çà sera tjs plus
performant que du awk surtout sur une machine 64bits.

merci qd même.
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
27 janv. 2010 à 18:33
Avant de quitter le boulot, j'ai joué à ton truc, voici ce que j'avais en tête pour un C, sans avoir à trier à l'avance :

#include <stdio.h>

typedef struct {
char **array;
int size;
int allocSize;
} ARR;

int findOrAddArray(char *item, ARR *arr)
{
int i, k;
int g 0, d arr->size-1;

while ( g <= d ) {
i = (g+d)/2;
k = strcmp(item, arr->array[i]);
if ( k == 0 )
return i;
if ( k < 0 )
d = i-1;
else
g = i+1;
}
i = g;

char ** p;
if ( arr->size == 0 )
{
p  = (char **) malloc(sizeof(char *)*arr->allocSize);
p[0] = malloc(strlen(item)+1);
strcpy(p[0], item);
arr->array = p;
}
else if ( arr->size == arr->allocSize )
{
arr->allocSize *= 2;
p  = (char **) malloc(sizeof(char *)*arr->allocSize);
if ( i > 0 )
memcpy(p, arr->array, sizeof(char *)*i);
p[i] = malloc(strlen(item)+1);
strcpy(p[i], item);
if ( i < arr->size )
memcpy(&p[i+1], &arr->array[i], sizeof(char *)*(arr->size-i));
free(arr->array);
arr->array = p;
}
else
{
p  = (char **) malloc(sizeof(char *)*arr->allocSize);
if ( i > 0 )
memcpy(p, arr->array, sizeof(char *)*i);
p[i] = malloc(strlen(item)+1);
strcpy(p[i], item);
if ( i < arr->size )
memcpy(&p[i+1], &arr->array[i], sizeof(char *)*(arr->size-i));
free(arr->array);
arr->array = p;
}
arr->size++;
return i;
}

main()
{
FILE *fp, *fpo;
ARR tag;
ARR gsm;

tag.size = 0;
tag.allocSize = 2000;
gsm.size = 0;
gsm.allocSize = 500;

char bufTag[512], bufGsm[512];
char prevTag[512];
int freq;
int i, j;

fp = fopen("sample.txt","r");
fpo = fopen("xxxx", "w");
prevTag[0] = 0;
while ( !feof(fp) )
{
if ( fscanf(fp, "%s %s %d", bufGsm, bufTag, &freq) == 3 )
{
i = findOrAddArray(bufTag, &tag);
j = findOrAddArray(bufGsm, &gsm);
fprintf(fpo, "%d %d %d\n", i, j, freq);
}

}
fclose(fp);
fclose(fpo);

int *res = (int*)malloc(tag.size*gsm.size*sizeof(int));
fp = fopen("xxxx","r"); /* temporaire */
while ( !feof(fp) ) 
{
if ( fscanf(fp, "%d %d %d", &i, &j, &freq) == 3 )
{
res[i*gsm.size+j] = freq;
}	
}
fclose(fp);

fpo = stdout;

fprintf(fpo, "etiquette");
for (j=0; j<gsm.size; j++)
{
fprintf(fpo, " %s", gsm.array[j]);
}
fprintf(fpo, "\n");

for (i=0; i<tag.size; i++)
{
fprintf(fpo, "%s", tag.array[i]);
for (j=0; j<gsm.size; j++)
{
fprintf(fpo, " %d", res[i*gsm.size+j]);
}
fprintf(fpo, "\n");
}
free(res);
for (i=0; i<tag.size; i++) free(tag.array[i]);
free(tag);
for (i=0; i<gsm.size; i++) free(gsm.array[i]);
free(gsm);
}


J'utilise un fichier temporaire pour simplifier mais on pourrait gérer en mémoire.

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
27 janv. 2010 à 20:27
oui çà m'a l'air pas mal ton code, il faut faire des tests.
tiens continues à jouer en le testant sur ce fichier: http://dl.free.fr/avyxd1N7f

mslider
0
Rejoignez-nous