Sujet Précédent Sujet Suivant

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

Précédent
Réponse 121 / 142
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 à 17:03
C'est quoi la ligne 95 ? 

char *cdest = dest+bytes-minor;
Celle-ci ?

fais un cast en (char *)

thip
0
Réponse 122 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 17:17
non c'est celle là: char *csrc = src+bytes-minor;
0
Réponse 123 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 17:30
(char *)csrc = src+bytes-minor;
me renvoit:
crosstab.c: In function ?memcpy_1?:
crosstab.c:95: erreur: ?csrc? undeclared (first use in this function)
crosstab.c:95: erreur: (Each undeclared identifier is reported only once
crosstab.c:95: erreur: for each function it appears in.)


j'ai fais un test sur une machine 32bits pour mon bigfile:

ya un bug en ecriture:

crosstab -v bigfile.txt out.txt
size = 1595586743
Lecture 100%, NL=58859592 19s
Traitement 100%, 28s
Ecriture 3%Taille limite de fichier dépassée (core dumped)


par contre sur /dev/null çà passe:

crosstab -v bigfile.txt /dev/null
size = 1595586743
Lecture 100%, NL=58859592 25s
Traitement 100%, 23s
Ecriture 10%
0
Réponse 124 / 142
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 à 17:37
Le cast, c'est à droite du =

.. = (char *)(...)


taille maximum de fichier = résultat de la commande ulimit
c'est un paramètre système, à augmenter.

thip
0

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

Posez votre question
Réponse 125 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 17:44
comme çà? :

char *csrc = (src+bytes-minor);
0
Réponse 126 / 142
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 à 17:46
char *csrc = (char*)src + (char *)(bytes-minor);


thip
0
Réponse 127 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 17:51
il me retourne que le + ne lui plait pas:

crosstab.c: In function ?memcpy_1?:
crosstab.c:96: char *csrc = (char*)src + (char *)(bytes-minor);
erreur: opérandes invalides pour le binaire +
0
Réponse 128 / 142
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 à 17:57
alors fais le en 2 fois.

char *csrc = (char *)src;
crsc += (char *) (bytes - minor);


thip
0
Réponse 129 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 21:30
non çà marche pas tu utilises le signe + pour additionner des char.
la bonne syntaxe c'est: char *csrc = (char *)(src+bytes-minor);
d'abord tu fais l'addition puis après tu cast.
0
Réponse 130 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
24 févr. 2010 à 21:36
voilà les tests avec le fichier d'un million de lignes:

version avec memcpy standard:
size = 75076335
Lecture 100%, NL=1689112 0s
Traitement 100%, 1s
Ecriture 100%, 6s
Temp total: 0'07


version avec memcpy_1:

size = 75076335
Lecture 100%, NL=1689112 1s
Traitement 100%, 1s
Ecriture 100%, 6s
Temp total: 0'08


sensiblement identiques.
0
Réponse 131 / 142
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 à 22:44
oui c'est quasi pareil, mais sur un fichier dont l'écriture est supérieure à 10mn ?
et sur la machine 64 bits ?

avec vérification de la cohérence du résultat à chaque fois.
0
Réponse 132 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
25 févr. 2010 à 10:07
en effet sur le bigfile et sur la machine 64bits, j'obtiens:

size = 1595586743
Lecture 100%, NL=58859592 12s
Traitement 100%, 16s
Ecriture 100%, 1318s
Temp total: 22'26

je vais maintenant essayer d'exploiter ce code de 'fast memcpy' sur ma machine 32bits: 

/********************************************************************
 ** File:     memcpy.c
 **
 ** Copyright (C) 2005 Daniel Vik
 ** 
 ** This software is provided 'as-is', without any express or implied
 ** warranty. In no event will the authors be held liable for any
 ** damages arising from the use of this software.
 ** Permission is granted to anyone to use this software for any
 ** purpose, including commercial applications, and to alter it and 
 ** redistribute it freely, subject to the following restrictions:
 ** 
 ** 1. The origin of this software must not be misrepresented; you
 **    must not claim that you wrote the original software. If you
 **    use this software in a product, an acknowledgment in the
 **    use this software in a product, an acknowledgment in the
 **    product documentation would be appreciated but is not
 **    required.
 ** 
 ** 2. Altered source versions must be plainly marked as such, and 
 **    must not be misrepresented as being the original software.
 ** 
 ** 3. This notice may not be removed or altered from any source 
 **    distribution.
 ** 
 ** 
 ** Description: Implementation of the standard library function memcpy.
 **             This implementation of memcpy() is ANSI-C89 compatible.
 **
 **             The following configuration options can be set:
 **
 **           LITTLE_ENDIAN   - Uses processor with little endian
 **                             addressing. Default is big endian.
 **
 **           PRE_INC_PTRS    - Use pre increment of pointers.
 **                             Default is post increment of
 **                             pointers.
 **
 **           INDEXED_COPY    - Copying data using array indexing.
 **                             Using this option, disables the
 **                             PRE_INC_PTRS option.
 **
 **
 ** Best Settings:
 **
 ** Intel x86:  LITTLE_ENDIAN and INDEXED_COPY
 **
 *******************************************************************/



