choix du structure des données

Marsh Posté le 01-11-2009 à 16:32:26

Bonjour,

Je vais refaire une grande partie de mon travail car j'ai mal choisi les structures des données car les accès fichiers sont plus coûteux. Tout mon travail se base sur les fichiers même les résultats
intermédiaires. Le but de mon travail est de trouver une solution à mon problème mais de plus minimiser le plus possible le temps d'exécution (le mesure le temps en utilisant la fonction 'clock()'.

Mais, lorsque j'ai testé le temps de l'exécution concernant la comparaison de deux fichiers selon les critères bien définis alors j'ai remarqué que le temps est devenir très longue si nous avons des fichiers avec des centaines lignes. On va lire chaque ligne de fichier 1 et le compare avec tous les lignes de fichier 2. C'est très couteux.

D'après vous :
- Avec quelles structures des données ces deux fichiers seront remplacés ?

- En général,quelle est la structure des données la moins couteuse en
mémoire et donc temps d'exécution le plus inférieur possible ?

Je souhaite que vous m'aidez.

Merci.

Reply

Marsh Posté le 01-11-2009 à 16:32:26

Reply

Marsh Posté le 01-11-2009 à 16:58:05

je comprends rien, tu pourrais pas donner encore moins de details ?

Reply

Marsh Posté le 01-11-2009 à 17:43:27

Bonjour,

Dans mon programme C, la fonction de comparaison est :

Code :

*rets = compare_files("f.txt", "f2.txt" );

Je passe deux fichiers "f.txt" et "f2.txt" à la fonction 'compare_files'
la taille de "f.txt" est toujours plus grande que "f2.txt".
chaque ligne de deux fichiers contient une chaine de caractère.

Je cherche les lignes qui appartiennent à "f.txt" et non pas "f2.txt"
C'est une sorte de différence lignes de "f.txt" moins lignes de "f2.txt"
à condition:
Une ligne de "f.txt" est identique à une ligne de "f2.txt"
si les deux lignes ont la même valeur et le même nombre des mots qui forment les deux lignes quelque soit l'ordre des mots puisque l'ordre des mots n'est pas important dans mon problème.
le plus important c'est : la même valeur et le même nombre

Sinon c'est à dire les deux lignes n'ont pas la même valeur et le même nombre des mots alors dans ce cas les deux lignes sont différentes.

par exemple:
"nom prenom age" = "nom age prenom"

Sachant que chaque ligne du deux fichiers "f.txt" et "f2.txt" est composé d'un seul champ (une chaine de caractères)

Soit le premier fichier fichier "f.txt":
nom prenom
nom age
prenom age
prenom emploi
nom prenom age
nom emploi
age emploi
prenom age emploi
nom age emploi
nom prenom emploi
nom prenom age emploi

Soit le deuxième fichier "f2.txt":

nom
prenom
age
emploi
age nom
nom age prenom
nom emploi
age emploi
prenom age emploi
nom prenom emploi

On applique le principe de comparaison alors on obtient ce résultat intermédiaire:
nom prenom
nom age emploi
nom prenom age emploi

Puis, on garde de ce résultat que les chaines qui ne contiennent pas autre chaine de ce résultat.
ici, on ne garde pas la chaine "nom prenom age emploi" car elle contienne la chaine "nom prenom"
Le résultat final souhaité obtenu est :
nom prenom
nom age emploi

Voici le code de la fonction 'compare_files'

