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.

A voir également:

Tableaux croisés
Tableaux constructeur ✓ - Forum PHP
Tableaux html - Conseils pratiques -PHP
Php fusionner 2 tableaux ✓ - Forum PHP
Ca peut servir mots croises - Forum VB.NET
Tableaux des types - Forum C# / .NET

142 réponses

Réponse 41 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
1 févr. 2010 à 17:03

idem meme seg fault après modif du code


 /*************************************/
        //long *res = (long*)malloc(tag.size * gsm.size * sizeof(long));
        long **res = (long **)calloc(tag.size, sizeof(long *));
        for (i = 0; i < tag.size; i++)
        {
                res[i] = (long *)calloc(gsm.size, sizeof(long));
        }

        while ( blk = depile(blk, &i, &j, &freq) )
                res[i][j] = freq;

        /*************************************/

        FILE *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]);
                   for (j=0; j<gsm.size; j++)
                        fprintf(fpo, " %d", res[i][j]);

        fprintf(fpo, "\n");
        free(res[i]);
        }
        hashtable_destroy(tag.h, 0);
        free(tag.array);
        hashtable_destroy(gsm.h, 0);
        free(gsm.array);
        free(res);
}

je vois d'où çà peut venir, enfin si çà vient de l'allocation mémoire mais à quel niveau ?

mslider

Réponse 42 / 142

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

Mets des traces pour savoir :

        for (i = 0; i < tag.size; i++)
        {
                res[i] = (long *)calloc(gsm.size, sizeof(long));
        }
fprintf(stderr, "boucle dépile\n");
        while ( blk = depile(blk, &i, &j, &freq) )
{
fprintf(stderr, "%d %d %d\n", i, j, freq);
                res[i][j] = freq;
}
fprintf(stderr, "boucle dépile terminée\n");

        /*************************************/

        FILE *fpo = stdout;

        fprintf(fpo, "etiquette");
        for (j=0; j<gsm.size; j++)
                fprintf(fpo, " %s", gsm.array[j]);
        fprintf(fpo, "\n");
// As-tu cette ligne d'entête (ci dessus) ?
        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]);
                   for (j=0; j<gsm.size; j++)
                        fprintf(fpo, " %d", res[i][j]);

        fprintf(fpo, "\n");
        free(res[i]);
        }
        hashtable_destroy(tag.h, 0);

thip

Réponse 43 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
1 févr. 2010 à 18:37

la ligne d'entête contenant "etiquette" ne s'affiche pas,
voilà la fin du listing que j'ai à l'écran:

size = 1595586743
1.2% tag:280413 gsm:23
2.3% tag:492601 gsm:44
3.4% tag:690003 gsm:65
.../...

98.5% tag:18256114 gsm:1538
99.4% tag:18257303 gsm:1570
boucle depilee70900 gsm:1597
1556774 1596 4

Réponse 44 / 142

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
2 févr. 2010 à 09:44

Donc c'est la pile. Je vais voir ça.

Je craignais pour Tag/Gsm : on frise la catastrophe avec la taille de ton fichier. Je double la mémoire allouée à chaque demande et j'ai mis des long au lieu de ulong. Ce sera vite court. Il faudrait allouer plus petit à chaque fois.
Déjà mon premier res réclamait pour ce gros fichier 18,3 10^6 * 1.6 10^3 * sizeof(long) soit 10^11 ce qui est déjà trop grand.

thip

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

Posez votre question

Réponse 45 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
2 févr. 2010 à 09:50

avec 64Go de RAM je pense qd même que j'en ai de reste pour traiter un fichier de 1.5Go, tu peux allouer gros en mémoire.

Réponse 46 / 142

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
2 févr. 2010 à 14:38

ben non, on peut pas tout à fait allouer beaucoup : malloc(size_t n), et size_t = unsigned long.
il faut le faire par bloc séparé, comme ma pile.

il faut assainir le code : chaque allocation doit être vérifiée, si NULL alors message+exit.

fait un #defile NFREQ 1024

définition de la structure : remplace 1024 par NFREQ