/********************************************************************
 ** Configuration definitions.
 *******************************************************************/

#define LITTLE_ENDIAN
#define INDEXED_COPY



/********************************************************************
 ** Includes for size_t definition
 *******************************************************************/

#include <stddef.h>



/********************************************************************
 ** Typedefs
 *******************************************************************/

typedef unsigned char  u8;
typedef unsigned short u16;
typedef unsigned long  u32;



/********************************************************************
 ** Remove definitions when INDEXED_COPY is defined.
 *******************************************************************/

#if defined (INDEXED_COPY)
#if defined (PRE_INC_PTRS)
#undef PRE_INC_PTRS
#endif /*PRE_INC_PTRS*/
#endif /*INDEXED_COPY*/



/********************************************************************
 ** Definitions for pre and post increment of pointers.
 *******************************************************************/

#if defined (PRE_INC_PTRS)

#define INC_VAL(x) *++(x)
#define START_VAL(x) (x)--
#define CAST_32_TO_8(p, o)       (u8 *)((u32)p + o + 4)
#define WHILE_DEST_BREAK         3
#define PRE_LOOP_ADJUST        - 3
#define PRE_SWITCH_ADJUST      + 1

#else /*PRE_INC_PTRS*/

#define START_VAL(x)
#define INC_VAL(x) *(x)++
#define CAST_32_TO_8(p, o)       (u8 *)((u32)p + o)
#define WHILE_DEST_BREAK         0
#define PRE_LOOP_ADJUST
#define PRE_SWITCH_ADJUST

#endif /*PRE_INC_PTRS*/



/********************************************************************
 ** Definitions for endians
 *******************************************************************/

#if defined (LITTLE_ENDIAN)

#define SHL >>
#define SHR <<

#else /*LITTLE_ENDIAN*/

#define SHL <<
#define SHR >>

#endif /*LITTLE_ENDIAN*/



/********************************************************************
 ** Macros for copying 32 bit words of  different alignment.
 ** Uses incremening pointers.
 *******************************************************************/

#define CP32_INCR() {                       \
    INC_VAL(dst32) = INC_VAL(src32);        \
}

#define CP32_INCR_SH(shl, shr) {            \
    dstWord   = srcWord SHL shl;            \
    srcWord   = INC_VAL(src32);             \
    dstWord  |= srcWord SHR shr;            \
    INC_VAL(dst32) = dstWord;               \
}



/********************************************************************
 ** Macros for copying 32 bit words of  different alignment.
 ** Uses array indexes.
 *******************************************************************/

#define CP32_INDEX(idx) {                   \
    dst32[idx] = src32[idx];                \
}

#define CP32_INDEX_SH(x, shl, shr) {        \
    dstWord   = srcWord SHL shl;            \
    srcWord   = src32[x];                   \
    dstWord  |= srcWord SHR shr;            \
    dst32[x] = dstWord;                     \
}



/********************************************************************
 ** Macros for copying 32 bit words of different alignment.
 ** Uses incremening pointers or array indexes depending on
 ** configuration.
 *******************************************************************/

#if defined (INDEXED_COPY)

#define CP32(idx)               CP32_INDEX(idx)
#define CP32_SH(idx, shl, shr)  CP32_INDEX_SH(idx, shl, shr)

#define INC_INDEX(p, o)         ((p) += (o))

#else /*INDEXED_COPY*/

#define CP32(idx)               CP32_INCR()
#define CP32_SH(idx, shl, shr)  CP32_INCR_SH(shl, shr)

#define INC_INDEX(p, o)

#endif /*INDEXED_COPY*/



/********************************************************************
 **
 ** void *memcpy(void *dest, const void *src, size_t count)
 **
 ** Args:     dest    - pointer to destination buffer
 **           src     - pointer to source buffer
 **           count   - number of bytes to copy
 **
 ** Return:   A pointer to destination buffer
 **
 ** Purpose:  Copies count bytes from src to dest. No overlap check
 **           is performed.
 **
 *******************************************************************/