Code :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define OUTPUT_NAME "finalresult.txt"
/* Nom du fichier dans lequel le resultat est stocké */
#define MAX_SIZE 1024
/* Taille maximale d'une ligne du fichier */
/** Teste le retour de realloc et quitte le programme si besoin */
void * xrealloc(void * prec, size_t len)
{
void *ret = realloc(prec, len);
if(!ret) /* Equivaut à if(ret == NULL) */
exit(0xDEAD);
return ret;
}
/** Copie n caractère de str dans une nouvelle chaine alloué dynamiquement, et renvoie cette chaine */
char * mstrndup(const char *str, size_t n)
{
char *ret = malloc((n+1) * sizeof(char));
if (!ret)
exit(0xDEAD);
strncpy(ret, str, n); /* Copie n caractère de str dans n */
ret[n] = 0; /* 0 == '\0' */
return ret;
}
/** Libère le tableau de chaine de caractère t de len chaine de caractère */
void free_tab(char **t, size_t len)
{
if (t)
{
size_t i;
for (i = 0; i < len; i++)
free(t[i]);
free(t);
}
}
/** Libère le tableau de chaine de caractère t et s'arrête lorsqu'un pointeur NULL est rencontré */
void free_tab2(char **t)
{
size_t i = 0;
while (t && t[i])
free(t[i++]);
free(t);
}
/** Compte le nombre de mot dans str (un mot correspond à une suite de lettre et s'arrête dès qu'un caractère autre est rencontré */
size_t count_word(const char *str)
{
size_t n = 0;
int a;
while (*str) /* Equivaut à while(*str != '\0') */
{
a = 0; /* Cette variable sert à indiquer si au moins une lettre a été trouvé (pour éviter les lignes vides) */
while (isalpha((unsigned char) *str) && *str) str++, a = 1; /* Tant que c'est une lettre et que ce n'est pas la fin de la chaine, on parcourt la chaine
et on met a à 1 pour indiquer qu'on a trouvé au moins une lettre */
if (a) n++; /* Si on a trouvé au moins une lettre, on augmente le nombre de mot */
while (!isalpha((unsigned char) *str) && *str) str++; /* On saute tous les caractères qui ne sont pas des lettres */
}
return n;
}
/** copie les mots de la chaine str dans le tableau de chaine de caractère tab */
void get_word(char **tab, const char *str)
{
const char* p = str;
int a, i = 0;
/* Le fonctionnement est le même que pour la fonction count_word mais ici on enregistre la chaien dans un tableau. On pourrait le faire en une seule
fonction mais il faudrai à chaque fois réallouer de la mémoire et ce n'est pas très propre */
while (*str)
{
a = 0;
while (isalpha((unsigned char) *p) && *p) p++, a = 1;
if (a)
tab[i++] = mstrndup(str, p-str); /* Si on a trouvé un mot, on met dans tab[i] le mot (la suite de lettre trouvé) et on incrémente i.
p-str correspond à la taille du mot, c'est l'adresse du caractère suivant le dernier caractère moins l'adresse du premier caractère */
while (!isalpha((unsigned char) *p) && *p) p++;
str = p;
}
}
/** Compare deux tableaux de mots, renvoie 1 si ces tableaux sont identiques sans tenir compte de l'ordre ni du nombre de mot, 0 sinon (En fait, il renvoie 1
si chaque ligne de t1 existe dans t2) */
int compareline(char **t1, size_t size1, char **t2, size_t size2)
{
int ret = 1;
size_t i, j;
int a;
/* Pour chaque ligne de t1, on compare avec chaque ligne de t2. Si à un moment on ne trouve pas la ligne, alors les tableaux ne sont pas identiques */
for (i = 0; i < size1; i++)
{
a = 0;
for (j = 0; j < size2; j++)
if (!strcmp(t1[i], t2[j]))
{
a = 1;
break; /* Dès que la ligne est trouvé, on peux arrêter de comparer pour cette valeur du tableau */
}
if (!a)
{
ret = 0;
break; /* Dès qu'une ligne manque, on peux arrêter la comparaison */
}
}
return ret;
}
/** Compare deux chaines de caractère, si comparesize vaut 1 alors la première doit contenir la seconde, et renvoie 1 si elles sont identiques sans tenir
compte de l'ordre des mots */
int is_same(const char *s1, const char *s2, int comparesize)
{
char **t1, **t2;
size_t size1 = count_word(s1), size2 = count_word(s2);
int ret = 0;
if (!comparesize || (size1 > size2)) /* Si comparesize vaut 0, on ne compare pas la taille, si comparesize vaut 1 alors il faut que size1 > size 2 */
{
t1 = malloc(size1 * sizeof(char*));
t2 = malloc(size2 * sizeof(char*));
if (t1 && t2)
{
get_word(t1, s1);
get_word(t2, s2);
ret = comparesize? compareline(t2, size2, t1, size1) : compareline(t1, size1, t2, size2);
free_tab(t1, size1), free_tab(t2, size2);
}
else
exit(0xDEAD);
}
return ret;
}
/** Compare deux fichiers er renvoie le résultat de la comparaison */
char ** compare_files(const char *filename1, const char *filename2)
{
FILE *f = fopen(filename1, "r" ), *f2 = fopen(filename2, "r" );
char s[MAX_SIZE], s2[MAX_SIZE];
int a, retsize = 0;
char **ret = NULL;
if (f && f2) /* Si les fichiers sont bien ouverts */
{
while (fgets(s, MAX_SIZE, f)) /* C'est la même principe que dans la fonction compareline en fait */
{
a = 0;
rewind(f2);
while (fgets(s2, MAX_SIZE, f2))
if (is_same(s, s2, 0))
{
a = 1;
break;
}
if (!a)
{
ret = xrealloc(ret, (++retsize) * sizeof(char*)); /* On alloue une case de plus au tableau de string, puis on ajoute la chaine à la fin du tableau */
ret[retsize-1] = mstrndup(s, strlen(s));
}
}
fclose(f), fclose(f2);
ret = xrealloc(ret, (++retsize) * sizeof(char*)); /* On ajoute un dernier pointeur sur NULL pour savoir quand le tableau se termine */
ret[retsize-1] = NULL;
}
else /* Si un fichier n'a pas pu être ouvert, on ferme eventuellement le fichier qui a pu être ouvert */
{
if (f) fclose(f);
if (f2) fclose(f2);
}
return ret;
}
/** Ecrit le tableau de len chaines de caractère dans le flux f */
void write_tab(FILE *f, char **t, size_t len)
{
size_t i;
for (i = 0; t && i < len; i++)
if (t[i])
fprintf(f, t[i]);
}
void disp_tab(char **t)
{
size_t i;
for (i = 0; t && t[i]; i++)
printf(t[i]);
}
int main(void)
{
#define MAXFILE 3
/* Le nombre de fichier à comparer, on compare f.txt à f1.txt, f2.txt etc... */
#define MAXTMP 10
/* La taille maximum du nom de fichier */
#define N 4
char **rets[MAXFILE] = {NULL}, tmp[MAXTMP];
char **interret = NULL;
size_t interret_size = 0;
int i,j,k;
int a, b;
int equN = 0, equN1 = 0, equothr = 0, equi = 0;
FILE *output;
*rets = compare_files("f.txt", "f1.txt" );
i = 0;
while(*rets && (*rets)[i]) /* On teste toutes les lignes */
{
a = count_word((*rets)[i]); /* On récupère le nombre de mot */
if(a == N) /* Si il vaut N, on augmente le "compteur de N" et on enregistre la position de la chaine, pour pouvoir la supprimer ensuite sans avoir
à reparcourir la tableau (gain de temps) */
equN++, equi = i;
else if (a == (N-1)) /* S'il vaut N-1, on augmente le "compteur de N-1" */
equN1++;
else if (a < (N-1))
equothr = 1; /* S'il y a une ligne qui comporte moins de N-1 mot, alors on utilise la méthode classique */
i++;
}
if(equN == 1 && !equothr) /* S'il y a exactement 1 ligne avec N mots et pas de ligne comportant moins de (N-1) mot*/
{
if(equN1) /* S'il y a au moins 1 ligne de (N-1) mots (s'il n'y en a pas 0 en fait) */
{
interret = *rets; /* Le resultat final est la premiere comparaison */
interret_size = i; /* La taille du tableau */
free((*rets)[equi]), (*rets)[equi] = NULL; /* On supprime la ligne contenant N mots */
}
else /* Sinon, on ne récupère que la premiere ligne */
{
interret = *rets;
interret_size = 1;
for(i = 1; rets[0][i]; i++)
free(rets[0][i]), rets[0][i] = NULL;
}
}
else
{
for (i = 1; i < MAXFILE; i++) /* Pour chaque fichier */
{
sprintf(tmp, "f%d.txt", i+1);
rets[i] = compare_files("f.txt", tmp); /* On comparer f.txt avec f%d.txt où %d est un nombre de 1 à MAXFILE */
/*disp_tab(rets[i]);
getchar();*/
}
i = 0;
while (rets[0] && rets[0][i]) /* Tant que ça ne vaut pas NULL */
{
a = b = 0;
for (j = 1; j < MAXFILE; j++) /* On compare le premier avec tous les autres */
{
k = 0;
while (rets[j] && rets[j][k]) /* On parcourt le tableau en entier (je rappelle qu'il est terminé par NULL */
{
if (!strcmp(rets[0][i], rets[j][k])) /* Si on trouve une ligne identique */
{
a = 1; /* On met a à 1, c'est à dire que la ligne rets[0][i] existe dans ret[j] */
break;
}
k++;
}
if (!a) /* Si on a pas trouvé la ligne, alors on met b à 1, ça veux dire que la ligne du tableau n'existe pas dans tous les autres tableaux */
{
b = 1;
break;
}
}
if (!b) /* Si b vaut 0 (on a trouvé la ligne ret[0][i] dans tous les tableaux ret[j] avec 0 < j < MAXFILE) */
{
interret = xrealloc(interret, (++interret_size) * sizeof(char*));
interret[interret_size-1] = mstrndup(rets[0][i], strlen(rets[0][i])); /* On recopie la ligne dans un nouveau tableau */
}
i++;
}
for (i = 0; i < MAXFILE; i++) /* On nettoie les tableaux issus des comparaison maistenant que l'intersection a été faite */
free_tab2(rets[i]);
for (i = 0; i < interret_size; i++) /* Pour chaque case du tableau... */
{
for (j = 0; interret[i] && j < interret_size; j++) /* On compare avec toutes les cases tant que la case actuelle ne vaut pas NULL */
{
if (interret[j] && j != i) /* Si la case qu'on veux comparer ne vaut pas NULL et que i est différent de j (sinon on compare la même case!) */
if (is_same(interret[i], interret[j], 1)) /* Si interret[j] est inclu dans interret[i] */
{
free(interret[i]), interret[i] = NULL; /* On supprime la case */
break;
}
}
}
}
if((output = fopen(OUTPUT_NAME, "w+" )) != NULL) /* On ouvre le fichier et on écrit le résultat si le fichier a bien été ouvert */
{
write_tab(output, interret, interret_size);
fclose(output);
}
free_tab(interret, interret_size); /* On nettoie le dernier tableau */
return 0;
}

