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 61 / 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 à 20:59

traitement terminé à 18h22.
18270901 lignes ds le fichier resultat.

1h20 de traitement c pas mal.
tu penses que çà peut être amelioré ?

Réponse 62 / 142

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

oui, avec 60 millions de lignes, si on gagne 1 millionnième de seconde dans la boucle de sortie, c'est 1mn de gagné sur le résultat. C'est la chasse au gaspi.

Il y a 3 parties dans ce code :
1 - lecture et chargement en mémoire
2 - détermination du tableau gsm
3 - parcours des tags avec sortie

1 et 2 pourraient fusionner, mais il faudra faire des allocations unitaires et non en bloc.
Pour 3 c'est l'amélioration du code.
Met en commentaire les calculs de pourcentages et déjà tu gagneras.

La lecture, c'est rapide ?
et le temps entre le premier 100% (fin de 1) et le démarrage du compte de la partie 3 ?

thip

Réponse 63 / 142

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

Voici une version avec 4 fonctions de hash différentes.
j'ai mis des options pour la ligne de commande, avec -v pour afficher les infos, -k i pour utiliser la fonction H n° i;
exemple :
prog -v -k 1 sample.txt

tu peux faire un shell contenant
time prog -k 1 big_file.txt > x1
time prog -k 2 big_file.txt > x2
time prog -k 3 big_file.txt > x3
time prog -k 4 big_file.txt > x4

sur ma machine, c'est le 2 qui est le plus rapide.

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

extern int optind;
extern char *optarg;

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


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

static unsigned int hashKey2(void* item)
{
unsigned int hash = 0;
int c;
char *p = (char *)item;
while ( c = *p++ )
hash = c + (hash << 6) + (hash << 16) - hash;
return hash;
}

//#if sizeof(short)==2
//#define getint16(x) *((short *)x)
//#else
#define getint16(x) (((x)[0] << 8) | (x)[1])
//#endif

static unsigned int hashKey3(void* item)
{
char *p = (char *)item;
int len = strlen(item), tmp;
unsigned int hash = len;
int rem;

if (len <0 || item NULL) return 0;

rem = len & 3;
len >>= 2;

/* Main loop */
for (;len > 0; len--) {
hash  += (p[0] << 8) | p[1];
tmp    = (((p[2] << 8) | p[3]) << 11) ^ hash;
hash   = (hash << 16) ^ tmp;
p  += 2;
hash  += hash >> 11;
}

    /* Handle end cases */
switch (rem) {
case 3:
hash += (p[0] << 8) | p[1];
hash ^= hash << 16;
hash ^= p[2] << 18;
hash += hash >> 11;
break;
case 2:
hash += (p[0] << 8) | p[1];
hash ^= hash << 11;
hash += hash >> 17;
break;
case 1:
hash += p[0];
hash ^= hash << 10;
hash += hash >> 1;
}

/* Force "avalanching" of final 127 bits */
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 4;
hash += hash >> 17;
hash ^= hash << 25;
hash += hash >> 6;

return hash;
}

static unsigned int hashKey4(void* item)
{
char *p = (char *)item;
const unsigned int m = 0x5bd1e995;
const int r = 24;

long seed = 0xc58f1a7b;
int len = strlen(item), tmp;

if ( len == 0 )
return 0;

unsigned int hash = seed ^ len;
int rem = len & 3; // mod 4
len >>= 2; // div 4
for ( ; len > 0; len-- )
{
unsigned int k = *((short *)p);
k *= m;
k ^= k >> r;
k *= m;

hash *= m;
hash ^= k;
p += sizeof(short);
}

switch ( rem )
{
case 3:
hash ^= *((short *)p);
hash ^= (*((short *)(p+2))) << 16;
hash *= m;
break;
case 2:
hash ^= *((short *)p);
hash *= m;
break;
case 1:
hash ^= *((short *)p);
hash *= m;
break;
default:
break;
}

// Do a few final mixes of the hash to ensure the last few
// bytes are well-incorporated.

hash ^= hash >> 13;
hash *= m;
hash ^= hash >> 15;

return hash;
}

