1. Поговорим о массивах

Изучение данного блока предполагает предварительное знание синтаксиса языка Swift. Для успешного освоения этого материала, необходимо иметь базовое понимание синтаксиса языка Swift. Это включает в себя знание основных структур данных, операторов, циклов, функций, абстракций и других ключевых элементов языка. Без этих фундаментальных знаний будет сложно понять более сложные концепции и примеры, которые будут рассматриваться в данном блоке.

Массивы являются одним из наиболее часто используемых типов данных в Swift. Они предоставляют упорядоченную коллекцию элементов одного типа и обладают богатым набором методов и функций для работы с ними. В этой статье мы подробно рассмотрим массивы в Swift, их основные методы, алгоритмическую сложность операций.

Введение в массивы¶

В Swift массивы представлены типом Array, который является обобщенным и может хранить элементы любого типа, соответствующего определенному условию (например, Array<Int>, Array<String> или просто [Int], [String]). Массивы в Swift являются коллекциями, соответствующими протоколу Collection, что предоставляет им множество функциональностей.

Создание массивов¶

// Пустой массив целых чисел
var numbers = [Int]()

// Массив строк с начальными значениями
let fruits = ["Яблоко", "Банан", "Апельсин"]

// Использование синтаксиса обобщений
var doubles: Array<Double> = [1.0, 2.0, 3.0]

Основные методы и операции с массивами¶

Добавление элементов¶

Добавление одного элемента в конец массива:

numbers.append(5)

Добавление элементов из другой коллекции:

numbers.append(contentsOf: [6, 7, 8])

Добавление элемента по указанному индексу:

numbers.insert(4, at: 0)

Удаление элементов¶

Удаление элементов по указанному индексу:

let removedNumber = numbers.remove(at: 0)

Удаление последнего элемента:

numbers.removeLast()

Удаление всех элементов массива:

numbers.removeAll()

Доступ к элементам¶

Индексирование:

let firstFruit = fruits[0]

Получение первого или последнего элемента:

if let firstNumber = numbers.first {
    print("Первый элемент: \(firstNumber)")
}

if let lastNumber = numbers.last {
    print("Последний элемент: \(lastNumber)")
}

Изменение элементов¶

Прямое присваивание по индексу:

numbers[0] = 10

Замена диапазона элементов:

numbers.replaceSubrange(0...1, with: [0, 1])

Функциональные методы¶

Функциональные методы массивов в Swift позволяют применять функциональный подход к обработке коллекций данных. Эти методы позволяют выполнять операции над массивами, не изменяя исходный массив, и часто могут быть объединены для создания цепочек преобразований.

Давайте подробно рассмотрим наиболее важные функциональные методы и приведем примеры их использования.

map(_:)¶

Метод map(_:) применяет заданное преобразование к каждому элементу массива и возвращает новый массив с преобразованными значениями.

func map<T>(_ transform: (Element) throws -> T) rethrows -> [T]

Пример использования:

let numbers = [1, 2, 3, 4, 5]
let squares = numbers.map { $0 * $0 }
print(squares) // [1, 4, 9, 16, 25]

В данном примере каждому элементу массива numbers применяется замыкание { $0 * $0 }, которое возводит число в квадрат.

compactMap(_:)¶

Метод compactMap(_:) также применяет преобразование к каждому элементу, но возвращает массив без nil значений. Это полезно, когда преобразование может вернуть опциональное значение.

func compactMap<ElementOfResult>(_ transform: (Element) throws -> ElementOfResult?) rethrows -> [ElementOfResult]

Пример использования:

let strings = ["1", "2", "three", "4", "five"]
let numbers = strings.compactMap { Int($0) }
print(numbers) // [1, 2, 4]

В этом примере пытаемся преобразовать каждый элемент строки в целое число. Если преобразование не удается (например, для “three”), результат будет nil, и такие элементы будут исключены из итогового массива.

flatMap(_:)¶