dans empile() :
remplacer

		b->next = 0;
}
else if ( b->n == sizeof(b->tbfreq)/sizeof(FREQ) ) {

par

		b->next = (BLOC *)0;
}
else if ( b->n == NFREQ ) {

C'est depile qui gêne : elle est bien déclarée en BLOC * ?
Le code fonctionne bien avec des fichiers plus petit ?

thip

Réponse 47 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
2 févr. 2010 à 14:56

j'ai fais les modifs, voilà ce qui s'affiche:
size = 1595586743
100.0% tag:18270900 gsm:1597

boucle depilee70900 gsm:1597
1556774 1596 4
Segmentation fault (core dumped)

voilà le code complet:

#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"
#define NFREQ 1024 



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

typedef struct {
long i;
long j;
long freq;
} FREQ;

typedef struct st_bloc {
FREQ tbfreq[1024];
int n;
struct st_bloc *next;
} BLOC;


static unsigned int hashKey(void* item)
{
unsigned int h = 0;
char *p = (char *)item;
while ( *p ) {
h = ((h << 5) + h) + *p++;
}
return h;
}

static int compareKey(void* k1, void* k2)
{
return !strcmp(k1, k2);
}


void initArray(ARR* a, int sz, int hsz)
{
a->size = 0;
a->allocSize = sz;
a->array = (char **) malloc(sizeof(char *) * sz);
a->h = create_hashtable(hsz, hashKey, compareKey);
}

long findOrAddArray(ARR *arr, char *item)
{
long * pi = (long *)hashtable_search(arr->h, item);
if ( pi )
{
return *pi;
}

long i = arr->size;
int n = strlen(item);
char * key = malloc(n + 1 + sizeof(long));
strcpy(key, item);

pi = (long *)(&key[n + 1]);
*pi = i;

if ( arr->size == arr->allocSize ) {
arr->allocSize *= 2;
char ** p  = (char **) malloc(sizeof(char *) * arr->allocSize);
memcpy(p, arr->array, sizeof(char *) * arr->size);
free(arr->array);
arr->array = p;
}
arr->array[i] = key;
arr->size++;
hashtable_insert(arr->h, key, pi);
return i;
}

BLOC* empile(BLOC *b, long i, long j, long freq)
{
if ( !b ) {
b = (BLOC *)malloc(sizeof(BLOC));
b->n = 0;
                b->next = (BLOC *)0;
}
else if ( b->n == NFREQ ) {		
BLOC *x = b;
b = (BLOC *)malloc(sizeof(BLOC));
b->next = x;
b->n = 0;
}
FREQ* pf = &b->tbfreq[ b->n++ ];
pf->i = i;
pf->j = j;
pf->freq = freq;
return b;
}

BLOC* depile(BLOC *b, long *i, long *j, long * freq)
{
if ( !b ) return NULL;

if ( b->n > 0 ) {
FREQ* pf = &b->tbfreq[ --b->n ];
*i = pf->i;
*j = pf->j;
*freq = pf->freq;
}
else {
BLOC *x = b->next;
free(b);
b = depile(x, i, j, freq);
}
return b;
}

main(int argc, char *argv[])
{
BLOC *blk = NULL;
FILE *fp;
ARR tag;
ARR gsm;
initArray(&tag, 10000, 1000000);
initArray(&gsm, 500, 1000);

if ( argc != 2 )
{
fprintf(stderr, "il manque le fichier a traiter.");
exit(1);
}

char bufTag[512], bufGsm[512];
long freq;
long i, j;

if ( !(fp = fopen(argv[1],"r")) ) 
{
fprintf(stderr, "%s: erreur d'ouverture");
exit(1);
}
struct stat st;
stat(argv[1], &st);
long fsz = st.st_size;
fprintf(stderr, "size = %d\n", fsz);

float n = 0.1;
while ( !feof(fp) )
{
if ( fscanf(fp, "%s %s %d", bufGsm, bufTag, &freq) == 3 )
{
i = findOrAddArray(&tag, bufTag);
j = findOrAddArray(&gsm, bufGsm);
blk = empile(blk, i, j, freq);
}
if ( fsz > 0 && ftell(fp)*100.0/fsz > n )
{
fprintf(stderr, "%.1f%% tag:%d gsm:%d\r", n,tag.size,gsm.size);
fflush(stderr);
n += 0.1;
}
}
fprintf(stderr, "100.0%% tag:%d gsm:%d\r", tag.size,gsm.size);
fclose(fp);

        /*************************************/
//long *res = (long*)malloc(tag.size * gsm.size * sizeof(long));
long **res = (long **)calloc(tag.size, sizeof(long *));
 for (i = 0; i < tag.size; i++)
        {
                res[i] = (long *)calloc(gsm.size, sizeof(long));
        }
fprintf(stderr, "boucle depilee\n");
        while ( blk = depile(blk, &i, &j, &freq) )
{
fprintf(stderr, "%d %d %d\n", i, j, freq);
                res[i][j] = freq;
}
fprintf(stderr, "boucle depilee terminee");

        /*************************************/

        FILE *fpo = stdout;

        fprintf(fpo, "etiquette");
        for (j=0; j<gsm.size; j++)
                fprintf(fpo, " %s", gsm.array[j]);
        fprintf(fpo, "\n");
// As-tu cette ligne d'entê (ci dessus) ?
        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]);
                   for (j=0; j<gsm.size; j++)
                        fprintf(fpo, " %d", res[i][j]);

        fprintf(fpo, "\n");
        free(res[i]);
        }

        hashtable_destroy(tag.h, 0);
