Быстрый гайд по коллекциям в Swift (Array, Set, Dictionary)

Для чего и кого статья?

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

Array (массив)

Это коллекция упорядоченных элементов по индексам (Ordered random-access collection).

1. Асимптотика (скорость операции или алгоритма по количеству итераций):

• Чтение - O(1) (чтение по индексу)

• Поиск - O(N) (проходим по всему массиву и ищем подходящий элемент)

• Добавление - O(1) в лучшем случае и O(N) в худшем случае

  • если в начало и надо сдвигать массив

  • если в конец и надо переносить непомещающийся массив в новую память

• Удаление - O(N) (при удалении надо сдвигать элементы)

2. Как устроен Array?

Выбирается сплошной участок памяти, делится на части по индексам c 0, и упорядоченно кладутся все элементы.

Элементы массива хранятся упорядоченно в памяти, где доступом к участку памяти будет индекс.

3. Полезные методы:

Список оценок

var grades = [5, 4, 3, 4, 1, 5, 5, 4, 5, 5, 2]

Получение максимальной и минимальной оценки из списка

grades.min()
grades.max()

Поставили оценку в начало

grades.insert(5, at: 0)

Удаляем 5 оценку в списке

var deletedGrade = grades.remove(at: 4)

Средняя арифметическая оценка

var average = 0
for item in grades {
		average = average + item
}

print (Double(resultAverage) / Double(grades.count))

Медианная оценка (удаляем самую min и самую max)

var minGrade = grades.min() ?? 0 //nil coalescing - оператор замены nil
var maxGrade = grades.max() ?? 0

var minIndex = grades.firstIndex(of: minGrade) ?? 0
var maxIndex = grades.firstIndex(of: maxGrade) ?? 0

//Удаляем оценку min и max из списка
grades.remove(at: minIndex)
grades.remove(at: maxIndex)

var average = 0
for item in grades {
		average = average + item
}

var medianGrade = Double(resultAverage) / Double(grades.count) //Type conversion - привидени типов
print(medianGrade)

Первые 3 оценки и последние 3 оценки из списка

print( grades.prefix(3) )
print( grades.suffix(3) )

Проверить есть ли оценка 2 в списке

print( grades.contains(where: { $0 == 2 }) ) //$0 - сокращенная запись элемента коллекции (short hand syntax param)

Получить все положительные оценки > 3

var allPositiveGrades = grades.filter { $0 > 3 }
print(allPositiveGrades)

Получить все отрицательные оценки < 3

var allNegativeGrades = grades.filter { $0 < 4 }
print(allNegativeGrades)

Поиск оценки 1 в списке

print( grades.first(where: { $0 == 1 }) )

Удалить все низкие оценки из списка

print( grades.removeAll { $0 < 4 } )
print(grades)

Set (множество)

Это неупорядоченная коллекция уникальных элементов (Unordered collection of unique elements).

1. Асимптотика:

• Поиск - O(1) в среднем случае (поиск по хеш-числу)

• Добавление - O(1) в среднем случае (поиск по хеш-числу)

• Удаление - O(1) в среднем случае (поиск по хеш-числу)

  В худшем случае если будут коллизии то O(N) для всех операций.

Коллизия - это когда совпадают хеш-коды у элементов.

2. Как устроен Set (Hash Set)?

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

Если элементы разные, то кладутся в ту же ячейку памяти, но как связный список (Linked List).

Если хеш-код и значение одинаковы, то элемент не кладется, так как уже лежит ячейке.

Элемент → Хеш-функция → Хеш-код → Индекс массива

var gradesArray: Array<Int> = [4, 5, 4, 3, 5, 5] // -> [4, 5, 4, 3, 5, 5]
var gradesSet: Set<Int> = [4, 5, 4, 3, 5, 5] // -> [4, 5, 3]

/*
item ("Farida") -> хеш-функция -> хеш-число (5) -> индекс внутр массива (5)
[][][][][]["Farida"] -> 64байт -> 2^64
"Farida" -> 611051
*/

print(gradesSet, type(of: gradesSet))

3. Полезные методы:

Множество купюр в коллекции

var wallet = Set([100, 10, 20, 200, 500, 1, 2, 50])

Создание множества оценок через диапазон

var grades = Set(1...10) //в массиве тоже можно

Добавление купюры в кошелек

wallet.insert(1000)

Проверка: есть ли купюра в кошельке

print( wallet.contains(where: { $0 == 100 }) )

Отфильтровать купюры больше 100

print( wallet.filter { $0 > 100 } )

Dictionary (словарь)

Это коллекция пар ключ-значение (Collection of pairs key-value).

1. Асимптотика:

   • берем реализацию Set

   • вместо элементов кладем пары "key: value"

   • getHashCode или сравнение элементов берем у ключей

     P.S. в NSDictionary используется HashSet. Асимптотика Dictionary зависит от того, на каком Hash Set она построена.

2. Как устроен Dictionary (Hash Map)?

Тот же самый механизм, что и у Set. Отличие только в том, что хеш-код берется не от элемента, а от ключа и кладется в массив не элемента, а как пара "key: value" KeyValuePair<Key, Value>

Ключ → Хеш-функция → Хеш-код → Индекс массива

3. Полезные методы:

Создание словаря бомбардиров

var footballers: [String: Int] = [
    "Ronaldo": 7,
    "Messi": 10
]

Получение доступа к кол-ву голов Ronaldo

let num = footballers["Ronaldo"]
print(num) // prints Optional(7)

Ronaldo забил еще пару голов, обновим словарь (изменяем значение)

// Subscript syntax
footballers["Ronaldo"] = 9
// OR
// updateValue method
footballers.updateValue(9, forKey:"Ronaldo")

Удаление футболиста 

var footballers: [String: Int] = [
    "Ronaldo": 7,
    "Messi": 10
		"Bale": 9
]

let baleNum = footballers.removeValue(forKey: "Bale")
print(baleNum) // Prints Optional(9)

Подсчет бомбардиров

footballers.count

Итерация по бомбардирам

for (player, number) in footballers {
    print("\(player) has number \(number).")
}// "Ronaldo has number 7"
// "Messi has number 10"

Список футболистов

let names = footballers.keys 
print(names) // prints e.g. ["Ronaldo", "Messi"]

Список голов

let numbers = footballers.values 
print(numbers) // prints e.g. [7, 10]