В Swift 4.1 и ранее flatMap(_:) применялся для “выравнивания” массивов массивов. Начиная с Swift 4.1, для этой цели рекомендуется использовать joined().

func flatMap<SegmentOfResult>(_ transform: (Element) throws -> SegmentOfResult) rethrows -> [SegmentOfResult.Element] where SegmentOfResult : Sequence

Пример использования:

let nestedArray = [[1, 2, 3], [4, 5, 6]]
let flatArray = nestedArray.flatMap { $0 }
print(flatArray) // [1, 2, 3, 4, 5, 6]

flatMap здесь преобразует массив массивов в одномерный массив, объединяя все внутренние массивы.

filter(_:)¶

Метод filter(_:) возвращает массив элементов, удовлетворяющих заданному условию.

func filter(_ isIncluded: (Element) throws -> Bool) rethrows -> [Element]

Пример использования:

let numbers = [1, 2, 3, 4, 5, 6]
let evenNumbers = numbers.filter { $0 % 2 == 0 }
print(evenNumbers) // [2, 4, 6]

Здесь выбираются только четные числа из исходного массива.

reduce(::)¶

Метод reduce(_:_:) сводит массив к одному значению, используя начальное значение и функцию-аккумулятор.

func reduce<Result>(_ initialResult: Result, _ nextPartialResult: (Result, Element) throws -> Result) rethrows -> Result

Пример использования:

let numbers = [1, 2, 3, 4, 5]
let sum = numbers.reduce(0) { $0 + $1 }
print(sum) // 15

В этом примере мы суммируем все элементы массива, начиная с начального значения 0.

reduce(into:_:)¶

Метод reduce(into:_:) похож на reduce, но более эффективен при работе с изменяемыми типами.

func reduce<into Result>(_ initialResult: Result, _ updateAccumulatingResult: (inout Result, Element) throws -> ()) rethrows -> Result

Пример использования:

let words = ["apple", "banana", "cherry"]
let wordLengths = words.reduce(into: [:]) { counts, word in
    counts[word] = word.count
}
print(wordLengths) // ["apple": 5, "banana": 6, "cherry": 6]

Здесь мы создаем словарь, где ключ — слово, а значение — его длина.

forEach(_:)¶

Метод forEach(_:) выполняет заданное действие для каждого элемента массива.

func forEach(_ body: (Element) throws -> Void) rethrows

Пример использования:

let numbers = [1, 2, 3]
numbers.forEach { print($0) }
// Вывод:
// 1
// 2
// 3

Метод forEach похож на цикл for-in, но не позволяет прерывать выполнение (например, с помощью break).

contains(_:) и contains(where:)¶

Методы для проверки наличия элемента или соответствия условия.

func contains(_ element: Element) -> Bool
func contains(where predicate: (Element) throws -> Bool) rethrows -> Bool

Пример использования:

let numbers = [1, 2, 3, 4, 5]
let hasThree = numbers.contains(3) // true
let hasEvenNumber = numbers.contains { $0 % 2 == 0 } // true

allSatisfy(_:)¶

Проверяет, удовлетворяют ли все элементы заданному условию.

func allSatisfy(_ predicate: (Element) throws -> Bool) rethrows -> Bool

Пример использования:

let numbers = [2, 4, 6]
let allEven = numbers.allSatisfy { $0 % 2 == 0 } // true

first(where:) и firstIndex(where:)¶

Находит первый элемент или индекс, удовлетворяющий условию.

func first(where predicate: (Element) throws -> Bool) rethrows -> Element?
func firstIndex(where predicate: (Element) throws -> Bool) rethrows -> Int?

Пример использования:

let numbers = [1, 3, 5, 6, 7]
if let firstEven = numbers.first(where: { $0 % 2 == 0 }) {
    print(firstEven) // 6
}

**dropFirst(:) и dropLast(:)**¶

Возвращает массив без первых или последних n элементов.