free(tag.array);
hashtable_destroy(gsm.h, 0);
free(gsm.array);
free(res);
}

Réponse 48 / 142

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
2 févr. 2010 à 17:35

A tout hasard, remplace
res[i][j] = freq;
par
long *resi = req[i];
resi[j] = freq;

thip

Réponse 49 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
2 févr. 2010 à 18:37

voilà céfé:

size = 1595586743
boucle depilee70900 gsm:1597
1556774 1596 4
Segmentation fault (core dumped)

kif kif

Réponse 50 / 142

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
2 févr. 2010 à 19:37

Alors ajoute un test aux calloc() :

long **res = (long **)calloc(tag.size, sizeof(long *));
if ( ! res ) {
fprintf(stderr, "erreur allocation res, %d\n", tag.size* sizeof(long *));
exit(2);
}
for (i = 0; i < tag.size; i++)
{
res[i] = (long *)calloc(gsm.size, sizeof(long));
if ( ! res[i] ) {
fprintf(stderr, "erreur allocation res[%d], %d\n", i, gsm.size* sizeof(long));
exit(2);
}
}

thip

Réponse 51 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
2 févr. 2010 à 21:17

cette fois il m'affiche çà:

size = 1595586743
100.0% tag:18270900 gsm:1597
erreur allocation res[1377279], 12776

et pas de seg fault.
c grave docteur ?

est ce que tu connais rt15 et dobel sur ce forum ?
peut-être qu'on pourrait leur demander leurs avis sur la question.

Réponse 52 / 142

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
3 févr. 2010 à 13:29

pas de seg fault car on capte l'erreur. Manifestement, on ne peut pas allouer autant dans un process, même en 64b.

Le long à une taille de 8 octets !
si le int est plus petit, remplace long par int.
sinon il faut changer d'algorithme pour utiliser moins de mémoire.

thip

Réponse 53 / 142

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
3 févr. 2010 à 14:09

Voici un essai moins rapide mais utilisant moins de mémoire.
Je charge l'intégralité du fichier en mémoire et je travaille dessus, en allouant que le nécessaire.
Inconvénient : 2 boucles imbriquées, c'est ça qui fait long.
Sur mon ordi, ça se plante avec big_file au premier malloc de 1,5 Go ! je n'ai que 256 Mo avec un swap de 512Mo, il faudrait que j'augmente le swap.

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"

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

static unsigned int hashKey(void* item)
{
unsigned int h = 0;
char *p = (char *)item;
while ( *p ) {
h = ((h << 5) + h) + *p++;
}
return h;
}

static int compareKey(void* k1, void* k2)
{
return !strcmp(k1, k2);
}

void initArray(ARR* a, int sz, int hsz)
{
a->size = 0;
a->allocSize = sz;
a->array = (char **) malloc(sizeof(char *) * sz);
a->h = create_hashtable(hsz, hashKey, compareKey);
}