static int compareKey(void* k1, void* k2)
{
//return !strcmp(k1, k2);
char *p1 k1, *p2 k2;
while ( *p1 && *p1 == *p2 )
p1++, p2++;
return *p1 == *p2 ? 1 : 0;
}

unsigned int (*hashKey)(void* item);

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;
}

static void usage(const char *name)
{
    fprintf(stderr, "usage: %s [option]... Fichier_Entrée\n\n", name);
    fprintf(stderr, "options:\n");
    fprintf(stderr, " -h, --help     affiche ce message\n");
    fprintf(stderr, " -v, --verbose  version bavarde vers stderr\n\n");
}

main(int argc, char *argv[])
{
int opt;
int verbose = 0;
const char *prgName = argv[0];

hashKey = hashKey1;

while ( (opt = getopt(argc, argv, "hk:v")) != EOF ) {
switch ( opt ) {
case 'v':
verbose = 1;
break;

case 'k':
switch ( atoi(optarg) )
{
case 2:
hashKey = hashKey2;
break;
case 3:
hashKey = hashKey3;
break;
case 4:
hashKey = hashKey4;
break;
default:
hashKey = hashKey1;
break;
}
break;

case 'h':
usage(prgName);
exit(0);
break;

default:
usage(prgName);
exit(-1);
break;
}
}

argv += optind;
argc -= optind;

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

char *inFile = argv[0];
char *outFile = NULL;

if ( argc > 1 )
outFile = argv[1];

/*************************************/
ARR gsm;
initArray(&gsm, 500, 1000);

long i, j;
int fd;

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

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

if ( verbose )
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, 4096)) > 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);

if ( verbose )
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;
if ( outFile )
fpo = fopen(outFile, "w");
if ( !fpo )
{
fprintf(stderr, "%s: erreur d'ouverture, utilisation de stdout\n", outFile);
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;
int pfreq = strlen(prevTag)+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;
pfreq = strlen(prevTag) + 1;
memset(res, 0, gsm.size*sizeof(long)); // remise à 0
}
res[*ivgsm] = atol(curTag + pfreq);
}

if ( verbose && 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");
}

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

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

thip

Réponse 64 / 142

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

est ce que le fichier d'entrée doit être initialement trié ?

merci.

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

Posez votre question

Réponse 65 / 142

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

Oui, trié suivant le tag (second champ)

thip

Réponse 66 / 142

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

voilà ce que çà donne sur ma bécane pour sample.txt:

0.060u 0.005s 0:00.07 85.7% 0+0k 0+0io 0pf+0w
0.063u 0.004s 0:00.07 85.7% 0+0k 0+0io 0pf+0w
0.066u 0.006s 0:00.07 85.7% 0+0k 0+0io 0pf+0w
0.066u 0.002s 0:00.07 85.7% 0+0k 0+0io 0pf+0w

pour un fichier un peu plus gros de 1149068 lignes avec 4 librairies differentes

0.653u 0.126s 0:00.78 98.7% 0+0k 0+0io 0pf+0w
0.650u 0.131s 0:00.78 100.0% 0+0k 0+0io 0pf+0w
0.673u 0.131s 0:00.80 100.0% 0+0k 0+0io 0pf+0w
0.654u 0.148s 0:00.85 92.9% 0+0k 0+0io 0pf+0w

et pour le bigfile de 60000000 lignes:

3251.562u 175.209s 57:34.41 99.1% 0+0k 0+0io 0pf+0w
3236.541u 178.638s 57:24.22 99.1% 0+0k 0+0io 0pf+0w
3381.191u 185.791s 59:34.77 99.7% 0+0k 0+0io 0pf+0w
3359.511u 184.805s 1:01:42.08 95.7% 0+0k 0+0io 0pf+0w

Réponse 67 / 142

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

alors qu'est ce t'en penses ?
sur ma machine aussi c le 2 qui est le plus rapide non ?

