Quelle est la complexité temporelle de « append » dans Go ?

Ajouter la complexité en Go

Problème :

Quelle est la complexité de calcul de la boucle suivante en Go ?

var a []int
for i := 0 ; i < n ; i++ {
  a = append(a, i)
}

L'ajout fonctionne-t-il en temps linéaire ou en constante amortie heure ?

Réponse :

La spécification du langage de programmation Go indique que l'ajout effectue une réallocation si nécessaire :

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

Cependant, l'algorithme spécifique à augmenter la tranche cible lorsque cela est nécessaire dépend de la mise en œuvre. Pour le compilateur gc actuel, l'algorithme est amorti en temps constant.

Explication en temps constant amorti :

La capacité de tranche est augmentée de manière gourmande :

• Si l'ancienne capacité est supérieure au double de l'ancienne capacité, la nouvelle capacité est définie sur l'ancienne capacité.
• Sinon, si l'ancienne longueur est inférieure à 1024, la nouvelle capacité est définie pour doubler l'ancienne capacité.
• Sinon, la nouvelle capacité est augmentée d'un quart jusqu'à ce qu'elle soit à au moins la taille de l'ancienne capacité.

Cette approche garantit que le temps total passé à réaffecter est amorti en O(n), où n est la durée de la tranche résultante.

Considérations d'implémentation :

La spécification du langage Go permet différentes implémentations d'append. Par exemple, la mise en œuvre peut être généreuse (en allouant plus que le montant minimum nécessaire) ou parcimonieuse (en allouant le montant minimum nécessaire). Le compilateur Go gc utilise un généreux algorithme à temps constant amorti par tableau dynamique.

Résumé :

La complexité de l'ajout dans Go dépend de l'implémentation. Cependant, les implémentations courantes telles que le compilateur Go gc et gccgo utilisent des algorithmes à temps constant amorti.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!