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

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

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()
    }

1. В первом случае мы добавляем два одинаковых Item, но поскольку UUID генерирует разное значение, мы просто увидим две одинаковые ячейки на экране;

2. Во втором случае 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

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

• Introducing Swift Collections

• https://github.com/apple/swift-collections/blob/main/Documentation/Heap.md

• https://github.com/apple/swift-collections/blob/main/Documentation/OrderedSet.md

• https://github.com/apple/swift-collections/blob/main/Documentation/OrderedDictionary.md