Le calculateur de croissance d’un tableau dynamique donne le nombre de redimensionnements, les éléments copiés, les copies amorties par ajout et la capacité inutilisée d’un tableau qui grandit d’un facteur fixe à mesure qu’on y ajoute des éléments.
Comment se fait le calcul
- Choisissez le facteur de croissance et saisissez la capacité initiale.
- Saisissez le nombre d’éléments ajoutés.
- Le calculateur donne les redimensionnements, la capacité finale, les copies, les copies par ajout, la capacité inutilisée et la mémoire de pointe.
Exemple
Ajouter 1 000 000 d’éléments à un tableau qui démarre à 16 cases et double demande 16 redimensionnements, jusqu’à une capacité finale de 1 048 576. Les copies totalisent 1 048 560, soit 1,049 par ajout, et 4,6 % de la capacité reste inutilisé à la fin. Lors du dernier redimensionnement, l’ancien et le nouveau tampon coexistent, donc la mémoire de pointe vaut 1,57 fois les données.
Pourquoi c’est utile
Le calculateur aide les étudiants en programmation et les développeurs à comparer les stratégies de croissance des vecteurs, des listes et des constructeurs de chaînes, et à décider quand réserver la capacité en vaut la peine.
À savoir
Les chiffres sont une borne supérieure, car la copie d’un redimensionnement ne déplace que les éléments réellement stockés, soit toute l’ancienne capacité quand un redimensionnement a lieu. Le coût d’un ajout isolé n’est pas constant : celui qui déclenche un redimensionnement coûte autant que tout le tableau, ce qui compte pour le code sensible à la latence. Pour les systèmes temps réel, un tampon de capacité fixe ou un redimensionnement incrémental évite ces pics. Les allocateurs peuvent aussi arrondir les tailles à une classe supérieure, et un grand realloc peut parfois s’étendre sur place, sans aucune copie. La même analyse vaut pour les tables de hachage qui doublent leur tableau de seaux quand le facteur de charge est dépassé, et pour la croissance des tampons de chaînes lors des concaténations.
Outils liés
Le calculateur de recherche dichotomique couvre les recherches dans les tableaux triés, celui de collisions de hachage décrit les tables de hachage, celui de mémoire des LLM dimensionne de gros tampons et celui de taille de la table des pages montre l’organisation de la mémoire.