Réponse 68 / 142

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

Oui mais ce n'est pas flagrant. Je suis déçu par H3 et H4 mais, finalement, c'est selon l'utilisation. Peu d'interrogation (contrairement à une base commerciale sollicitée en permanence) donc H2 permet un calcul plus rapide et une dispersion moyenne mais avec peu de conflit dans ces formes de données.

As-tu pu noter les temps, même approximatifs, des 3 parties du programme ?

thip

Réponse 69 / 142

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

stats avec l'option -v

voilà ce que çà donne sur ma bécane pour sample.txt:
size = 232551
lecture 100% NL=10000
écriture 100%
0.073u 0.006s 0:00.11 63.6% 0+0k 0+0io 2pf+0w
size = 232551
lecture 100% NL=10000
écriture 100%
0.070u 0.007s 0:00.08 87.5% 0+0k 0+0io 0pf+0w
size = 232551
lecture 100% NL=10000
écriture 100%
0.066u 0.008s 0:00.07 85.7% 0+0k 0+0io 0pf+0w
size = 232551
lecture 100% NL=10000
écriture 100%
0.063u 0.010s 0:00.07 100.0% 0+0k 0+0io 0pf+0w

pour un fichier un peu plus gros de 1149068 lignes avec 4 librairies differentes
size = 18599524
lecture 100% NL=1149068
écriture 100%
0.698u 0.145s 0:00.86 96.5% 0+0k 0+0io 0pf+0w
size = 18599524
lecture 100% NL=1149068
écriture 100%
0.649u 0.125s 0:01.11 68.4% 0+0k 0+0io 0pf+0w
size = 18599524
lecture 100% NL=1149068
écriture 100%
0.737u 0.109s 0:00.85 97.6% 0+0k 0+0io 0pf+0w
size = 18599524
lecture 100% NL=1149068
écriture 100%
0.651u 0.139s 0:00.79 98.7% 0+0k 0+0io 0pf+0w

et pour le bigfile de 60000000 lignes:

size = 1595586743
lecture 100% NL=58859592
écriture 100%
3239.486u 183.017s 57:27.91 99.2% 0+0k 0+0io 0pf+0w
size = 1595586743
lecture 100% NL=58859592
écriture 100%
3235.793u 175.632s 57:56.52 98.1% 0+0k 0+0io 0pf+0w
size = 1595586743
lecture 100% NL=58859592
écriture 100%
3366.359u 170.754s 1:16:14.63 77.3% 0+0k 0+0io 0pf+0w
size = 1595586743
lecture 100% NL=58859592
écriture 100%
3360.956u 179.829s 59:33.23 99.0% 0+0k 0+0io 0pf+0w

Réponse 70 / 142

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

Essaies ce code, c'est une approche un peu différente avec le H2. Ce code n'utilise pas la mémoire de manière directe, pour fonctionner sur ma machine. C'est ce que j'ai obtenu de plus rapide, et j'aimerai savoir ce que ça donne sur ton ordi.

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

extern int optind;
extern char *optarg;

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

long nComp 0, nHash 0;

static unsigned int hashKey(void* item)
{
unsigned int hash = 0;
int c;
char *p = (char *)item;
while ( c = *p++ ) {
//hash = ((hash << 5) + hash) + c;
hash = c + (hash << 6) + (hash << 16) - hash;
}
return hash;
}

static int compKey(void* k1, void* k2)
{
char *p1 = k1;
char *p2 = k2;
while ( *p1 && *p1 == *p2 )
p1++, p2++;
return *p1 == *p2 ? 1 : 0;
}

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

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));
memcpy(key, item, n);

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

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

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

static void usage(const char *name)
{
    fprintf(stderr, "usage: %s [option]... Fichier_Entrée\n\n", name);
    fprintf(stderr, "options:\n");
    fprintf(stderr, " -h, --help     affiche ce message\n");
    fprintf(stderr, " -v, --verbose  version bavarde vers stderr\n\n");
}