long findOrAddArray(ARR *arr, char *item)
{
long * pi = (long *)hashtable_search(arr->h, item);
if ( pi )
{
return *pi;
}

long i = arr->size;
int n = strlen(item);
char * key = malloc(n + 1 + sizeof(long));
strcpy(key, item);

pi = (long *)(&key[n + 1]);
*pi = i;

if ( arr->size == arr->allocSize ) {
arr->allocSize *= 2;
char ** p  = (char **) malloc(sizeof(char *) * arr->allocSize);
memcpy(p, arr->array, sizeof(char *) * arr->size);
free(arr->array);
arr->array = p;
}
arr->array[i] = key;
arr->size++;
hashtable_insert(arr->h, key, pi);
return i;
}

main(int argc, char *argv[])
{
ARR gsm;
initArray(&gsm, 500, 1000);

if ( argc != 2 )
{
fprintf(stderr, "il manque le fichier à traiter.");
exit(1);
}

long freq;
long i, j;
int fd;

if ( !(fd = open(argv[1],O_RDONLY)) ) 
{
fprintf(stderr, "%s: erreur d'ouverture");
exit(1);
}
struct stat st;
stat(argv[1], &st);
unsigned long fsz = st.st_size;

fprintf(stderr, "size = %d\n", fsz);
char *bufFile = malloc(st.st_size);
if ( !bufFile ) {
fprintf(stderr, "Erreur malloc bufFile\n");
exit(2);
}

int nr;
char *pbf, *p;
int n = 1;
long nl = 0;
long ncur = 0;
for (pbf = bufFile; (nr=read(fd, pbf, 1024)) > 0; pbf += nr )
{
for (p=pbf; p 0 && ncur*100.0/fsz > n )
{
fprintf(stderr, "lecture %d%%\r", n);
fflush(stderr);
n += 1;
}
}
*pbf = 0;
if ( pbf>bufFile && pbf[-1] )
nl++;
fprintf(stderr, "lecture 100.0%%\r\n");
close(fd);

char **row = (char **)malloc(nl*sizeof(char *));
if ( !row ) {
fprintf(stderr, "Erreur malloc row\n");
exit(2);
}
long *vgsm = (long *)malloc(nl*sizeof(long));
if ( !vgsm ) {
fprintf(stderr, "Erreur malloc vgsm\n");
exit(2);
}

char **prow = row;
long *pvgsm = vgsm;
j = 0;
for (pbf=bufFile; *pbf; )
{
*pvgsm = 0;
*prow = NULL;
i = strlen(pbf)+1;

if ( p = strtok(pbf, " ") ) {
*pvgsm = findOrAddArray(&gsm, p);
if ( (p=strtok(NULL, " ")) && strtok(NULL, " ") )
*prow = p; // pointe sur tag
}
*prow++;
*pvgsm++;
pbf += i;
}

/*************************************/
long *res = (long *)malloc(gsm.size * sizeof(long));
FILE *fpo = stdout;

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

char **irow;
char **jrow;
char *curTag; //tag en cours
long *ivgsm = vgsm;

for (i=0, irow = row; i<nl; i++, irow++, ivgsm++)
{
if ( *irow )
{
memset(res, 0, gsm.size*sizeof(long)); // remise à 0

curTag = *irow;
p =  curTag + strlen(curTag) + 1;
res[*ivgsm] = atol(p);

long *jvgsm = ivgsm + 1;
for (j = i+1, jrow=irow+1; j < nl; j++, jrow++, jvgsm++)
{
if ( (p = *jrow) && !strcmp(curTag, p) )
{
p +=  strlen(p) + 1;
res[*jvgsm] = atol(p);
*jrow = (char *)0;
}
}
fprintf(fpo, "%s", curTag);
for (j=0; j<gsm.size; j++)
fprintf(fpo, " %d", res[j]);
fprintf(fpo, "\n");
}
}

/*************************************/
hashtable_destroy(gsm.h, 0);
free(gsm.array);
free(res);
free(bufFile);
exit(0);
}

thip

Réponse 54 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
3 févr. 2010 à 15:32

je viens de le lancer,
çà rame mais çà tourne sans plantage pour le moment.

le top me donne 100% CPU et 3.5% MEM

on verra bien.

Réponse 55 / 142

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
4 févr. 2010 à 09:41

