realloc par blocs

Version imprimable

realloc par blocs

Salut a tous,

Voila, je lis un fichier texte ligne par ligne dont je connais pas le nombre de ligne. Je pourrais lire le fichier une 1ere fois pour determiner le nombre de ligne et faire un malloc ensuite. mais pour de gros fichier, ce la peut etre lourd (je parle de fichiers de + de 2 milions de lignes)

Une autre solution est d'utiliser un malloc initial suivit de realloc a chaque ligne. Mais cela peut etre aussi lourd (voire meme plus que lire le fichier 2 fois)
Une solution serait de faire ca par bloque de N (avec N=1 milion par example)
Si on atteint la fin du 1er bloque, on aggrandit la table de N.

ci-joint un code qui simule une lecture de fichier par une boucle for de i=0 a 45 en remplissant des tables avec tab[i]=1.5*i et name[i]="blabla"
(la je connais la longueur pour debuger plus facilement). ca fonctionne bien avec ma table de double, mais pas avec ma table de *char

je ne pense que je ne fais pas les realloc correctement...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include <stdio.h> #include <stdlib.h> #include <string.h> int main() { double *tab; char **name; int N=10; int j=0,ii=0,i=0,k=1; tab = (double*)malloc((N*k) * sizeof (double)); name = (char**)malloc((N*k) * sizeof (*name)); for(i=0;i<(N*k);i++){name[i] = (char*)malloc(10 * sizeof (**name));} for(i=0;i<45;i++){ /*loop starts*/ tab[i] = 1.5*i; name[i] = "blabla"; if((i+1)%(N)==0){ /*if initial allocation filled up*/ /*realloc some more memory */ k++; printf("realloc at %d \n",N*k); tab = (double*)realloc(tab,(N*k) * sizeof (double)); name = (char**)realloc(name,(N*k) * sizeof (*name)); for(ii=0;ii<(N*k);ii++){name[ii] = (char*)realloc(name[ii],10 * sizeof (**name));} } j++; } /*loop ends*/ if(N*k>j){ /*if realloced too much memory*/ /*realloc down to the right value*/ printf("final realloc at %d",j); tab = (double*)realloc(tab,j * sizeof (double)); name = (char**)realloc(name,(j+1) * sizeof (*name)); for(ii=0;ii<(j+1);ii++){name[ii] = (char*)realloc(name[ii],10 * sizeof (**name));} } /* printf("\n\n"); for(i=0;i<j;i++){ printf("tab[%d]=%f\n",i,tab[i]); //printf("name[%d]=%s\n",i,name[i]); } */ return 0; }
J'esperes que j'etais clair...

merci d'avance

Dave

05/07/2007, 22h28
Médinoc

Déjà, il y a beaucoup plus de casts qu'il n'est censé y en avoir dans un programme C.
Commence par supprimer les casts des retours de malloc(), on y verra plus clair.

Ensuite, pour le fonctionnement du realloc(), tu t'en sers mal en effet: En cas d'échec, la mémoire existante est leakée...
Tu peux t'inspirer de ce que j'ai posté dans ce thread:
http://www.developpez.net/forums/sho...d.php?t=248441

PS: Tu devrais donner des noms plus explicites à tes variables.
05/07/2007, 22h36
dmichel

qu'est que tu veux dire par casts ?

Le cast est une conversion de type ;)

Dans ton cas ce sont par exemple :

Code:

name = (char**)malloc((N*k) * sizeof (*name));

qui peut être simplifié en :
Code:

1 2 3 4 /* L'opérateur sizeof ne peut être appliqué à un pointeur je pense... du moins le résultat n'est ss doute pas celui auquel tu t'attends */ name = malloc (N * k * (strlen (name) + 1));

05/07/2007, 22h42
Médinoc

Code:

tab = (double*)malloc((N*k) * sizeof (double));

Le cast en (double*) est inutile en C.
Si ça ne compile pas sans, c'est que tu compiles en C++.
05/07/2007, 23h00
dmichel

Citation:

Envoyé par Médinoc

Tu peux t'inspirer de ce que j'ai posté dans ce thread:
http://www.developpez.net/forums/sho...d.php?t=248441

ok je verais ca demain

voila, j'ai modifier ce p'tit bout de code mais j'ai simplement pris en compte un pointer simple de double. (On verra plus tard avec le char **name...).

J'ai rajouter des verifications pour les retours de malloc() et realloc(). J'ai aussi utilise un pointer temporaire (double *tmp) pour eviter de perdre le pointer principal en cas d'erreur.

Qu'en pensez-vous ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define oops(s)          { perror((s)); exit(1); }
 