void outBuf(FILE *fp, char *t, char **s, int n, int bf)
{
char *p;
int j;

fputs(t, fp);
for (j=0; j<n; j++)
{
if ( p = *s++ ) {
fputc(' ', fp);
fputs(p, fp);
if ( bf )
free(p);
}
else
fputs(" 0", fp);
}
fputc('\n', fp);
}

main(int argc, char *argv[])
{
int opt;
int verbose = 0;
const char *prgName = argv[0];

while ( (opt = getopt(argc, argv, "hv")) != EOF ) {
switch ( opt ) {
case 'v':
verbose = 1;
break;

case 'h':
usage(prgName);
exit(0);
break;

default:
usage(prgName);
exit(-1);
break;
}
}

argv += optind;
argc -= optind;

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

char *inFile = argv[0];
char *outFile = NULL;

if ( argc > 1 )
outFile = argv[1];

/*************************************/
FILE *fp = fopen(inFile, "r");
if ( !fp )
sortie("erreur d'ouverture entrée", 1);

struct stat st;
stat(inFile, &st);
size_t fsz = st.st_size;
if ( fsz == 0 )
sortie("la taille du fichier est nulle", 1);

ARR gsm;
initArray(&gsm, 2500);

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

char buf[512];
char *pGsm, *pTag, *pFrq;

time_t t0, t1, t2;
long *pi;
char *p;
long i, j;
double n = 0;
double cx = 100.0/fsz;

time(&t0);

while ( fgets(buf, sizeof(buf), fp) ) 
{
if ( p = strchr(buf, ' ') )
{
*p = 0;
findOrAddArray(&gsm, buf);
}

if ( verbose && ftell(fp)*cx > n )
{
fprintf(stderr, "\rLecture %.0f%%", n);
fflush(stderr);
n += 1;
}
}

time(&t1);
if ( verbose )
fprintf(stderr, "\rLecture 100%%, %d s.\n", t1-t0);

/*************************************/
size_t szRes = gsm.size * sizeof(char *);
char **res = (char **) malloc( szRes );
char **pRes;
if ( !res )
sortie("Erreur malloc res\n", 2);
memset(res, 0, szRes);

FILE *fpo = stdout;
if ( outFile )
fpo = fopen(outFile, "w");
if ( !fpo ) {
fprintf(stderr, "erreur d'ouverture du fichier en sortie : utilisation de stdout\n");
fpo = stdout;
}

//setvbuf(fpo, NULL, _IOFBF, gsm.size * 128);

/*************************************/
outBuf(fpo, "etiquette", gsm.array, gsm.size, 0);

n = 0;
fseek(fp, 0, 0);

char oBuf[2][BUFSIZ];
int iBuf = 0;
char *pBuf = oBuf[0];
char *prevTag = NULL;

while ( fgets(pBuf, BUFSIZ, fp) ) 
{
strcpy(oBuf[1], oBuf[0]);
if ( pTag = strchr(pBuf, ' ') )
{
*pTag++ = 0;
if ( pFrq = strchr(pTag, ' ') )
{
*pFrq = 0;
prevTag = pTag;
iBuf = 1;
pBuf = oBuf[1];
break;
}
}
}

if ( prevTag )
{
do
{
if ( pTag = strchr(pBuf, ' ') )
{
*pTag++ = 0;
if ( pFrq = strchr(pTag, ' ') )
{
*pFrq++ = 0;
long *pi = (long *)hashtable_search(gsm.h, pBuf);
if ( strcmp(pTag, prevTag) )
{
outBuf(fpo, prevTag, res, gsm.size, 1);

// Réinitialisation
//strcpy(prevTag, pTag);
prevTag = pTag;
iBuf = 1 - iBuf;
pBuf = oBuf[iBuf];
memset(res, 0, szRes);
}

if ( pi )
{
int np = strlen(pFrq);
if ( np>0 && pFrq[np-1] == '\n' )
pFrq[np-1] = 0;
p = malloc(np);
memcpy(p, pFrq, np);
res[*pi] = p;
}
}
}

if ( verbose && ftell(fp)*cx > n )
{
time(&t2);
fprintf(stderr, "\rEcriture %.1f%% %d s.", n, t2-t1);
fflush(stderr);
n += 0.1;
}
} while ( fgets(pBuf, BUFSIZ, fp) );

outBuf(fpo, prevTag, res, gsm.size, 1);
}

fclose(fp);
fclose(fpo);

time(&t2);
if ( verbose )
fprintf(stderr, "\rEcriture 100%%, %d s\n", t2-t1);

/*************************************/
if ( verbose )
fprintf(stderr, "temp: %d'%02d\n", (t2-t0)/60, (t2-t0)%60);

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

thip

Réponse 71 / 142

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

voilà ce que çà donne sur ma bécane pour sample.txt:

0.030u 0.017s 0:03.85 1.0% 0+0k 0+0io 0pf+0w

pour un fichier un peu plus gros de 1149068 lignes avec 4 librairies differentes

0.659u 1.075s 0:37.90 4.5% 0+0k 0+0io 0pf+0w

et pour le bigfile de 60000000 lignes:

3236.541u 178.638s 57:24.22 99.1% 0+0k 0+0io 0pf+0w

çà va pas plus vite que la version précédente sur ma bécane.

2 heures que çà tourne et c pas encore fini...

Réponse 72 / 142

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

Dommage, j'aimais bien le concept, et ça fonctionnait même sur ma bécane en moins de 5h ! je rappelle que j'ai fait ça sur un pentium 500 avec 256Mo en RAM !

Il y a tout de même des idées à reprendre dans cette version.

thip

Réponse 73 / 142

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

pourquoi çà devrait aller plus vite ?
ce qui est bizarre c que sur ta bécane çà va plus vite mais pas sur la mienne.

Réponse 74 / 142

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

Oui, bizarre, mais on ne va pas chercher la raison.
En prenant le meilleur des 2 systèmes :

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

extern int optind;
extern char *optarg;

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

static unsigned int hashKey(void* item)
{
unsigned int hash = 0;
int c;
char *p = (char *)item;
while ( c = *p++ )
{
//hash = c + (hash << 5) + hash;
hash = c + (hash << 5) + (hash << 11) - hash;
}
return hash;
}

static int compareKey(void* k1, void* k2)
{
char *p1 k1, *p2 k2;
while ( *p1 && *p1 == *p2 )
p1++, p2++;
return *p1 == *p2 ? 1 : 0;
}

void initArray(ARR* a, int sz)
{
a->size = 0;
a->allocSize = sz;
a->array = (char **) malloc(sizeof(char *) * sz);
a->h = create_hashtable(sz, 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));
memcpy(key, item, n+1);

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;
}