Que proposez vous ?

Merci.

Message édité par msedirim le 01-11-2009 à 17:45:28

Reply

Marsh Posté le 01-11-2009 à 17:53:39

Deja ecris des fonctions au lieu de bananer tout dans un main imbitable.
Et quel est l'itneret de tes fonctions qui wrappe la libc ?

Reply

Marsh Posté le 01-11-2009 à 18:31:02

C'est lent comment?
Tes fichiers sont gros comment? Est ce que tu peux les faire tenir en mémoire plutot que de les relire n1*n2 fois?
Est-ce que tu ne pourrais pas remplacer tes chaines de caractères par des trucs qui les représenteraient de façon unique (des checksums peut-être???) et dont la comparaison serait plus rapide? (faut demander à quelqu'un d'autre que moi pour ces aspects)

Reply

Marsh Posté le 01-11-2009 à 21:08:25

Citation :

C'est lent comment?

Lorsque je mesure le temps d'exécution de ce traitement de comparaison en utilisant la fonction 'clock()' alors j'obtiens un temps plus élevé même des milliers de secondes pour un fichier de centaines des lignes.

Code :

debut = clock();
//comparaison entre deux fichiers
fin = clock();
fprintf(stderr, "temps : %f\n", (double)(fin-debut) / (double) CLOCKS_PER_SEC);