func dropFirst(_ k: Int = 1) -> SubSequence
func dropLast(_ k: Int = 1) -> SubSequence

Пример использования:

let numbers = [1, 2, 3, 4, 5]
let withoutFirstTwo = numbers.dropFirst(2) // [3, 4, 5]
let withoutLastTwo = numbers.dropLast(2) // [1, 2, 3]

**prefix(:) и suffix(:)**¶

Возвращает первые или последние n элементов.

func prefix(_ maxLength: Int) -> SubSequence
func suffix(_ maxLength: Int) -> SubSequence

Пример использования:

let numbers = [1, 2, 3, 4, 5]
let firstThree = numbers.prefix(3) // [1, 2, 3]
let lastTwo = numbers.suffix(2) // [4, 5]

enumerated()¶

Возвращает последовательность пар (индекс, элемент).

func enumerated() -> EnumeratedSequence<Array<Element>>

Пример использования:

let fruits = ["Apple", "Banana", "Cherry"]
for (index, fruit) in fruits.enumerated() {
    print("\(index): \(fruit)")
}
// Вывод:
// 0: Apple
// 1: Banana
// 2: Cherry

zip(_:)¶

Объединяет два массива в последовательность пар.

func zip<Sequence1, Sequence2>(
    _ sequence1: Sequence1,
    _ sequence2: Sequence2
) -> Zip2Sequence<Sequence1, Sequence2> where Sequence1 : Sequence, Sequence2 : Sequence

Пример использования:

let letters = ["A", "B", "C"]
let numbers = [1, 2, 3]
let zipped = zip(letters, numbers)
for (letter, number) in zipped {
    print("\(letter): \(number)")
}
// Вывод:
// A: 1
// B: 2
// C: 3

lazy¶

Позволяет отложить выполнение цепочки операций до момента, когда результат действительно нужен.

Пример использования:

let numbers = 1...1000
let result = numbers.lazy
    .map { $0 * 2 }
    .filter { $0 % 3 == 0 }
    .prefix(5)
print(Array(result)) // [6, 12, 18, 24, 30]

С использованием lazy операции map и filter выполняются только до тех пор, пока не будет получено первые 5 элементов.

partition(by:)¶

Разделяет массив на две части в зависимости от условия.

mutating func partition(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Int

Пример использования:

var numbers = [3, 1, 4, 1, 5, 9, 2]
let pivotIndex = numbers.partition(by: { $0 > 3 })
let lessThanOrEqualThree = numbers[..<pivotIndex] // [3, 1, 1, 2]
let greaterThanThree = numbers[pivotIndex...] // [4, 5, 9]

Метод partition(by:) переставляет элементы массива так, чтобы элементы, удовлетворяющие условию, были в конце массива.

sorted(by:)¶

Возвращает отсортированный массив на основе заданного критерия.

func sorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element]

Пример использования:

let names = ["Charlie", "Alice", "Bob"]
let sortedNames = names.sorted(by: <)
print(sortedNames) // ["Alice", "Bob", "Charlie"]

reversed()¶

Возвращает массив в обратном порядке.

func reversed() -> ReversedCollection<Array<Element>>

Пример использования:

let numbers = [1, 2, 3, 4, 5]
let reversedNumbers = numbers.reversed()
print(Array(reversedNumbers)) // [5, 4, 3, 2, 1]

firstIndex(of:)¶

Находит индекс первого вхождения заданного элемента.

func firstIndex(of element: Element) -> Int?

Пример использования:

let letters = ["a", "b", "c", "a", "b", "c"]
if let index = letters.firstIndex(of: "b") {
    print(index) // 1
}

drop(while:) и prefix(while:)¶

Позволяют пропустить или выбрать элементы, пока условие выполняется.

func drop(while predicate: (Element) throws -> Bool) rethrows -> SubSequence
func prefix(while predicate: (Element) throws -> Bool) rethrows -> SubSequence

Пример использования:

let numbers = [1, 2, 3, 4, 5]
let dropped = numbers.drop(while: { $0 < 3 }) // [3, 4, 5]
let prefixed = numbers.prefix(while: { $0 < 3 }) // [1, 2]

Алгоритмическая сложность операций¶

Понимание алгоритмической сложности операций с массивами важно для написания эффективного кода. Ниже мы рассмотрим наиболее распространенные операции с массивами, их временную сложность и приведем примеры для лучшего понимания.

Добавление элементов¶

append(_:)¶

O(1) амортизированное время.

В большинстве случаев добавление элемента в конец массива происходит за константное время, так как массивы в Swift хранятся в непрерывной области памяти и имеют дополнительную емкость для новых элементов. Однако, когда внутренний буфер массива переполнен, происходит перераспределение памяти и копирование элементов в новый более крупный буфер, что может занять O(n) времени.

var numbers = [Int]()
for i in 1...1000 {
    numbers.append(i)
}

В данном примере мы добавляем 1000 элементов в массив. Несмотря на то, что операция append(_:) имеет амортизированную сложность O(1), общее время выполнения цикла будет O(n), где n — количество добавляемых элементов.

Вставка и удаление элементов¶

insert(_:at:)¶

O(n).

При вставке элемента по определенному индексу все элементы после этого индекса должны быть сдвинуты на одну позицию вправо, что требует времени, пропорционального количеству элементов после индекса.

var numbers = [1, 2, 3, 4, 5]
numbers.insert(0, at: 0) // Вставка в начало

В этом случае элементы [1, 2, 3, 4, 5] сдвигаются на одну позицию вправо, что занимает O(n) времени.

remove(at:)¶

O(n).

При удалении элемента по индексу все последующие элементы должны быть сдвинуты на одну позицию влево.

var numbers = [1, 2, 3, 4, 5]
numbers.remove(at: 2) // Удаление элемента с индексом 2

Элементы [4, 5] перемещаются на одну позицию влево, что требует O(n) времени в худшем случае.

Удаление последнего элемента¶

removeLast()¶

O(1).

Удаление последнего элемента не требует сдвига других элементов, поэтому операция выполняется за константное время.

var numbers = [1, 2, 3, 4, 5]
numbers.removeLast()

Последний элемент удаляется напрямую, не влияя на другие элементы.

Доступ к элементам¶

Доступ по индексу [i]¶

O(1).

Массивы в Swift хранятся в непрерывной области памяти, поэтому доступ к элементу по индексу происходит за константное время, используя адресную арифметику.

let numbers = [10, 20, 30, 40, 50]
let element = numbers[3] // 40

Получение элемента с индексом 3 происходит мгновенно.

Поиск элементов¶

firstIndex(of:)¶

O(n).

В худшем случае метод firstIndex(of:) может потребоваться проверить каждый элемент массива, чтобы найти совпадение.

let numbers = [1, 2, 3, 4, 5]
if let index = numbers.firstIndex(of: 5) {
    print("Индекс: \(index)")
}

Если искомый элемент находится в конце или отсутствует, потребуется O(n) операций.

Перебор массива¶

for-in цикл¶

O(n).

Итерирование по массиву требует посещения каждого элемента один раз.

for number in numbers {
    print(number)
}

Количество операций пропорционально размеру массива.

Функциональные методы¶

**map(:), filter(:), reduce(_:)**¶

O(n).

Эти методы проходят по каждому элементу массива, применяя функцию или выполняя операцию, поэтому время выполнения пропорционально количеству элементов.

let numbers = [1, 2, 3, 4, 5]

// map
let squares = numbers.map { $0 * $0 } // [1, 4, 9, 16, 25]

// filter
let evenNumbers = numbers.filter { $0 % 2 == 0 } // [2, 4]

// reduce
let sum = numbers.reduce(0, +) // 15

Каждый метод требует одного прохода по массиву.

Сортировка¶

sort() и sorted()¶

O(n log n).