Ca ne rame pas trop, c'est un peu plus long que la version précédente, mais au moins elle tourne.

Tu devrais chercher les limites de l'ordinateur et du compilateur, ça peut servir.
Ou alors fait des essais pour voir combien tu peux allouer en mémoire avant que ça se plante.

Comme je te l'ai dit, un malloc reçoit un size_t en paramètre. Sur ta machine, le long à l'air d'être sur 8 octets, mais ce n'est pas pour ça que le compilateur et le système vont suivre.

A part ça, où en es-tu ?

thip

Réponse 56 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
4 févr. 2010 à 10:03

ben à 10h ce matin le programme vient d'écrire sa 70000 lignes alors que je l'ai lancé hier à 14h !
je sais pas au final combien de lignes il y a à générer.
on verra bien.

ce qui est chiant dans ce forum c'est que les autres personnes plus ou moins callé en prog, même si tu les invites à venir
de donner un petit coup de pouce dans la prog, et bien ils font même pas cas à toi.
On peut se demander à quoi sert un forum ?

Réponse 57 / 142

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
4 févr. 2010 à 11:34

Un forum c'est pour échanger des informations, mais là c'est un peu différent vu que c'est un vrai boulot, alors que je l'avais pris à la légère au début.

70000 seulement, c'est trop peu. On ne peut pas dire combien de temps il reste vu la méthode. Sur mon ordi avec sample.txt, j'avais mis un pourcentage, et je voyais les nombres jusqu'à 40 à une vitesse croissante, puis une légère pause de l'accélération (ou vitesse stagnante) jusqu'à 65% et après trop rapide pour voir.