int main()
{
 
double *tab;
double *tmp;
 
 
int i;
int n = 10;
int increment = 5;
int current_size=0;
int isecret;
 
/*initial dynamic allocation*/
tab=malloc(sizeof(double)*n);
if(tab==NULL){oops("Error: malloc()");} 
 
 
/*----loop starts----*/
 
isecret  = rand() % 100 + 1;
for(i=0;i<isecret;i++){ 
 
    tab[i] = rand() % 10;
 
    printf("current_size=%d  n=%d\n",current_size,n);
 
    if(current_size>=(n-1)){ /*if initial allocation filled up*/
 
        printf("realloc at %d\n",n+increment);               
 
        tmp=realloc(tab,sizeof(double)*(n+increment));
        if(tmp==NULL){oops("Error: realloc()");}           
 
        n += increment;                   
        tab = tmp;
 
    }
 
current_size++;
} 
/*----loop ends----*/
 
 
/*if realloc'ed too much memory*/ 
if(n>current_size){ 
 
   /*realloc down to the right value*/                 
   printf("final realloc at %d\n",current_size); 
 
   tmp = (double*)realloc(tab,sizeof (double) * current_size);
   if(tmp==NULL){oops("reallocc() error");}
   tab = tmp;
 
}
 
for(i=0;i<current_size;i++){printf("tab[%d]=%1.1f\n",i,tab[i]);}
 
free(tab);
free(tmp);
 
return 0;
}/*end main*/

Dois-je faire un free(tmp) avant chaque tmp=realloc(tab,sizeof(double)*(n+increment)) ??

merci

06/07/2007, 22h19
Médinoc
Non, pas de free(tmp). Jamais.
Par contre, tu pourrais rajouter un free(tab) juste avant le oops() en cas d'échec de realloc().

Et aussi, je pense que dans la boucle i et current_size pourraient être la même variable. Mais surtout, tu devrais réallouer AVANT de modifier tab[i].

L'algorithme devrait être:
Code:

1 2 3 4 5 6 7 BOUCLE SI tableau trop petit pour la valeur actuelle de i ALORS on agrandit FIN SI enregistrer tableau[i] FIN BOUCLE
06/07/2007, 22h45
dmichel

Je suis d'accord mais comme je verifie avec n-1 dans

Code:

if(current_size>=(n-1)){}

il ne devrait pas y avoir de problemes, non ?
Quand i=n-1, on a atteint la derniere valeur de tab possible et j'ai aggrandit donc pour la prochaine valeur.
06/07/2007, 23h02
Médinoc
Mais tu agrandis quand même après un ajout et non avant.
Ce qui signifie:
- Que ton tableau DOIT être assez grand au début
- Que tu peux réallouer une fois de trop juste après avoir ajouté le dernier nombre.

merci pour tes conseils...
j'ai modifier le code et j'ai essayer de faire la meme chose avec une pointer double mais ca plante. Qu'est-ce que je ne fais pas correctement ??

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define oops(s)          { perror((s)); exit(1); }
 
int main()
{
 
double *tab;
double *tmp;
 
double **tab2;
double **tmp2;
 
int i,j;
int n = 10;
int increment = 5;
int current_size=0;
int isecret;
 
/*initial dynamic allocation*/
 
tab=malloc(sizeof(double)*n);
if(tab==NULL){free(tab);oops("Error: malloc()");} 
 
tab2 = malloc(sizeof(double*)*n);
if(tab2==NULL){free(tab2);oops("Error: malloc()");}
for(i=0;i<n;i++){
tab2[i] = malloc(sizeof(double)*3);
if(tab2[i]==NULL){free(tab2[i]);oops("Error: malloc()");}
}
 
/*----loop starts----*/
 
isecret  = rand() % 100 + 1;
isecret = 30;
for(i=0;i<isecret;i++){     
 
    printf("current_size=%d  n=%d\n",current_size,n);
 
    if(current_size>=n){ /*if initial allocation filled up*/
 
        printf("realloc at %d\n",n+increment);               
 
        tmp=realloc(tab,sizeof(double)*(n+increment));
        if(tmp==NULL){free(tab);oops("Error: realloc()");}           
 
        tmp2=realloc(tab2,sizeof(double*)*(n+increment));        
        if(tmp==NULL){free(tab);oops("Error: realloc()");}
        for(j=0;j<n;j++){
        tmp2[j] = realloc(tab2,sizeof(double)*3);
        if(tmp2[j]==NULL){free(tab2[j]);oops("Error: malloc()");}
        }
 
        n += increment;                   
        tab = tmp;
        tab2 = tmp2;
    }
 
 
    tab[i] = rand() % 10;
 
    tab2[i][0] = rand() % 20;
    tab2[i][1] = rand() % 200;
    tab2[i][2] = rand() % 200;
 
current_size++;
} 
/*----loop ends----*/
 
 
/*if realloc'ed too much memory*/ 
if(n>current_size){ 
 
   /*realloc down to the right value*/                 
   printf("final realloc at %d\n",current_size); 
 
   tmp = realloc(tab,sizeof (double) * current_size);
   if(tmp==NULL){free(tab);oops("reallocc() error");}
   tab = tmp;
 
   tmp2 = realloc(tab2,sizeof (double*) * current_size);
   if(tmp2==NULL){free(tab2);oops("reallocc() error");}
   for(j=0;j<3;j++){
   tmp2[j] = realloc(tab2,sizeof(double)*3);
   if(tmp2[j]==NULL){free(tab2[j]);oops("Error: malloc()");}
   }
   tab2 = tmp2;
 
}
 
for(i=0;i<current_size;i++){
printf("tab[%d]=%1.1f\n",i,tab[i]);
for(j=0;j<3;j++){printf("tab2[%d][%d]=%1.1f\n",i,j,tab2[i][j]);}
}
 
free(tab);
free(tmp);
 
free(tmp2);
for(j=0;j<3;j++){
free(tmp2[j]);
}
 
 
return 0;
}/*end main*/