Методы сортировки обычно используют алгоритмы с временной сложностью O(n log n), такие как QuickSort или MergeSort.

var numbers = [5, 2, 3, 1, 4]
numbers.sort()

Поиск максимального и минимального значения¶

max() и min()¶

O(n).

Для нахождения максимального или минимального значения необходимо проверить каждый элемент массива.

if let maxNumber = numbers.max() {
    print("Максимальное число: \(maxNumber)")
}

Проверка наличия элемента¶

contains(_:)¶

O(n).

В худшем случае метод должен проверить каждый элемент массива.

let exists = numbers.contains(3)

Если элемент отсутствует или находится в конце массива, потребуется O(n) времени.

Добавление коллекции элементов¶

append(contentsOf:)¶

O(k), где k — количество добавляемых элементов.

Добавление нескольких элементов требует копирования этих элементов в конец массива.

var numbers = [1, 2, 3]
numbers.append(contentsOf: [4, 5, 6])

Резервирование емкости¶

reserveCapacity(_:)¶

O(n).

Резервирование емкости может потребовать перераспределения памяти и копирования существующих элементов.

var numbers = [Int]()
numbers.reserveCapacity(1000)

Если массив уже имеет элементы, они могут быть скопированы в новую область памяти, что занимает O(n) времени.

Удаление всех элементов¶

removeAll(keepingCapacity:)¶

O(n).

Удаление всех элементов требует обнуления ссылок или вызова деструкторов для каждого элемента.

numbers.removeAll()

Даже если память не освобождается (при keepingCapacity: true), требуется пройти по всем элементам.

Итоговая таблица сложностей¶

Операция	Сложность
append(_:)	O(1)*
insert(_:at:)	O(n)
remove(at:)	O(n)
removeLast()	O(1)
Доступ по индексу `[i]`	O(1)
first и last	O(1)
map(_:)	O(n)
filter(_:)	O(n)
reduce(::)	O(n)
sort() и sorted()	O(n log n)
max() и min()	O(n)
contains(_:)	O(n)
append(contentsOf:)	O(k)
reserveCapacity(_:)	O(n)
removeAll()	O(n)

1. Поговорим о массивах

Введение в массивы¶

Создание массивов¶

Основные методы и операции с массивами¶

Добавление элементов¶

Удаление элементов¶

Доступ к элементам¶

Изменение элементов¶

Функциональные методы¶

map(_:)¶

compactMap(_:)¶

flatMap(_:)¶

filter(_:)¶

reduce(::)¶

reduce(into:_:)¶

forEach(_:)¶

contains(_:) и contains(where:)¶

allSatisfy(_:)¶

first(where:) и firstIndex(where:)¶

dropFirst(:) и dropLast(:)¶

prefix(:) и suffix(:)¶

enumerated()¶

zip(_:)¶

lazy¶

partition(by:)¶

sorted(by:)¶

reversed()¶

firstIndex(of:)¶

drop(while:) и prefix(while:)¶

Алгоритмическая сложность операций¶

Добавление элементов¶

append(_:)¶

Вставка и удаление элементов¶

insert(_:at:)¶

remove(at:)¶

Удаление последнего элемента¶

removeLast()¶

Доступ к элементам¶

Доступ по индексу [i]¶

Поиск элементов¶

firstIndex(of:)¶

Перебор массива¶

for-in цикл¶

Функциональные методы¶

map(:), filter(:), reduce(_:)¶

Сортировка¶

sort() и sorted()¶

Поиск максимального и минимального значения¶

max() и min()¶

Проверка наличия элемента¶

contains(_:)¶

Добавление коллекции элементов¶

append(contentsOf:)¶

Резервирование емкости¶

reserveCapacity(_:)¶

Удаление всех элементов¶

removeAll(keepingCapacity:)¶

Итоговая таблица сложностей¶

**dropFirst(:) и dropLast(:)**¶

**prefix(:) и suffix(:)**¶

**map(:), filter(:), reduce(_:)**¶