Citation :

Tes fichiers sont gros comment? Est ce que tu peux les faire tenir en mémoire plutot que de les relire n1*n2 fois?

Le fichier peut contenir des centaines de lignes et chaque ligne contient une chaine de caractère (ensemble des mots).
Je voulais les les faire tenir en mémoire mais comment faire ceci ? et avec quelle structure des données on peut faire ceci?

Citation :

Est-ce que tu ne pourrais pas remplacer tes chaines de caractères par des trucs qui les représenteraient de façon unique (des checksums peut-être???) et dont la comparaison serait plus rapide?

Reply

Marsh Posté le 02-11-2009 à 07:48:56

regarde peut-être du coté des listes chainées?

Message édité par GrosBocdel le 02-11-2009 à 07:49:06

Reply

Marsh Posté le 03-11-2009 à 09:51:20

Bonjour,

J'ai trouvé sur le net que le tableau est plus rapide que la liste chainée au niveau accès.
C'est vraie ? Sinon, pourquoi ?

Message cité 1 fois

Reply

Marsh Posté le 03-11-2009 à 20:07:36

msedirim a écrit :

Bonjour,

J'ai trouvé sur le net que le tableau est plus rapide que la liste chainée au niveau accès.
C'est vraie ? Sinon, pourquoi ?

Oh, ptet bien.
Si tu veux accéder à n'importe quel élément de ton ensemble de données, le tableau sera plus rapide car on y accède directement par tab[i], alors que pour ta liste chainée, il faut parcourir tous les éléments qui le précèdent

Seulement là:
-Tu ne connais pas le nombre d'éléments de ton fichier1 et de ton fichier2, alors tu leur donnes quelle taille initiale à tes tableaux?
-Tu cherches des doublons dans tes données : avec ta liste chainée, tu peux les supprimer, tes comparaisons s'accélèrent au fur et à mesure puisqu'il y a moins d'éléments, et à la fin de ton algo, il ne te reste que tes éléments uniques.
-Tu dois de toute façon regarder tous tes éléments un par un.

Ptet bien autre chose.

Reply

choix du structure des données

Sujets relatifs:

Leave a Replay