realloc par blocs

**dmichel** · 05/07/2007, 22h14

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Médinoc** · 05/07/2007, 22h28

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.

**dmichel** · 05/07/2007, 22h36

qu'est que tu veux dire par casts ?

**Freed0** · 05/07/2007, 22h42

Le cast est une conversion de type

Dans ton cas ce sont par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

qui peut être simplifié en :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Médinoc** · 05/07/2007, 22h42

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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++.

**dmichel** · 05/07/2007, 23h00

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

**dmichel** · 06/07/2007, 21h29

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Médinoc** · 06/07/2007, 22h19

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**dmichel** · 06/07/2007, 22h45

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**Médinoc** · 06/07/2007, 23h02

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.

**dmichel** · 07/07/2007, 01h31

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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*/

**Médinoc** · 07/07/2007, 10h36

Ç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).

**dmichel** · 07/07/2007, 12h33

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Médinoc** · 07/07/2007, 12h41

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.

**dmichel** · 07/07/2007, 16h30

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

**Médinoc** · 07/07/2007, 17h33

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...

**dmichel** · 09/07/2007, 18h54

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 :-)

realloc par blocs

C

Discussions similaires

Partager

Partager