Pourquoi la matrice de vecteurs est-elle doublée?

Question

Pourquoi l’implémentation classique de Vector (ArrayList pour les utilisateurs de Java) double-t-elle la taille de son tableau interne sur chaque extension au lieu de la multiplier ou de la quadrupler?

Answer 1

Lors du calcul du temps moyen d'insertion dans un vecteur, vous devez prendre en compte les insertions non en croissance et les insertions en croissance.

Appelez le nombre total d'opérations pour insérer les n éléments o total , et la moyenne o moyenne .

Si vous insérez des n éléments et que vous multipliez la valeur par A , le nombre de o total = n + & # 931; A ⁱ [0 < je < 1 + ln _A n] opérations. Dans le pire des cas, vous utilisez 1 / A de la mémoire allouée.

Intuitivement, A = 2 signifie au pire que vous avez o total = 2n , donc o moyenne est O (1), et dans le pire des cas, vous utilisez 50% de la mémoire allouée.

Pour un plus grand A , vous avez un o total inférieur, mais davantage de stockage inutilisé.

Pour un A plus petit, o total est plus grand, mais vous ne gaspillez pas autant de stockage. Tant qu’il se développe géométriquement, il reste toujours un temps d’insertion amorti de O (1), mais la constante augmentera.

Pour les facteurs de croissance 1,25 (en rouge), 1,5 (en cyan), 2 (en noir), 3 (en bleu) et 4 (en vert), ces graphiques montrent l’efficacité ponctuelle et en taille moyenne (rapport taille / espace alloué; plus c'est mieux) ) à gauche et efficacité temporelle (rapport insertions / opérations; plus c'est mieux) à droite pour insérer 400 000 articles. Une efficacité spatiale de 100% est atteinte pour tous les facteurs de croissance juste avant le redimensionnement; le cas de A = 2 montre un gain de temps compris entre 25% et 50% et un gain d'espace d'environ 50%, ce qui est bon dans la plupart des cas:

Pour les environnements d'exécution tels que Java, les tableaux sont remplis de zéros. Le nombre d'opérations à allouer est donc proportionnel à la taille du tableau. La prise en compte de ces résultats réduit la différence entre les estimations de l’efficacité temporelle:

Answer 2

Le fait de doubler exponentiellement la taille du tableau (ou de la chaîne) est un bon compromis entre avoir suffisamment de cellules dans le tableau et gaspiller trop de mémoire.

Disons que nous partons de 10 éléments:

1 - 10
2 - 20
3 - 40
4 - 80
5 - 160

Quand on triple la taille, on grandit trop vite

1 - 10
2 - 30
3 - 90
4 - 270
5 - 810

En pratique, vous pourriez pousser 10 ou 12 fois. Si vous tripliez, vous le feriez peut-être 7 ou 8 fois - le temps d'exécution pour la réaffectation est que ce nombre de fois est suffisamment petit pour vous inquiéter, mais vous risquez davantage de dépasser complètement la taille requise.

Answer 3

Si vous allouiez un bloc de mémoire de taille inhabituelle, il serait un trou de mémoire de taille inhabituelle lorsque ce bloc serait désalloué (soit parce que vous le redimensionnez, soit parce qu'il est redimensionné). maux de tête pour le gestionnaire de mémoire. Il est donc généralement préférable d’allouer de la mémoire par deux. Dans certains cas, le gestionnaire de mémoire sous-jacent ne vous donnera que des blocs de certaines tailles, et si vous demandez une taille étrange, il sera arrondi à la taille immédiatement supérieure. Donc, plutôt que de demander 470 unités, de récupérer 512 quand même, puis de redimensionner une fois que vous avez utilisé toutes les 470 que vous avez demandées, vous pouvez également demander 512 pour commencer.

Answer 4

Tout multiple est un compromis. Faites-le trop gros et vous perdez trop de mémoire. Faites-le trop petit et vous perdez beaucoup de temps pour les réaffectations et les copies. J'imagine que le doublement existe parce que cela fonctionne et qu'il est très facile à mettre en œuvre. J'ai également vu une bibliothèque de type STL propriétaire qui utilise 1,5 comme multiplicateur pour la même chose - je suppose que ses développeurs ont envisagé de doubler le gaspillage de mémoire.

Answer 5

Si vous vous interrogez sur l'implémentation spécifique à Java de Vecteur et ArrayList , alors ce n'est pas nécessairement doublé à chaque expansion.

De la Javadoc pour le vecteur:

  

Chaque vecteur essaie d'optimiser la gestion du stockage en conservant un capacity et un capacityIncrement. La capacité est toujours au moins aussi grande que la taille du vecteur; il est généralement plus volumineux car, au fur et à mesure que des composants sont ajoutés au vecteur, sa capacité de stockage augmente en morceaux de la taille ensureCapacity(int minCapacity). Une application peut augmenter la capacité d'un vecteur avant d'insérer un grand nombre de composants. cela réduit la quantité de réallocation incrémentielle.

L’un des constructeurs de Vector vous permet de spécifier la taille initiale et l’incrément de capacité du vecteur. La classe Vector fournit également les setSize(int newSize) et ArrayList ajustements manuels de la taille minimale du vecteur et le redimensionnement individuel.

La classe ArrayList est très similaire:

  

Chaque <=> instance a une capacité. La capacité est la taille du tableau utilisé pour stocker les éléments dans la liste. Il est toujours au moins aussi grand que la taille de la liste. Lorsque des éléments sont ajoutés à une liste de tableaux, sa capacité augmente automatiquement. Les détails de la politique de croissance ne sont pas spécifiés au-delà du fait que l'ajout d'un élément a un coût en temps amorti constant.

     

Une application peut augmenter la capacité d'une instance <=> avant d'ajouter un grand nombre d'éléments à l'aide de l'opération EnsureCapacity. Cela peut réduire le montant de la réallocation incrémentielle.

Si vous vous interrogez sur la mise en œuvre générale d’un vecteur, vous devez choisir le choix de l’augmentation de la taille et de la valeur du compromis. Généralement, les vecteurs sont supportés par des tableaux. Les tableaux ont une taille fixe. Redimensionner un vecteur parce qu'il est plein signifie que vous devez copier tous les éléments d'un tableau dans un nouveau tableau plus grand. Si vous agrandissez trop votre nouveau tableau, vous avez alloué de la mémoire que vous n'utiliserez jamais. S'il est trop petit, la copie des éléments de l'ancien tableau dans le nouveau tableau plus grand risque de prendre trop de temps - une opération que vous ne voulez pas exécuter très souvent.

Answer 6

Personnellement, je pense que c’est un choix arbitraire. Nous pourrions utiliser la base e au lieu de la base 2 (au lieu de doubler la taille multiple de (1 + e).)

Si vous allez ajouter de grandes quantités de variables au vecteur, il serait avantageux d’avoir une base élevée (pour réduire le temps de copie que vous ferez.) De l’autre côté si vous devez stocker des données. seulement quelques membres sur avg, alors une base faible ira bien et réduira les frais généraux, accélérant ainsi les choses.

La base 2 est un compromis.

Answer 7

Il n'y a aucune raison de performance pour doubler vs tripler ou quadrupler, car ils ont tous les mêmes grands profils de performance. Cependant, en termes absolus, le fait de doubler aura tendance à être plus efficace dans un scénario normal.