Czy Swift ma kwadratowe połączenie ciągów podczas używania var?

Question

In the Swift Language Reference, under String Mutability mówi:

wskazać, czy dany ciąg może być modyfikowana (lub zmutowane), przypisując go do zmiennej (w tym przypadku może być modyfikowana) lub stałym (w którym to przypadku nie można modyfikować)

jest dla mnie jasne, czy „to”, które jest zmienny jest zmienna lub wartość.

Na przykład, jeśli piszę:

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

Czy jest zbliżona do tworzenia NSMutableString i nazywając appendString 100 razy (czyli kosztów liniowy)?

Czy jest to podobne do tworzenia serii coraz większych instancji NSString i łączenia ich z stringByAppendingString (tj. Kosztem kwadratowym)?

A może tworzy się za kulisami coś w rodzaju konstrukcji linowej, więc jest niezmienna i liniowa w agregacie?

Answer 1

Dołączanie do kolekcji takiej jak ta (podczas gdy String nie jest zbiorem, zasadniczo dołącza się do jej widoku characters) jest liniowe, a nie kwadratowe. Łańcuch w Swift ma wewnętrzny bufor, którego rozmiar jest podwajany za każdym razem, gdy się zapełnia, co oznacza, że ​​zobaczysz mniej ponownych przydziałów, gdy będziesz wielokrotnie dodawać. Dokumentacja opisuje dołączanie w ten sposób jako "zamortyzowaną" operację O (1): większość czasu dołączania to O (1), ale czasami trzeba będzie ponownie przydzielić pamięć ciągu.

Tablice, zestawy i słowniki działają tak samo, ale można również zarezerwować określoną pojemność tablicy (przy użyciu reserveCapacity(_:)), jeśli wiesz, że będziesz dołączać wiele razy.

---

Wszystkie te kolekcje używają "kopiuj-napisz", aby zagwarantować semantykę wartości. Tutaj x i y dzielą bufor:

let x = "a" 
let y = x 

Jeśli mutować x, to dostaje nowy, unikalny egzemplarz bufora:

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

potem x posiada własny bufor, więc późniejsza mutacje nie wymagają kopii.

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