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
23 févr. 2010 à 10:23
On pourrait améliorer la lecture et le traitement mais au vu de tes résultats c'est inutile face au temps d'écriture.

Combien mets-tu de temps pour copier le fichier en entrée ? (avec cp, tout simplement)

Tu trie ce fichier en 2 mn : le fichier est-il bien trié à l'arrivée ? (quelques pages avec more pour voir, puis un tail)

J'ai un rapport de 1 à 15 entre les 2 premières phases et la troisième. Toi tu as 30s, avec ce ratio x 15 7.5 mn, + les 30s du début 8mn : c'est pourquoi je m'attendais à 10mn.
Avec /dev/null, mon ratio est de 4.5 : le tien est un poil plus bas mais ça se tient.

La Question est donc "Pourquoi l'écriture est-elle si longue ?"

Au fait, quelle est la taille du fichier résultant ?
Contrairement à un tri (taille après = taille avant), ce programme crée un fichier différent de l'entrée, et a priori plus grand.

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
23 févr. 2010 à 10:37
j'ai vérifié le fichier est bien trié.

temps pour copier le bigfile.txt: time cp bigfile.txt bigfile.dat
0.001u 6.316s 1:09.12 9.1% 0+0k 0+0io 0pf+0w

c'est normal que le fichier résultant est plus gros vu que le programme construit une matrice
en rajoutant un nombre considérable de 0 et de retour à la ligne,un exemple avec le fichier sample.dat de 10000 lignes:

./last -v sample.dat out.txt

232551 Feb 4 21:06 sample.dat
1086525 Feb 23 10:36 out.tx
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
23 févr. 2010 à 11:16
Erreur de ma part : ce n'est pas le temps de copie de bigfile qu'il faut mais celui de out.txt, le fichier résultant du big_file.


thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
23 févr. 2010 à 12:15
./last -v bigfile.txt out.txt
size = 1595586743
Lecture 100%, NL=58859592 10s
Traitement 100%, 16s
Ecriture 100%, 2088s
Temp total: 35'14

puis un time cp out.txt out.dat:
0.124u 397.258s 36:15.08 18.2% 0+0k 0+0io 0pf+0w
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
23 févr. 2010 à 12:30
Finalement on doit être au taquet : c'est bien le même temps que cp.

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
23 févr. 2010 à 13:40
oui effectivement çà en a l'air, 35 minutes c déjà bien, sachant que ce bigfile est un cas extrème.

merci.

mslider
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
23 févr. 2010 à 15:28
Surtout n'oublie pas de trier suivant la colonne "tag" avant de lancer ce traitement.

Entre la version page 7 et la dernière, il y a une amélioration sur le sample.txt (sur mon ordi) mais pas sur le bigfile (sur ton ordi).
Ca dépend du nombre de cases remplies dans la matrice finale. Plus il y en a, et plus ça va vite relativement à la taille du fichier initial.

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
23 févr. 2010 à 15:35
toutes façon toutes les parties du code ont été optimisées,
la partie du code qui occupe la majeure partie du traitement c'est l'écriture et encore que tu as utilisé open qui est une instruction de plus bas niveau que fopen.
Ya pas une instruction sysopen() qui est encore de plus bas niveau en C ?
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
23 févr. 2010 à 15:56
ben non. Si mon souvenir est bon, le code de read() est en assembleur. Mais ça dépend peut-être des implémentations.

Il y a encore moyen d'améliorer les 2 premières parties, mais le jeu n'en vaut plus la chandelle. Il s'agit d'agir sur 1/70e du temps total ! bof. Au mieux, on va gagner 5 secondes.

Sur mon ordi, il est plus rapide de ne pas mettre de 2nd parametre et de rediriger la sortie standard dans un fichier. Là j'ai un message d'erreur (il faut initialiser fdo à 1 au lieu de -1, et ce sera bon).

Et finalement, sans l'option -v, on gagne encore quelques secondes !


thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 11:58
d'après toi en écrivant la fonction d'ecriture en assembleur est ce que çà pourrait aller plus vite ?

inclure du code asm dans du C du style:

char* chaine = "bonjour\n";
int main(int argc, char **argv)
{
asm("mov $4, %eax");
asm("mov $1, %ebx");
asm("mov chaine, %ecx");
asm("mov $8, %edx");
asm("int $0x80");
return 0;
}
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
24 févr. 2010 à 12:16
Non, write() est déjà trop bas niveau pour espérer faire mieux.
Ce serait dépenser beaucoup d'énergie pour gagner très peu.

Essaye plutôt de gagner en travaillant sur des disques physiques différents.

utilise un SCSI 15k si ce n'est pas encore le cas

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 15:05
je viens de compiler le code sur une machine 32 bits qui a 6Go de RAM
tout se passe bien, çà tourne bien sur le fichier sample.dat (10000 lignes)
par contre pour un fichier plus gros d'un million de lignes:

size = 75076335
Lecture 100%, NL=1689112 0s
Traitement 100%, 1s
Ecriture 24%*** glibc detected *** crosstab: free(): invalid next size (fast): 0x08a46828 ***
===== Backtrace: =========
/lib/libc.so.6[0x5b8d06]
/lib/libc.so.6(cfree+0x90)[0x5bc1e0]
crosstab[0x804912f]
/lib/libc.so.6(__libc_start_main+0xdc)[0x565dec]
crosstab[0x8048731]
===== Memory map: ========
004b4000-004ce000 r-xp 00000000 08:08 6770578 /lib/ld-2.5.so
004ce000-004cf000 r--p 00019000 08:08 6770578 /lib/ld-2.5.so
004cf000-004d0000 rw-p 0001a000 08:08 6770578 /lib/ld-2.5.so
004d2000-004f7000 r-xp 00000000 08:08 6771137 /lib/libm-2.5.so
004f7000-004f8000 r--p 00024000 08:08 6771137 /lib/libm-2.5.so
004f8000-004f9000 rw-p 00025000 08:08 6771137 /lib/libm-2.5.so
00550000-0068d000 r-xp 00000000 08:08 6770579 /lib/libc-2.5.so
0068d000-0068f000 r--p 0013d000 08:08 6770579 /lib/libc-2.5.so
0068f000-00690000 rw-p 0013f000 08:08 6770579 /lib/libc-2.5.so
00690000-00693000 rw-p 00690000 00:00 0
008de000-008df000 r-xp 008de000 00:00 0 [vdso]
00990000-0099b000 r-xp 00000000 08:08 6771170 /lib/libgcc_s-4.1.2-20080102.so.1
0099b000-0099c000 rw-p 0000a000 08:08 6771170 /lib/libgcc_s-4.1.2-20080102.so.1
08048000-0804a000 r-xp 00000000 08:06 7211639 /usr/bin/crosstab
0804a000-0804b000 rw-p 00001000 08:06 7211639 /usr/bin/crosstab
08a43000-08a65000 rw-p 08a43000 00:00 0
b2900000-b2921000 rw-p b2900000 00:00 0
b2921000-b2a00000 ---p b2921000 00:00 0
b2a72000-b7ef1000 rw-p b2a72000 00:00 0
b7f08000-b7f09000 rw-p b7f08000 00:00 0
bff25000-bff3b000 rw-p bff25000 00:00 0 [stack]
Abandon (core dumped)

je pense que mon code était adapté à une machine 64 bits.
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
24 févr. 2010 à 15:24
C'est surtout un free() malencontreux. Le seul malloc de cette phase est dans outBuf();

Tu peux l'enlever (avec son free) et utiliser une variable globale. Risqué, sauf si tu utilise un majorant absolu (nombre de gsm * 10 ou 15)

ex: char line[30000];

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 15:31
tu peux m'envoyer le code que tu utilises sur ta bécane 32 bits pour que je teste sur la mienne, STP ?
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
24 févr. 2010 à 15:44
J'ai le même que toi.

char line[30000];
void outBuf(int fd, char *t, char **s, int n)
{
char *p = line;
while ( *p++ = *t++)
;
        while ( n-- > 0 )
        {
p[-1] = ' ';
t = *s++;
while ( *p++ = *t++)
;
        }
        p[-1] = '\n';
write(fd, line, (size_t)(p-line));
}


thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 16:04
j'ai fais la modif çà fonctionne, par contre il me rajoute une colonne Y en sortie:

fichier d'entrée:
GSM10425 AAAAAAAAAA 15
GSM1 AAAAAAAAAA 17
GSM10419 AAAAAAAAAA 54
GSM10419 AAAAAAAAAC 2
GSM10425 AAAAAAAAAG 2
GSM10425 AAAAAAAAAT 1
GSM10425 AAAAAAAGAA 1
GSM10425 AAAAAAAGAG 4
GSM1 AAAAAAATCA 1
GSM1 AAAAAAATTT 1
GSM10419 AAAAAACTAC 1
GSM10419 AAAAAACTCC 2
GSM10419 AAAAAACTGA 1
GSM10419 AAAAAAGAAA 3
GSM10419 AAAAAAGGCA 14
GSM1 AAAAACAAAA 1
GSM10424 AAAAACATAG 1
GSM10424 AAAAACATCC 1
GSM10424 AAAAACCAAA 1
GSM10424 AAAAACCTAC 1

et en sortie j'ai:

etiquette GSM10425 GSM1 GSM10419 GSM10424 Y
AAAAAAAAAA 15 17 54 0 0
AAAAAAAAAC 0 0 2 0 0
AAAAAAAAAG 2 0 0 0 0
AAAAAAAAAT 1 0 0 0 0
AAAAAAAGAA 1 0 0 0 0
AAAAAAAGAG 4 0 0 0 0
AAAAAAATCA 0 1 0 0 0
AAAAAAATTT 0 1 0 0 0
AAAAAACTAC 0 0 1 0 0
AAAAAACTCC 0 0 2 0 0
AAAAAACTGA 0 0 1 0 0
AAAAAAGAAA 0 0 3 0 0
AAAAAAGGCA 0 0 14 0 0
AAAAACAAAA 0 1 0 0 0
AAAAACATAG 0 0 0 1 0
AAAAACATCC 0 0 0 1 0
AAAAACCAAA 0 0 0 1 0
AAAAACCTAC 0 0 0 1 0
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 16:18
c bon j'ai trouvé pourquoi yavais ce bug:
il faut un retour à la ligne en fin de fichier d'entrée !

sinon j'ai trouvé peut être une amélioration de memcpy, peut etre pas plus rapide
pour les petits fichiers mais x4 pour les gros:

void *memcpy_1(void *dest, const void *src,int bytes){
int minor = bytes % 4;
int dwords = bytes >> 2;
int *idest = (int *)dest;
int *isrc = (int *)src;
while(dwords--)
*idest++ = *isrc++;

char *cdest = dest+bytes-minor;
char *csrc = src+bytes-minor;
while(minor--)
*cdest++ = *csrc++;

return dest;
}
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
24 févr. 2010 à 16:33
bien vu.

Pour éviter le problème :

d'abord ajouter un pointeur q

/************************ Lecture ***************************/
time_t t0, t1, t2, t3;
int nr;
char *pbf, *p, *q;


puis modifier l'appel à findOrAddArray
if ( p = strtok(pbf, " ") ) {
if ( q = strtok(NULL, " ") )
{
*pvgsm = findOrAddArray(&gsm, p);
*prow = q; // pointe sur tag
}
}


en plus tu gagneras encore quelques secondes.

Je suis très étonné que ton remplacement de memcpy soit plus rapide !
Mais tant mieux.

thip
0
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
24 févr. 2010 à 16:42
2 remarques sur ton memcpy :

- int minor = bytes % 4;
modulo, pas terrible avec une puissance de 2, quand on fait ensuite du décalage de bits.
Je verrai plutôt
int minor = bytes & 0x03;
ok, c'est puriste

- cela sous-entend que sizeof(int) = 4. Quand c'est 8, danger !

thip
0
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 16:49
zut çà coince à la compil avec mon memcpy modifié:

crosstab.c: In function ?memcpy_1?:
crosstab.c:95: attention : initialization discards qualifiers from pointer target type
0
Rejoignez-nous