le nombre de lignes à sortir est celui du nombre de tag (+1 pour l'entête).
Soit 18 millions de lignes !! 18 270 901 exactement

Les 2 boucles imbriquées sont trop lentes, même optimisées en virant les tags en double (il n'y en a pas tant que ça finalement).

Si on conserve la même méthode et que le fichier est trié suivant le tag, on peut le faire en une seule passe.
Tu le tries en combien de temps avec le prog de rt15 ?

thip

Réponse 58 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
4 févr. 2010 à 11:37

je le trie en moins de deux minutes, il booste pas mal son code.
je viens d'arreter le process, c'est trop long et çà bouffe tout le CPU.

Réponse 59 / 142

tpoinsot Messages postés 345 Date d'inscription mardi 1 juin 2004 Statut Membre Dernière intervention 17 octobre 2014 4
4 févr. 2010 à 16:48

Alors voici une version qui n'utilise qu'une seule passe mais il faut trier par tag car il sort une ligne à chaque changement de tag.

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"

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

static unsigned int hashKey(void* item)
{
unsigned int h = 0;
char *p = (char *)item;
while ( *p ) {
h = ((h << 5) + h) + *p++;
}
return h;
}

static int compareKey(void* k1, void* k2)
{
return !strcmp(k1, k2);
}

void initArray(ARR* a, int sz, int hsz)
{
a->size = 0;
a->allocSize = sz;
a->array = (char **) malloc(sizeof(char *) * sz);
a->h = create_hashtable(hsz, hashKey, compareKey);
}

void sortie(char *msg, int nret)
{
fprintf(stderr, msg);
exit(nret);
}

long findOrAddArray(ARR *arr, char *item)
{
long * pi = (long *)hashtable_search(arr->h, item);
if ( pi )
return *pi;

long i = arr->size;
int n = strlen(item);
char * key = malloc(n + 1 + sizeof(long));
strcpy(key, item);

pi = (long *)(&key[n + 1]);
*pi = i;

if ( arr->size == arr->allocSize ) {
arr->allocSize *= 2;
char ** p  = (char **) malloc(sizeof(char *) * arr->allocSize);
memcpy(p, arr->array, sizeof(char *) * arr->size);
free(arr->array);
arr->array = p;
}
arr->array[i] = key;
arr->size++;
hashtable_insert(arr->h, key, pi);
return i;
}

main(int argc, char *argv[])
{
ARR gsm;
initArray(&gsm, 500, 1000);

if ( argc != 2 )
sortie("il manque le fichier à traiter.", 1);

long i, j;
int fd;

if ( !(fd = open(argv[1],O_RDONLY)) )
sortie("erreur d'ouverture", 1);

struct stat st;
stat(argv[1], &st);
unsigned long fsz = st.st_size;
if ( fsz == 0 )
sortie("la taille du fichier est nulle", 1);

fprintf(stderr, "size = %d\n", fsz);
char *bufFile = malloc(st.st_size);
if ( !bufFile )
sortie("Erreur malloc bufFile\n", 2);

/*************************************/
int nr;
char *pbf, *p;
int n = 1;
long nl = 0;
long ncur = 0;
for (pbf = bufFile; (nr=read(fd, pbf, 1024)) > 0; pbf += nr )
{
for (p=pbf; p n*fsz )
{
fprintf(stderr, "lecture %d%%\r", n);
fflush(stderr);
n += 1;
}
}
*pbf = 0;
if ( pbf>bufFile && pbf[-1] )
nl++;
close(fd);

fprintf(stderr, "lecture 100%% NL=%d\r\n", nl);
if ( nl == 0 )
sortie("Fichier vide\n", 4);

/*************************************/
char **row = (char **)malloc(nl*sizeof(char *));
if ( !row )
sortie("Erreur malloc row\n", 2);

long *vgsm = (long *)malloc(nl*sizeof(long));
if ( !vgsm )
sortie("Erreur malloc vgsm\n", 2);

char **prow = row;
long *pvgsm = vgsm;

pbf = bufFile;
while ( *pbf )
{
*pvgsm = 0;
*prow = NULL;
i = strlen(pbf)+1;

if ( p = strtok(pbf, " ") ) {
*pvgsm = findOrAddArray(&gsm, p);
if ( (p=strtok(NULL, " ")) && strtok(NULL, " ") )
*prow = p; // pointe sur tag
}
prow++;
pvgsm++;
pbf += i;
}
if ( gsm.size == 0 )
sortie("Pas de gsm\n", 3);

/*************************************/
long *res = (long *)malloc(gsm.size * sizeof(long));
if ( !res ) 
sortie("Erreur malloc res\n", 2);

FILE *fpo = stdout;

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

char **irow;
char *curTag; //tag en cours
long *ivgsm = vgsm;
char *prevTag = NULL;
for (i=0, irow = row; i < nl && !(prevTag = *irow); i++, irow++)
;
memset(res, 0, gsm.size*sizeof(long)); // remise à 0

n = 1;
for (i=0, irow = row; i < nl; i++, irow++, ivgsm++)
{
if ( curTag = *irow )
{
if ( strcmp(curTag, prevTag) ) {
fprintf(fpo, "%s", prevTag);
for (j=0; j<gsm.size; j++)
fprintf(fpo, " %d", res[j]);
fprintf(fpo, "\n");

// Réinitialisation
prevTag = curTag;
memset(res, 0, gsm.size*sizeof(long)); // remise à 0
}
res[*ivgsm] = atol(curTag + strlen(curTag) + 1);
}

if ( i*100.0 > n*nl )
{
fprintf(stderr, "écriture %d%%\r", n);
fflush(stderr);
n += 1;
}
}

if ( nl > 0 ) {
fprintf(fpo, "%s", curTag);
for (j=0; j<gsm.size; j++)
fprintf(fpo, " %d", res[j]);
fprintf(fpo, "\n");
}

fprintf(stderr, "écriture 100%%\r\n");

/*************************************/
hashtable_destroy(gsm.h, 0);
free(gsm.array);
free(res);
free(bufFile);
exit(0);
}

thip

Réponse 60 / 142

mslider Messages postés 109 Date d'inscription jeudi 21 octobre 2004 Statut Membre Dernière intervention 7 mars 2010
4 févr. 2010 à 17:05

je vais essayé,
je vais le lancé pour voir.

voilà lancé le jeudi 4 à 17h:

size = 1595586743
lecture 100% NL=58859592

çà tourne, çà a l'air de bien tourner.

je te tiens au courant.

Discussions similaires

création mots croisés

Les tableaux - constructeur

Stockage de la date sytème dans un tableau

générer une grille de mots mêlés

initialisation tableau dans un constructeur

Votre réponse

Discussions similaires