void *memcpy(void *dest, const void *src, size_t count) {
    u8 *dst8 = (u8 *)dest;
    u8 *src8 = (u8 *)src;

    if (count < 8) {
        if (count >4 && ((((u32)src8 | (u32)dst8)) & 3) 0) {
            *((u32 *)dst8) = *((u32 *)src8);
            dst8  += 4;
            src8  += 4;
            count -= 4;
        }

        START_VAL(dst8);
        START_VAL(src8);

        while (count--) {
            INC_VAL(dst8) = INC_VAL(src8);
        }

        return dest;
    }

    START_VAL(dst8);
    START_VAL(src8);

    while (((u32)dst8 & 3L) != WHILE_DEST_BREAK) {
        INC_VAL(dst8) = INC_VAL(src8);
        count--;
    }

    switch ((((u32)src8) PRE_SWITCH_ADJUST) & 3L) {
    default:
        {
            u32 *dst32 = (u32 *)(((u32)dst8) PRE_LOOP_ADJUST);
            u32 *src32 = (u32 *)(((u32)src8) PRE_LOOP_ADJUST);
            u32 length = count / 4;

            while (length & 7) {
                CP32_INCR();
                length--;
            }

            length /= 8;

            while (length--) {
                CP32(0);
                CP32(1);
                CP32(2);
                CP32(3);
                CP32(4);
                CP32(5);
                CP32(6);
                CP32(7);

                INC_INDEX(dst32, 8);
                INC_INDEX(src32, 8);
            }

            src8 = CAST_32_TO_8(src32, 0);
            dst8 = CAST_32_TO_8(dst32, 0);

            if (count & 2) {
                *dst8++ = *src8++;
                *dst8++ = *src8++;
            }

            if (count & 1) {
                *dst8 = *src8;
            }

            return dest;
        }

    case 1:
        {
            u32 *dst32  = (u32 *)((((u32)dst8) PRE_LOOP_ADJUST) & ~3L);
            u32 *src32  = (u32 *)((((u32)src8) PRE_LOOP_ADJUST) & ~3L);
            u32 length  = count / 4;
            u32 srcWord = INC_VAL(src32);
            u32 dstWord;

            while (length & 7) {
                CP32_INCR_SH(8, 24);
                length--;
            }

            length /= 8;

            while (length--) {
                CP32_SH(0, 8, 24);
                CP32_SH(1, 8, 24);
                CP32_SH(2, 8, 24);
                CP32_SH(3, 8, 24);
                CP32_SH(4, 8, 24);
                CP32_SH(5, 8, 24);
                CP32_SH(6, 8, 24);
                CP32_SH(7, 8, 24);

                INC_INDEX(dst32, 8);
                INC_INDEX(src32, 8);
            }

            src8 = CAST_32_TO_8(src32, -3);
            dst8 = CAST_32_TO_8(dst32, 0);

            if (count & 2) {
                *dst8++ = *src8++;
                *dst8++ = *src8++;
            }

            if (count & 1) {
                *dst8 = *src8;
            }

            return dest;
        }

    case 2:
        {
            u32 *dst32  = (u32 *)((((u32)dst8) PRE_LOOP_ADJUST) & ~3L);
            u32 *src32  = (u32 *)((((u32)src8) PRE_LOOP_ADJUST) & ~3L);
            u32 length  = count / 4;
            u32 srcWord = INC_VAL(src32);
            u32 dstWord;

            while (length & 7) {
                CP32_INCR_SH(16, 16);
                length--;
            }

            length /= 8;

            while (length--) {
                CP32_SH(0, 16, 16);
                CP32_SH(1, 16, 16);
                CP32_SH(2, 16, 16);
                CP32_SH(3, 16, 16);
                CP32_SH(4, 16, 16);
                CP32_SH(5, 16, 16);
                CP32_SH(6, 16, 16);
                CP32_SH(7, 16, 16);

                INC_INDEX(dst32, 8);
                INC_INDEX(src32, 8);
            }

            src8 = CAST_32_TO_8(src32, -2);
            dst8 = CAST_32_TO_8(dst32, 0);

            if (count & 2) {
                *dst8++ = *src8++;
                *dst8++ = *src8++;
            }

            if (count & 1) {
                *dst8 = *src8;
            }

            return dest;
        }

    case 3:
        {
            u32 *dst32  = (u32 *)((((u32)dst8) PRE_LOOP_ADJUST) & ~3L);
            u32 *src32  = (u32 *)((((u32)src8) PRE_LOOP_ADJUST) & ~3L);
            u32 length  = count / 4;
            u32 srcWord = INC_VAL(src32);
            u32 dstWord;

            while (length & 7) {
                CP32_INCR_SH(24, 8);
                length--;
            }

            length /= 8;

            while (length--) {
                CP32_SH(0, 24, 8);
                CP32_SH(1, 24, 8);
                CP32_SH(2, 24, 8);
                CP32_SH(3, 24, 8);
                CP32_SH(4, 24, 8);
                CP32_SH(5, 24, 8);
                CP32_SH(6, 24, 8);
                CP32_SH(7, 24, 8);

                INC_INDEX(dst32, 8);
                INC_INDEX(src32, 8);
            }

            src8 = CAST_32_TO_8(src32, -1);
            dst8 = CAST_32_TO_8(dst32, 0);

            if (count & 2) {
                *dst8++ = *src8++;
                *dst8++ = *src8++;
            }

            if (count & 1) {
                *dst8 = *src8;
            }

            return dest;
        }
    }
}
0
Réponse 133 / 142
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
25 févr. 2010 à 10:32
Ca me rappelle un code d'un type d'Intel. Attention au 64 bits : valide en faisant un memcmp standard après le memcpy pour vérifier (après test, tu enlèves).