07/07/2007, 10h36
Médinoc

Ça m'a l'air bien compliqué, ça.
Je ne peux pas trop t'aider sans savoir exactement ce que tu cherches à allouer dynamiquement : Des tableaux de trois doubles ?
Des structures ne seraient-elles pas plus appropriées dans ce cas ? (sachant qu'une structure peut elle-même contenir un tableau de trois doubles).

je suis d'accord qu'une structure sera sans doute plus appropriee...mais je veux aussi apprendre a faire les reallocs sur un tableau de 3 doubles...

Imaginons que je lise un fichier organise de la facon suivante

1.252530 0.265454 -5.312582
2.555555 -2.5424545 1.222222
...

J'aimerais avoir la fin:

tab[0][0]=1.252530 tab[0][1]=0.265454 tab[0][2]=-5.312582
tab[1][0]=2.555555 tab[1][1]=-2.5424545 tab[1][2]=1.222222
etc...

Je suis pas sur si les malloc() initials sonts corrects ou pas
Code:

1 2 3 4 5 6 7 tab2 = malloc(sizeof(double*)*n); if(tab2==NULL){free(tab2);oops("Error: malloc()");} for(i=0;i<n;i++){ tab2[i] = malloc(sizeof(double)*3); if(tab2[i]==NULL){free(tab2[i]);oops("Error: malloc()");} }
et encore moins pour les realloc() qui suivent:
Code:

1 2 3 4 5 6 7 8 tmp2=realloc(tab2,sizeof(double*)*(n+increment)); if(tmp==NULL){free(tab);oops("Error: realloc()");} for(j=0;j<n;j++){ tmp2[j] = realloc(tab2,sizeof(double)*3); if(tmp2[j]==NULL){free(tab2[j]);oops("Error: malloc()");} }

07/07/2007, 12h41
Médinoc
Le problème, c'est que là tu ne réalloues pas une matrice, mais un tableau de pointeurs de tableaux.

La première chose à savoir, c'est : Quand allouer les tableaux imbriqués ?
- Toi, tu sembles avoir choisi l'allocation immédiate: On agrandit le tableau de tableaux, on alloue les tableaux directement.
- Moi, je conseillerais plutôt une allocation à la demande: On agrandit le tableau, on initialise les nouveaux pointeurs à NULL, et on alloue un tableau de trois doubles pour chaque ligne.
PS: Fais des fonctions. Une fonction d'ajout, ou du moins une fonction qui s'assure que le tableau alloué a la bonne taille, etc.

Ok merci pour tes conseils. Maintenant pour faire la reallocation, je fais ca:
Code:

1 2 3 4 5 6 7 8 9 10 tmp2 = realloc(tab2,sizeof(double*)*(n+increment)); if(tmp2==NULL){free(tab2);oops("Error: realloc()");} for(i=n;i<n+increment;i++){ tmp2[i] = malloc(sizeof(double)*3); if(tmp2[i]==NULL){free(tmp2[i]);oops("Error: malloc()");} } tab2 = tmp2;
par-contre, si maintenant, je fais une reallocation quit reduit la taille du tableau de tableaux de 'n' a 'current_size', faut-il que je fasse un free sur les tableaux de chaque ligne en trop (de 'current_size' a 'n'), par example:
Code:

1 2 3 4 5 6 7 8 9 for(i=current_size;i<n;i++){ free(tab2[i]); } tmp2 = realloc(tab2,sizeof(double*)*current_size); if(tmp2==NULL){free(tab2);oops("reallocc() error");} tab2 = tmp2;
Ou est-ce que le realloc sur tab2 est suffisant ?

07/07/2007, 17h33
Médinoc

Non, le realloc() de tab2 n'est pas suffisant.
Mais comme je te l'ai dit, je pense qu'une allocation à-la-demande des tableaux de double serait un meilleur moyen...
09/07/2007, 18h54
dmichel

Merci pour tes conseils...
j'ai pas trop le temps de bosser sur ca en ce moment, mais des que j'peux, je serais surement de retour ici :-)