Bonjour,
 
j'ai un fichier contenant des entiers (nombre non connu à l'avance), par exemple
0
1
2
...
 
Je voudrais stocker ces entiers dans un tableau dynamique, mais je ne sais pas trop quelle méthode adopter pour remplir le tableau; quel est le mieux (en terme de performances surtout) ?
 
1) Parcourir le fichier une première fois pour connaitre le nombre d' entiers et ainsi faire une unique allocation puis le reparcourir pour remplir le tableau ?
2) Parcourir le fichier une seule fois mais faire autant de realloc qu'il y a d' entiers ?
3) Une méthode "hybride", genre faire un malloc (n...), où n serait un nombre "typique" de entiers, puis adapter le tableau au cas où on aurait plus de n entiers ?
 
Merci d'avance pour vos suggestions

man realloc
 
ou utiliser une bibliothèque genre glib g_array

je pencherais pour une méthode "hybride" où tu alloues par paquets. Dans ce genre là, il y différents types de méthodes : celles où tu alloues par paquets de taille fixe (genre 1000 éléments). Sinon, il y a des trucs plus dynamiques, comme par exemple la stratégie d'allocation des vectors du C++ : tu doubles la taille à chaque réallocation.

Apparemment, il semble qu'il faille multiplier par le nombre d'or : voir http://www.bourguet.org/realloc.pdf

merci, je ne connaissais pas ça. Je vais me pencher un peu là dessus : ça a l'air intéressant.

 
Taz avait déjà dit un truc analogue dans un de ses topics. Il avait privilégié la méthode "taille n" = "taille n - 2 + taille n - 1" ce qui amène évidemment au nombre d'or...

Le tout c'était de multiplier n avec un facteur k de manière à ce que n[i+2] ~ n[i+1] + n[i]. En effet dans le cas d'une réallocation complète et dans si l'allocateur mémoire a des propriétés de type 'best fit', ce facteur de croissance peut permettre de réussir l'allocation i+2 en réutilisant l'espace des deux précédentes allocations i+1 et i. C'est choisi par pas mal d'implémentations mais aussi parce l'accroissement est moins important qu'avec k = 2 tout en restant exponentiel.

On cherche donc un k tel que
¤ n[i+1] = k * n[i]
¤ n[i+2] = n[i+1] + n[i]

<=> k² * n[i] = k * n[i] + n[i]
<=> k² = k + 1
on cherche k réel strictement positif
<=> k = (1 + sqrt(5)) / 2
i.e. k ~ 1,62

Et ne pas oublier qu'on peut faire une approximation en calcul entier en faisant '16 * n / 10' par exemple.