N'oublie pas de compiler avec l'option -O3 (Optimize level 3)
0
Réponse 134 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
25 févr. 2010 à 10:54
le code est tiré d'ici: http://www.vik.cc/daniel/portfolio/

il est optimisé pour du 32bits,
la compilation passe pas sur ma bécane 64bits, par contre çà passe si je mets -m32 mais bon c dommage de pas exploiter
les 64 bits d'allocation
0
Réponse 135 / 142
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
25 févr. 2010 à 11:13
Ce qui m'inquiète c'est que sur /dev/null, tu obtenais 2,5 mn. Ce temps inclus l'utilisation de memcpy.
Or, tu annonces un gain de 13 mn !
0
Réponse 136 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
25 févr. 2010 à 11:48
oui un gain de 13 minutes en utilsant memcpy_1
et un écrivant dans un fichier de sortie:

./last -v bigfile.txt out.txt
size = 1595586743
Lecture 100%, NL=58859592 12s
Traitement 100%, 16s
Ecriture 100%, 1318s
Temp total: 22'26

maintenant sur /dev/null
./last -v bigfile.txt /dev/null
size = 1595586743
Lecture 100%, NL=58859592 13s
Traitement 100%, 16s
Ecriture 100%, 180s
Temp total: 3'29

et avec memcpy standard:

size = 1595586743
Lecture 100%, NL=58859592 9s
Traitement 100%, 16s
Ecriture 100%, 120s
Temp total: 2'25


maintenant avec le memcpy récupéré sur le site de Daniel Vik:

./lastbis -v bigfile.txt /dev/null
size = 1595586743
Lecture 100%, NL=58859592 10s
Traitement 100%, 18s
Ecriture 100%, 137s
Temp total: 2'45
0
Réponse 137 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
25 févr. 2010 à 11:55
c bizarre qd je compile en 32 bits ton code, que ce soit sur ma bécane 64bits ou sur une bécane 32bits, çà génére
un plantage à l'écriture:

size = 1595586743
Lecture 100%, NL=58859592 9s
Traitement 100%, 19s
Ecriture 3%Filesize limit exceeded (core dumped)

alors que la version 64bits ne génére pas ce plantage.
0
Réponse 138 / 142
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
25 févr. 2010 à 12:23
D'habitude ça correspond au dépassement de ulimit. Mais en 32 bits, on ne doit pas pouvoir dépasser 2 Go de fichier. Le résultat est à 67 Go ?
Je crois qu'il y a un paramètre de compilation pour les gros fichiers, genre large_file
0
Réponse 139 / 142
mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
25 févr. 2010 à 12:36
oui çà me rappelle quelque chose,
je crois qu'il faut recompiler le noyer en activant le LFS (Large File Support)
0
Réponse 140 / 142
tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
25 févr. 2010 à 15:50
dans l'open, ajoute O_LARGEFILE :
fdo = open(outFile,O_WRONLY|O_CREAT|O_TRUNC|O_LARGEFILE);
0

Discussions similaires

création mots croisés
sylber0 -
sylber0 -

3 réponses
Les tableaux - constructeur
axelvdk -
axelvdk -

2 réponses
Stockage de la date sytème dans un tableau
cs_Shany -
Lutinore -

8 réponses
générer une grille de mots mêlés
orangin12FR -
orangin12FR -

2 réponses
initialisation tableau dans un constructeur
cs_tontonzip -
ekinox17 -

5 réponses
Rejoignez-nous