void outBuf(FILE *fp, char *t, char **s, int n)
{
char *p;

fputs(t, fp);
while ( n-- > 0 )
{
if ( p = *s++ ) {
fputc(' ', fp);
fputs(p, fp);
}
else
fputs(" 0", fp);
}
fputc('\n', fp);
}


static void usage(const char *name)
{
    fprintf(stderr, "usage: %s [option]... Fichier_Entrée\n\n", name);
    fprintf(stderr, "options:\n");
    fprintf(stderr, " -h, --help     affiche ce message\n");
    fprintf(stderr, " -v, --verbose  version bavarde vers stderr\n\n");
}

main(int argc, char *argv[])
{
int opt;
int verbose = 0;
const char *prgName = argv[0];
time_t t0, t1, t2;

while ( (opt = getopt(argc, argv, "hv")) != EOF ) {
switch ( opt ) {
case 'v':
verbose = 1;
break;

case 'h':
usage(prgName);
exit(0);
break;

default:
usage(prgName);
exit(-1);
break;
}
}

argv += optind;
argc -= optind;

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

char *inFile = argv[0];
char *outFile = NULL;

if ( argc > 1 )
outFile = argv[1];

/*************************************/
time(&t0);

ARR gsm;
initArray(&gsm, 3000);

long i, j;
int fd;

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

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

if ( verbose )
fprintf(stderr, "size = %d\n", fsz);

char *bufFile = malloc(st.st_size);
if ( !bufFile )
sortie("Erreur malloc bufFile\n", 2);

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

if ( verbose )
{
time(&t1);
fprintf(stderr, "\rLecture 100%% NL=%d t=%d'%02d\r\n", nl, (t1-t0)/60, (t1-t0)%60);
}

if ( nl == 0 )
sortie("Fichier vide\n", 4);

/* TRAITEMENT ************************************/
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);

