Ich weiß, dass .append gelegentlich die Kapazität eines Arrays erhöht und eine neue Kopie des Arrays bilden, aber wird .removeLast dies jemals umkehren und die Kapazität eines Arrays durch Kopieren in ein neues kleineres Array reduzieren?Reduziert `removeLast` jemals die Kapazität eines Arrays in swift?
Nein (oder zumindest, wenn es ja ist, ist es ein Fehler (*)). Das würde sein Komplexitätsversprechen verletzen.
Wenn Sie die Komplexität Versprechen für append lesen, heißt es:
Komplexität: Amortisierte O (1) über viele Ergänzungen. Wenn das Array eine überbrückte NSArray-Instanz als Speicher verwendet, ist die Effizienz nicht angegeben.
„Amortisieren O (1) über viele Hinzufügungen“ bedeutet, dass für jede gegebene Operation nicht O sein kann (1), aber die Grenze wie die Anzahl der Elemente geht gegen unendlich ist O (1), weil größere und es werden größere Vorabzuweisungen vorgenommen, so dass Umschichtungen immer seltener werden.
nun die Komplexität Versprechen für removeLast() lesen:
Komplexität: O (1)
Es gibt keinen Ort für eine Umverteilung in dort zu verstecken (oder zumindest könnte es nicht umgesetzt werden "durch Kopieren in ein neues kleineres Array").
(*) Es gibt eine schwierige Ausnahme. Jede Mutation in einem Array unterliegt einer möglichen Kopie beim Schreiben. Das bedeutet, dass jede Mutation, egal was es verspricht, O (n) wird, wenn sie den Speicher mit einem anderen Array teilt. Dies macht das Nachdenken über Swift sehr schwierig, ist aber nicht spezifisch für diese Frage.
Wie Rob Napiers Antwort darauf hinweist, sollte removeFirst die Kapazität des Arrays nicht reduzieren. Hinzufügen von einigen Details, removeLast nicht auch, und removeAllfunktioniert standardmäßig, obwohl es einen Parameter keepingCapacity erfordert, um dieses Verhalten zu ändern.
var arr = [Int]()
print(arr.capacity) // 0
arr.append(1)
print(arr.capacity) // 2
arr.append(2)
print(arr.capacity) // 2
arr.removeFirst()
print(arr.capacity) // 2
arr.removeLast()
print(arr.capacity) // 2 (though the array is now empty)
arr.removeAll(keepingCapacity: true)
print(arr.capacity) // 2
arr.removeAll()
print(arr.capacity) // 0