Мобильные разработчики редко сталкиваются в работе со сложными структурами данных. Как правило, в рутинных задачах вполне достаточно уметь использовать Array
, Dictionary
и Set
.
На моей практике даже с этими структурами данных у разработчиков есть проблемы. Не все могут объяснить, почему, например, для ключа в словаре нужен Hashable
протокол, а для значения нет. С оценкой сложности операций также бывают проблемы. Но сегодня не об этом. Хороших статей о том, как устроены базовые структуры данных, предостаточно.
Наверное, вы слышали и о деревьях, графах, связанных списках Tree
, Graph
, Linked List,
но в повседневной работе мобильного разработчика вряд ли вы с ними сталкиваетесь. Сегодня я хотел бы рассказать о редких и недооцененных структурах данных. И самое главное, как впустить их в свою рутинную работу программиста.
За основу я взял open-source библиотеку от Apple swift-collections. Наибольший интерес для меня представляют следующие структуры данных:
Deque
Heap (Priority Queue)
OrderedSet
OrderedDictionary
Deque (Double-ended queue)
Deque
(произносится как “дек”) - структура данных, которая предоставляет возможность работать с коллекцией элементов, к которой можно добавлять и удалять элементы как с начала, так и с конца.
Вы спросите, зачем она нужна, ведь обычный массив Array
умеет делать тоже самое. Особенность заключается в том, что удаление и вставка в начало и конец имеют амортизированную сложность О(1)
, в то время как массивы требуют 0(n)
при вставке элемента в начало.
Амортизированная производительность (или амортизированное время выполнения) — это метод анализа алгоритмов, который используется для оценки среднего времени выполнения операций в последовательности, даже если некоторые операции могут быть значительно медленнее других.
Это особенность может сильно увеличить перфоманс при работе с большими коллекциями, когда необходимо вставлять и удалять элементы в начало или конец часто.
Пример использования Deque
Допустим нам понадобился класс, который отвечает за отмену и возобновления неких операций. У нас есть несколько ограничений.
Количество операций, которые можно отменить - конечно
Если мы отменили какие-то операции и совершили новые, то возможность возобновления пропадает
Работа с самой структурой данных не будет сильно отличаться от массива, интерфейс и остальные свойства схожи.
import Collections
final class UndoRedoService<Operation> {
private var operations: Deque<Operation> = []
private var lastOperationIndex = -1
private let capacity: Int
init(capacity: Int = 100) {
self.capacity = capacity
}
func register(_ operation: Operation) {
// Удаляем отмененные операции из очереди операций
if lastOperationIndex != operations.count - 1 && lastOperationIndex != -1 {
operations.removeLast(operations.count - lastOperationIndex - 1)
}
// Удаляем первую операцию в случае переполнения допустимого размера очереди
if operations.count > capacity {
operations.removeFirst()
}
operations.append(operation)
lastOperationIndex = operations.count - 1
}
func undo() -> Operation? {
guard !operations.isEmpty else { return nil }
let last = operations.last
lastOperationIndex -= 1
return last
}
func redo() -> Operation? {
guard lastOperationIndex != operations.count - 1 else { return nil }
lastOperationIndex += 1
let redo = operations[lastOperationIndex]
return redo
}
}
В данном примереDeque
будет предпочтительным выбором. Добавление новой операции в очередь, удаление первой операции в случае переполнения или удаление нескольких при наличии отмененных - эффективней, чем в Array
. Насколько эффективней, можно увидеть на графике:
![Добавление элемента в начало за константное время для Deque, но линейное для Array. Добавление элемента в начало за константное время для Deque, но линейное для Array.](https://habrastorage.org/getpro/habr/upload_files/154/112/d76/154112d76f07d8a72a5cbd2fc1cf4ad5.png)
Deque
, но линейное для Array
.Hidden text
Если хотите глубже погрузиться в особенности Deque, предлагаю решить задачу Design Circular Deque
Heap
Heap (в русско-язычной литературе можно встреть название куча) - частично-упорядоченное дерево с эффективными операциями вставки и удаления.
Элементы, хранящиеся в куче, должны соответствовать протоколу Comparable
.
public struct Heap<Element: Comparable>
Пример использования с целыми числами:
var heap = Heap([5,7,1,20,2,10,15])
print("heap.unordered: \(heap.unordered)") // heap.unordered: [1, 20, 15, 7, 2, 10, 5]
let max = heap.max
print("heap.max: \(String(describing: max))") // "heap.max: Optional(20)
let popedMax = heap.popMax()
print("heap.popMax: \(String(describing: popedMax))") // "heap.popMax: Optional(20)
let removedMax = heap.removeMax()
print("heap.removeMax(): \(String(describing: removedMax))") // "heap.removeMax(): 15
heap.insert(0)
let removedMin = heap.removeMin()
print("heap.removeMin(): \(String(describing: removedMin))") // "heap.removeMin(): 0
print("heap.unordered: \(heap.unordered)") // heap.unordered: [1, 7, 10, 5, 2]
Сложность операций в Heap
Operation | Complexity |
---|---|
Вставка |
|
Получить минимальный элемент |
|
Получить максимальный элемент |
|
Удалить минимальный элемент |
|
Удалить максимальный элемент |
|
Пример планировщика задач
Heap
можно применить при решении разных задач, например:
Очередь запросов в сеть или базу данных;
Обработка мультимедиа (аудио и видео);
Обработка уведомлений в порядке важности.
Допустим, у нас есть некая структура Task
. Под ней может подразумеваться любой тип задачи, запрос в сеть, базу данных, любая тяжеловесная задача.
struct Task: Comparable {
enum Priority: Comparable {
case low
case medium
case high
}
let id: String
let priority: Priority
let action: () -> Void
static func < (lhs: Task, rhs: Task) -> Bool {
return lhs.priority < rhs.priority
}
static func == (lhs: Task, rhs: Task) -> Bool {
lhs.id == rhs.id && lhs.priority == rhs.priority
}
}
структура
Task
соответствует протоколуComparable
;Сравнимость задается в зависимости от приоритетов (
low
,medium
,high
).
final class TaskScheduler {
private var taskQueue = Heap<Task>()
// Добавляет новую задачу в очередь
func scheduleTask(_ task: Task) {
taskQueue.insert(task)
executeNextTaskIfExist()
}
// Достает и исполняет самую приоритетную задачу, если есть в очереди
private func executeNextTaskIfExist() {
guard let task = taskQueue.popMax() else { return }
task.action()
// взять новую задачу если есть
}
}
TaskScheduler
контролирует порядок выполнения задач в соответствии с Task.Priority
OrderedSet
OrderedSet
- мощный и удобный гибрид Array
и Set
Элементы коллекции должны соответствовать протоколу Hashable
. Главное отличие от обычного Set
- теперь мы можем обращаться по индексу к элементам, и порядок не будет нарушен.
Для себя я нашел удобное применение этой коллекции в iOS при работе с Diffable Data Source
. Обычно для работы с этим API используют массив в качестве источника данных. Но может возникнуть ситуация, когда в этом дата сорсе окажутся дубли. Тогда или мы увидим повторяющиеся элементы на экране, или, что еще хуже, краш в случае неправильной реализации Hashable
протокола.
Пример использования OrderedSet
В качестве данных будем использовать структуру Item
struct Item: Hashable {
let id: String
let title: String
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
static func == (lhs: Item, rhs: Item) -> Bool {
lhs.id == rhs.id
}
}
Допустим, у нас есть экран c UITableView
и UITableViewDiffableDataSource
class DiffableViewController: UIViewController {
var tableView: UITableView!
var dataSource: UITableViewDiffableDataSource<Int, Item>!
var items = [Item]()
override func viewDidLoad() {
super.viewDidLoad()
tableView = UITableView(frame: view.bounds, style: .plain)
view.addSubview(tableView)
dataSource = UITableViewDiffableDataSource<Int, Item>(tableView: tableView) { (tableView, indexPath, item) -> UITableViewCell? in
let cell = tableView.dequeueReusableCell(withIdentifier: "cell", for: indexPath)
cell.textLabel?.text = item.title
return cell
}
tableView.register(UITableViewCell.self, forCellReuseIdentifier: "cell")
// 1
let item1 = Item(id: UUID().uuidString, title: "Item 1")
let item2 = Item(id: UUID().uuidString, title: "Item 1")
items.append(item1)
items.append(item2)
// warning: Две одинаковые строки будут отображены на экране
updateSnapshot()
// 2
let item3 = Item(id: "123456789", title: "Item 3")
let item4 = Item(id: "123456789", title: "Item 4")
items.append(item3)
items.append(item4)
// crash: Приведет к крашу, так как item3 и item4 будут иметь одинаковый хэш
updateSnapshot()
}
func updateSnapshot() {
var snapshot = NSDiffableDataSourceSnapshot<Int, Item>()
snapshot.appendSections([0])
snapshot.appendItems(items)
dataSource.apply(snapshot, animatingDifferences: true)
}
func addItem(_ newItem: Item) {
items.append(newItem)
updateSnapshot()
}
В первом случае мы добавляем два одинаковых
Item
, но посколькуUUID
генерирует разное значение, мы просто увидим две одинаковые ячейки на экране;Во втором случае
id
будет одинаковое, что приведет к падению приложения.Diffable Data Source
принимает только уникальные объекты.
Отследить, что хэши всегда разные может быть проблемой, особенно если мы хотим завязаться на данные с бэка. В этом случае на помощь приходит OrderedSet
. Он поможет отфильтровать дубли и передавать в снепшот только уникальные значения.
var items = OrderedSet<Item>()
...
func updateSnapshot() {
var snapshot = NSDiffableDataSourceSnapshot<Int, Item>()
snapshot.appendSections([0])
snapshot.appendItems(Array(items)) // конвертируем в массив
dataSource.apply(snapshot, animatingDifferences: true)
}
OrderedDictionary
OrderedDictionary
- упорядоченная коллекция пар ключ-значение. OrderedDictionary
обладает свойствами как словаря, так и массива.
import OrderedCollections
@frozen struct OrderedDictionary<Key: Hashable, Value>
Сразу рассмотрим пример использования из реального проекта на iOS.
Пример использования OrderedDictionary
У нас есть структура некого поста, например, как в социальных сетях:
struct Post: Codable {
let id: String
var title: String
var content: String
}
Также есть API
, которое возвращает новые и обновленные посты в методе fetchPosts
struct PostsResponse: Codable {
let newPosts: [Post]
let updatedPosts: [Post]
}
...
func fetchPosts() async throws -> PostsResponse
Менеджер PostManager
отвечает за добавление и обновление постов по следующей логике:
final class PostManager {
typealias ID = String
/// Хранит посты в заданном порядке
private var postArray: [Post] = []
/// Хранит пару id и порядковый номер поста
private var postDictionary: [ID: Int] = [:]
func addOrUpdatePosts(_ response: PostsResponse) {
// Проверяем, что таких постов еще нет и добавляем в конец
for post in response.newPosts where postDictionary[post.id] == nil {
postArray.append(post)
postDictionary[post.id] = postArray.count - 1
}
// Находим пост по id чтобы обновить его в массиве
for post in response.updatedPosts {
if let index = postDictionary[post.id] {
postArray[index] = post
}
}
}
}
Теперь попробуй отрефакторить этот код. В игру вступает OrderedDictionary
:
private var posts = OrderedDictionary<ID, InstagramPost>()
func addOrUpdatePosts(_ response: PostsResponse) {
// Если пост новый, то он добавится в конец
for post in response.newPosts {
posts[post.id] = post
}
// Если пост существует, то он обновится
for post in response.updatedPosts {
posts[post.id] = post
}
}
Использование OrderedDictionary
значительно упрощает задачу, так как объединяет функциональность массива и словаря:
Поддерживает порядок элементов;
Обеспечивает уникальность ключей;
Упрощает добавление и обновление элементов.
В то время как использование отдельного массива и словаря требует дополнительной логики и увеличивает шанс совершить ошибку.
Использование OrderedDictionary
делает код более чистым и поддерживаемым.
Заключение
Цель этой статьи донести до читателя пользу эффективных структур данных и показать, как их использовать в рутинных задачах iOS разработчику.
Если у меня получилось заинтересовать вас этой статьей, то бонусом предлагаю разобраться с Trie
. За вопросом, “Как работает поиск в Google?” скрывается именно эта структура данных. На моем собеседовании как раз таки в Google мне его и задали.
Зачастую можно услышать утверждение, что алгоритмы и структуры данных не нужны, особенно мобильным разработчикам. На мой взгляд правда где-то посередине. Не стоит пытаться изучить все возможные хитрые алгоритмы и приемы, эти знания вряд ли найдут применения.
Я чувствую, что умение решать алгоритмические задачи и умение правильно выбрать структуру данных помогаем мне осознанней писать код, совершать меньше ошибок, заранее видеть корнер кейсы и выстраивать логические цепочки до момента имплементации.
Еще один лайфхак, который помогает не сдаваться, если я не могу решить сложную задачу на LeetCode, относится к этому как к игре в шахматы. Сегодня ты проиграл, (не смог решить задачу) но завтра ты пришел с новыми знаниями и победил. Спортивный интерес дает энергию для самосовершенствования.
PS. Чтобы узнать больше о мобильной разработке и жизни в Лондоне залетайте в мой Telegram канал https://t.me/ios_mobile_developer