if ( verbose )
{
time(&t2);
fprintf(stderr, "\rTraitement t=%d'%02d\r\n", (t2-t1)/60, (t2-t1)%60);
t1 = t2;
}

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

FILE *fpo = stdout;
if ( outFile )
fpo = fopen(outFile, "w");
if ( !fpo )
{
fprintf(stderr, "%s: erreur d'ouverture, utilisation de stdout\n", outFile);
fpo = stdout;
}

outBuf(fpo, "etiquette", gsm.array, gsm.size);

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, szRes); // remise à 0

n = 1;
int pfreq = strlen(prevTag)+1;
for (i=0, irow = row; i < nl; i++, irow++, ivgsm++)
{
if ( curTag = *irow )
{
if ( strcmp(curTag, prevTag) )
{
outBuf(fpo, prevTag, res, gsm.size);

// Réinitialisation
prevTag = curTag;
pfreq = strlen(curTag) + 1;
memset(res, 0, szRes); // remise à 0
}
res[*ivgsm] = curTag + pfreq;
}

if ( verbose && i*100.0/nl > n )
{
fprintf(stderr, "\rEcriture %d%%", n);
fflush(stderr);
n += 1;
}
}

if ( nl > 0 )
{
outBuf(fpo, prevTag, res, gsm.size);
}
fclose(fpo);

if ( verbose )
{
time(&t2);
fprintf(stderr, "\rEcriture 100%% t=%d'%02d\r\n", (t2-t1)/60, (t2-t1)%60);
fprintf(stderr, "Total t=%d'%02d\r\n", (t2-t0)/60, (t2-t0)%60);
}

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

thip

Réponse 75 / 142

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

voilà ce que çà donne sur ma bécane pour sample.txt:

0.030u 0.017s 0:03.85 1.0% 0+0k 0+0io 0pf+0w
0.021u 0.029s 0:09.21 0.4% 0+0k 0+0io 0pf+0w (plus long que la précédente)

pour un fichier un peu plus gros de 1149068 lignes avec 4 librairies differentes

0.659u 1.075s 0:37.90 4.5% 0+0k 0+0io 0pf+0w
0.574u 1.029s 1:50.91 1.4% 0+0k 0+0io 0pf+0w (idem c plus long)

je fais le test sur le bigfile.

je refais un test en utilisant ton ancien programme avec l'option -k 2 sur le fichier de
1149068 lignes, et voilà:

0.794u 0.963s 1:43.80 1.6% 0+0k 0+0io 2pf+0wpas

Réponse 76 / 142

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

Là je ne te suis plus. Les 2 derniers sont plus rapides sur ma machine que les précédents.
Au fait, j'ai viré l'option -k, tu n'as pas eu d'erreur ?

Si tu reprends le code de la fin de la page 7, c'est toujours à 1h20 ?
Si c'est le cas je repars de cette version pour intégrer mes dernières idées.

thip

Réponse 77 / 142

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

ya pas photo c bien le dernier code de la page 7 utilisé
avec l'option -k 2 qui est le plus rapide.

Au fait j'y pensais pourquoi ne pas utiliser plusieurs processeurs
pour résoudre le problème, diviser pour règner çà marche bien en général.

