Est-ce que Swift a une concaténation de chaîne quadratique lors de l'utilisation de var?

Question

In the Swift Language Reference, under String Mutability il dit:

Vous indiquez si une chaîne particulière peut être modifié (ou muté) en attribuant à une variable (dans ce cas, il peut être modifié), ou à une constante (auquel cas il ne peut pas être modifié)

on ne sait pas à moi si le « il » qui est mutable est la variable ou la valeur .

Par exemple, si je vous écris:

var s = "" 
for i in 0...100 { 
    s += "a" 
} 

est-il semblable à la création d'un NSMutableString et d'appeler appendString 100 fois (c.-à-coût linéaire)?

Ou est-ce semblable à la création d'une série d'instances NSString toujours plus grandes et en les combinant avec stringByAppendingString (à savoir le coût quadratique)?

Ou peut-être crée-t-il une sorte de structure de corde dans les coulisses, donc et sont-ils linéaires?

Answer 1

L'ajout d'une collection comme celle-ci (alors que String n'est pas en elle-même une collection, vous ajoutez essentiellement à sa vue characters avec ce code) est linéaire, et non quadratique. Une chaîne dans Swift a un tampon interne dont la taille est doublée chaque fois qu'elle se remplit, ce qui signifie que vous verrez de moins en moins de réaffectations à mesure que vous ajoutez plusieurs fois. La documentation décrit l'ajout de cette manière comme une opération O (1) «amortie»: la plupart du temps, l'ajout est O (1), mais occasionnellement, il faudra réallouer le stockage de la chaîne. Les tableaux, ensembles et dictionnaires ont le même comportement, bien que vous puissiez également réserver une capacité spécifique pour un tableau (en utilisant reserveCapacity(_:)) si vous savez que vous ajouterez plusieurs fois. Toutes ces collections utilisent "copy-on-write" pour garantir la sémantique des valeurs. Ici, x et y partagent un tampon:

let x = "a" 
let y = x 

Si vous muter x, il obtient une nouvelle copie unique du tampon:

x += "b" 
// x == "ab" 
// y == "a" 

Après cela, x a son propre tampon, si la suite les mutations ne nécessiteront pas de copie.

x += "c" // no copy unless buffer is full