Узнайте, как работают массивы swift, и как их можно оптимизировать — работа с ContiguousArray, их сравнение и т. д.
_ContiguousArrayStorage— выделение памяти для хранения элементов, обеспечение быстрого доступа по индексу._ArrayBridgeStorage— абстракция, позволяющая использовать как собственное хранилище, так и NSArray._ArrayBuffer<T>- реализация копирования при записи.Array<T>- публичный интерфейс.
Увеличение размера массива
Каждый массив резервирует определенный объем памяти для хранения своего содержимого. Когда вы добавляете элементы в массив, и этот массив начинает превышать зарезервированную емкость, массив выделяет большой объем памяти и копирует свои элементы в новое хранилище, где новое хранилище во много раз превышает размеры старого хранилища.
Эта стратегия экспоненциального роста означает, что добавление элемента происходит за постоянное время, что усредняет производительность многих операций добавления. Операции добавления, запускающие перераспределение, снижают производительность, но они выполняются все реже и реже по мере увеличения массива.
Пример. Создайте массив из 10 элементов.
Swift выделит достаточно места для этого массива, чтобы хранить только эти 10 элементов, поэтому как array.capacity, так и array.count будет равно 10.
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array.capacity) // 10
print(array.count) // 10Добавим 11 и 12 элементов. Массив не имеет для этого возможностей, поэтому ему нужно освободить место — он найдет память для хранения большего количества элементов, скопирует туда массив, а затем добавит 11 и 12 элементов. Время выполнения этих вставок сложное — O(n), где n — количество элементов в массиве.
array.append(11)
array.append(12)
print(array.capacity) // 20
print(array.count) // 12Таким образом, когда вы добавляете 11 и 12 элементов в массив емкостью 10, swift создает массив размером 20. И когда мы превысим этот размер, следующая емкость будет 40, потом 80, потом 160, и так на.
Если вы примерно знаете, сколько элементов вы хотите сохранить, используйте reserveCapacity(_:). Это позволит вам избежать промежуточных перераспределений.
Используйте свойства capacity и count, чтобы определить, сколько элементов массив может хранить без выделения больших ресурсов.
var stringArray = Array<String>()
stringArray.reserveCapacity(128) Если тип вашего массива Element является классом или протоколом @objc и вам не нужно соединять массив с NSArray или передавать массив API-интерфейсам Objective-C, использование ContiguousArray может быть более эффективным и иметь более предсказуемую производительность, чем Array. Если тип массива Element является структурой или перечислением, Array и ContiguousArray должны иметь одинаковую эффективность.
Тип ContiguousArray — это специализированный массив, который всегда хранит свои элементы в непрерывной области памяти. Это контрастирует с Array, который может хранить свои элементы либо в непрерывной области памяти, либо в NSArrayэкземпляре, если его Element тип является классом или @objc протоколом.
Array будет храниться непрерывно:
- Массивы, созданные в Swift, всегда будут храниться непрерывно;
- Массивы структур и перечислений всегда будут храниться непрерывно;
- Массивы на платформах без среды выполнения Objective-C (т. е. на платформах, отличных от Darwin) всегда хранятся непрерывно;
- Единственный случай, когда массив не будет храниться непрерывно, это если он относится к классам и был соединен мостом с
NSArray - Даже в этом случае во многих случаях
NSArrayбудет храниться непрерывно и может представлять собой указатель бесплатно или по амортизированной стоимости.
Сравнение Array и ContiguousArray
import Foundation
protocol Possibles {
init(repeating: Bool, count: Int)
subscript(index: Int) -> Bool { get set }
var count: Int { get }
}
extension Array: Possibles where Element == Bool {}
extension ContiguousArray: Possibles where Element == Bool {}
func lazySieveOfEratosthenes<Storage: Possibles>(makeStorage: () -> Storage) -> [Int] {
var possibles = makeStorage()
let limit = possibles.count - 1
return (2 ... limit).lazy.filter { i in // Lazy, so that `possibles` is updated before it is used.
possibles[i]
}.map { i in
stride(from: i * i, through: limit, by: i).lazy.forEach { j in
possibles[j] = false
}
return i
}.reduce(into: [Int]()) { (result, next) in
result.append(next)
}
}
func forSieveOfEratosthenes<Storage: Possibles>(makeStorage: () -> Storage) -> [Int] {
var possibles = makeStorage()
let limit = possibles.count - 1
var result = [Int]()
for i in 2 ... limit where possibles[i] {
var j = i * i
while j <= limit {
possibles[j] = false
j += i
}
result.append(i)
}
return result
}
func test(_ name: String, _ storageType: String, _ function: (Int) -> [Int]) {
let start = Date()
let result = function(100_000)
let end = Date()
print("\(name) \(storageType) biggest: \(result.last ?? 0) time: \(end.timeIntervalSince(start))")
}
test("for ", "Array ") { limit in
forSieveOfEratosthenes {
Array(repeating: true, count: limit + 1)
}
}
test("for ", "ContiguousArray") { limit in
forSieveOfEratosthenes {
ContiguousArray(repeating: true, count: limit + 1)
}
}
test("lazy ", "Array ") { limit in
lazySieveOfEratosthenes {
Array(repeating: true, count: limit + 1)
}
}
test("lazy ", "ContiguousArray") { limit in
lazySieveOfEratosthenes {
ContiguousArray(repeating: true, count: limit + 1)
}
}Результат:
for Array biggest: 99991 time: 41.016937017440796
for ContiguousArray biggest: 99991 time: 40.648478984832764
lazy Array biggest: 99991 time: 3.3549970388412476
lazy ContiguousArray biggest: 99991 time: 3.5851539373397827Другой:
for Array biggest: 99991 time: 41.801795959472656
for ContiguousArray biggest: 99991 time: 42.37710893154144
lazy Array biggest: 99991 time: 3.438219904899597
lazy ContiguousArray biggest: 99991 time: 3.4085270166397095Запуск производился на ноутбуке со следующей конфигурацией:
- macOS Монтерей (версия 12.3)
- Процессор 8-ядерный Intel Core i9 с тактовой частотой 2,3 ГГц
- Память 16 ГБ DDR4
- Версия Xcode 13.3.1 (13E500a), игровая площадка
Пример кода взят здесь, советую посмотреть всю ветку. Как видите, Array не всегда медленнее, чем ContiguousArray..
Массив с классами
Если элементы в Array являются экземплярами класса, семантика будет одинаковой, хотя поначалу они могут выглядеть по-разному. В этом случае значения, хранящиеся в массиве, являются ссылками на объекты вне массива. Когда вы меняете ссылку на объект в одном массиве, только этот массив имеет ссылку на новый объект. Тем не менее, если два массива содержат ссылки на один и тот же объект, вы можете наблюдать изменения в свойствах этого объекта из обоих массивов.
class MyClass {
var name = "Name"
}
var firstArray = [MyClass(), MyClass()]
var secondArray = firstArray
firstArray[0].name = "Another Name"
print(firstArray[0].name) // "Another name"
print(secondArray[0].name) // "Another name- Замены, добавления и удаления имеют область действия только для массива, к которому применяются действия:
firstArray[0] = MyClass()
print(firstArray[0].name) // "Name"
print(secondArray[0].name) // "Another nameСложность алгоритма Big-O с операциями:
- O (1) — Постоянное время (самое быстрое). Доступ к элементу массива по его индексу:
let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
array[3]- O(n log n) — логарифмическое время (немного хуже, чем постоянное время). Сортировка по возрастанию, стандартная функция:
var people = ["Sandra", "Mike", "James", "Donald"]
people.sort()- O(n) — линейное время (чуть хуже, чем логарифмическая сложность). Подсчет суммы элементов с помощью стандартной функции forEach:
let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
var sumOfNumbers = 0
numbers.forEach {
sumOfNumbers += $0
}
print(sumOfNumbers) // 55- O(n ²) — квадратичное время (немного хуже, чем O (n log n). Обход двумерного массива:
var twoDimensionalArray = [["first one", "second one"], ["first two", "second two"], ["first third", "second third"]]
for i in 0..<twoDimensionalArray.count {
for n in 0..<twoDimensionalArray[i].count {
print(twoDimensionalArray[i][n])
}
}Заключение
Массивы в Swift — хороший тип данных для организации упорядоченной коллекции, где вы можете хранить различные элементы, но помните о семантике со значениями и ссылочными типами. Вы можете выполнять самые разные операции (добавление, удаление и т. д.), а также использовать не только Array, но и ContiguousArray, NSArray, ArraySliceи и т. д.
Спасибо за прочтение. Не забудьте подписаться на меня на Medium. Давайте подключимся и в Linkedin.
Массив — это структура, что означает, что это тип значения в Swift. Вы используете массивы для организации данных вашего приложения, тип массива для хранения элементов одного типа и тип элемента массива.