Regarde sur ce post:
"tri alphabétique ultra rapide de chaines
de caractères de longueur variable"
(http://www.cppfrance.com/forum/sujet-TRI-ALPHABETIQUE-ULTRA-RAPIDE-CHAINES-CARACTERES-LONGUEUR-VARIABLE_1359742.aspx?p=3)

Dobel utilise la librairie pthread, résultat des courses, voilà son code ici: http://pastebin.com/f1fceff27
et sur ma bécane un fichier de 80 000 000 de lignes (1.5 Go !) est
trié en 2 minutes, çà dépote à mort.
Le souci c'est qu'il faut avoir une machine multicoeur et c'est pas ton cas donc tu peux pas tester le code.
Mais l'idée est bonne: affecter une partie du fichier à traiter sur chaque processeur, puis regrouper les résultats à la fin.

je pense qu'en combinant tes idées et celles du code de Dobel on doit aboutir à un code béton.

slider

Réponse 78 / 142

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

Le problème vient du hash : j'ai changé les coefficients pour avoir une meilleure dispersion. Sur ma machine 32 bits, les "int" font 32 bits; sur la tienne, c'est 64.
Bref le résultat du hashing n'est pas le même sur les 2 machines à cause des décalages de bits qui sont utilisés. Au delà de 32, j'ai des zéros mais pas toi !

Pour le multithread, je n'y crois pas trop car dans le cas d'un tri par la méthode des pivots (je crois me souvenir que c'était sa méthode), une fois que tu as un pivot tu as un code travaillant sur des parties de données totalement séparées. Ici, tout est séquentiel, mais il faut essayer. On verra avec un coeur pour les E/S et un pour le reste.

Avant, je propose d'améliorer le code : le programme fait 80M d'atol() puis 18M de fprintf("%d" pour retransformer en string !
De plus je faisais des fprintf alors que fputs est plus rapide.

Alors, il faut faire :

size_t szRes = gsm.size * sizeof(char *);
char **res = (char **)malloc(szRes);
if ( !res ) 
sortie("Erreur malloc res\n", 2);
// ajouter ci-dessous : je recopierai res0 dans res pour éviter une grosse boucle
char **res0 = (char **)malloc(szRes);
if ( !res0 ) 
sortie("Erreur malloc res0\n", 2);
char *zero = "0"; // plus besoin d' if/else sur les pointeurs nuls
for (i=0; i<gsm.size; i++) res0[i] = zero;

puis

for (i=0, irow = row; i < nl && !(prevTag = *irow); i++, irow++)
;
// On ne fait plus : memset(res, 0, gsm.size*sizeof(long)); // remise à 0
memcpy(res, res0, szRes); // remise à 0

n = 1;
int pfreq = strlen(prevTag)+1;
for (i=0, irow = row; i < nl; i++, irow++, ivgsm++)
{

plus loin

// Réinitialisation
prevTag = curTag;
pfreq = strlen(curTag) + 1;
//memset(res, 0, szRes); supprimé et remplacé par :
memcpy(res, req0, szRes); // remise à 0

et enfin

res[*ivgsm] = curTag + pfreq; // et non plus : atol(curTag + pfreq);

et pour finir, la boucle de sortie devient en gardant l'appel à la fonction :

void outBuf(FILE *fp, char *t, char **s, int n)
{
fputs(t, fp);
while ( n-- > 0 )
{
fputc(' ', fp);
fputs(*s++, fp);
}
fputc('\n', fp);
}

thip

Réponse 79 / 142

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

en intégrant tes denières modifs voilà ce que çà donne:

pour sample.txt:
0.026u 0.018s 0:11.28 0.2% 0+0k 0+0io 0pf+0w

pour le fichier plus gros de 1149068 lignes avec 4 librairies differentes:
0.557u 1.108s 2:22.45 1.1% 0+0k 0+0io 0pf+0w

en effet on retombe sur la vitesse d'execution du programme de la page 7.

Réponse 80 / 142

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

As-tu bien intégré les modifs dans le programme de la page 7 ?

Sinon vérifie que la fonction de hashing est bien :

		hash = c + (hash << 6) + (hash << 16) - hash;

6 et 16 et non 5 et 11

thip

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