Aller au contenu
Omnikalc

Calculateur de croissance d’un tableau dynamique

Saisissez le facteur de croissance, la capacité initiale et le nombre d’éléments ajoutés pour obtenir le nombre de redimensionnements, les copies totales, le coût amorti par ajout et la capacité inutilisée.

Mis à jour le
Vos paramètres
cases

Valeur hors limites

Valeur hors limites

Résultats

Nombre de redimensionnements

16

Capacité finale
1 048 576
Éléments copiés au total (au plus)
1 048 560
Copies par ajout (amorti)
1,049
Capacité inutilisée à la fin
4,6 %
Mémoire de pointe lors du dernier redimensionnement (× données)
1,57 ×
Pic de mémoire modéré

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.

Questions fréquentes

Pourquoi l’ajout est-il à temps constant en moyenne ?

Chaque redimensionnement copie tout le tableau, mais ils deviennent de plus en plus rares car la capacité croît de façon géométrique. Les copies forment une série géométrique c0 × (g^r − 1) / (g − 1), proportionnelle à la taille finale, donc le coût par ajout reste constant, environ 1 / (g − 1) copies.

Quel facteur de croissance est le meilleur ?

Il y a un compromis. Un grand facteur comme 2 donne moins de copies, environ une par ajout, mais jusqu’à la moitié de la capacité peut rester inutilisée. Un petit facteur comme 1,5 copie environ deux fois par ajout et gaspille moins. Un facteur inférieur à 2 permet aussi de réutiliser les blocs libérés pour les tampons suivants, ce qui explique que certaines bibliothèques choisissent 1,5.

Comment éviter les redimensionnements ?

Si vous connaissez la taille finale à l’avance, réservez-la dès le départ. Le tableau est alloué une seule fois, sans copie et sans capacité gaspillée au-delà de ce que vous avez demandé. La plupart des langages offrent cela avec un appel du type reserve, with-capacity ou ensureCapacity.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.