Мобильные разработчики редко сталкиваются в работе со сложными структурами данных. Как правило, в рутинных задачах вполне достаточно уметь использовать 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`.

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
Вставка	`O(log n)`
Получить минимальный элемент	`O(1)`
Получить максимальный элемент	`O(1)`
Удалить минимальный элемент	`O(log n)`
Удалить максимальный элемент	`O(log n)`

Пример планировщика задач

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

Дополнительные материалы

Изучаем новые структуры данных для iOS разработчика