Выбираем правильную структуру данных в Swift

И снова здравствуйте. Прежде чем уйти на выходные хотим поделиться с вами переводом материала, который был подготовлен специально для базового курса «iOS-разработчик».

---

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

Стандартная библиотека Swift поставляется с тремя основными структурами данных — Array, Dictionary и Set, каждая из которых имеет свой набор оптимизаций, плюсов и минусов. Давайте рассмотрим некоторые из их характеристик, а также случаи, когда нам может понадобиться выйти за рамки стандартной библиотеки, чтобы найти правильную структуру данных для наших целей.

Линейность массивов

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

Например, здесь мы используем массив для хранения коллекции фигур, помещенных на Canvas в приложении для рисования. Затем, когда нужно будет визуализировать canvas в изображение, мы просто пройдем по массиву, чтобы нарисовать каждый элемент с помощью DrawingContext — следующим образом:

struct Canvas {
    var shapes: [Shape]

    func render() -> Image {
        let context = DrawingContext()
        shapes.forEach(context.draw)
        return context.makeImage()
    }
}

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

Однако, как и все другие структуры данных, массивы имеют свои недостатки. В нашем случае мы столкнемся с одним из его недостатков, когда захотим удалить фигуры с canvas. Поскольку элементы массива хранятся по индексу, нам всегда нужно сначала найти с каким индексом связана данная фигура, прежде чем мы сможем удалить ее:

extension Canvas {
    mutating func remove(_ shape: Shape) {
        guard let index = shapes.firstIndex(of: shape) else {
            return
        }

        shapes.remove(at: index)
    }
}

Поначалу приведенный выше код может показаться не таким уж проблематичным, но он может стать узким местом в плане производительности для любого canvas, содержащего большое количество фигур, поскольку firstIndex является линейной (O(N)) с точки зрения временной сложности.

Хотя мы можем обойти это ограничение там, где мы используем наш тип Canvas. Например, всегда обращаясь к фигурам по индексу, а не по значению или ID — это сделало бы наш код более сложным и более хрупким, поскольку мы всегда должны бы были быть уверенными, что наши индексы не устареют, когда canvas, с которым мы работаем, изменится.

Скорость множеств

Вместо этого давайте посмотрим, сможем ли мы оптимизировать сам Canvas, изменив его базовую структуру данных. Рассматривая вышеупомянутую проблему, одной из наших первоначальных идей может быть использование Set (множества) вместо Array. Как мы уже рассматривали в статье The power of sets in Swift (Сила множеств в Swift), одно из значительных преимуществ множеств над массивами заключается в том, что как вставка, так и удаление всегда могут выполняться за постоянное (O(1)) время, так как элементы хранятся по значению хеша, а не по индексу.

Обновив Canvas таким образом, чтобы в нем использовались множества, мы получим следующее:

struct Canvas {
    var shapes: Set<Shape>

    func render() -> Image {
        let context = DrawingContext()
        shapes.forEach(context.draw)
        return context.makeImage()
    }

    mutating func remove(_ shape: Shape) {
        shapes.remove(shape)
    }
}

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

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

Давайте продолжим экспериментировать. Теперь посмотрим, сможем ли мы оптимизировать Canvas, введя Dictionary (словарь), который позволяет нам искать индекс любой фигуры на основе его ID. Мы начнем с того, что изменим уровень доступа для нашего массива shapes на private, чтобы иметь возможность контролировать вставку элементов, используя новый метод add. И каждый раз, когда добавляется новая фигура, мы также добавляем ее индекс в наш словарь:

struct Canvas {
    private var shapes = [Shape]()
    private var indexes = [Shape.ID : Int]()

    func render() -> Image {
        let context = DrawingContext()
        shapes.forEach(context.draw)
        return context.makeImage()
    }

    mutating func add(_ shape: Shape) {
        let index = shapes.count
        indexes[shape.id] = index
        shapes.append(shape)
    }
}

Поскольку теперь мы всегда знаем, по какому индексу хранится данная фигура, мы можем быстро выполнять удаление за постоянное время, как при использовании множества:

extension Canvas {
    mutating func remove(_ shape: Shape) {
        guard let index = indexes[shape.id] else {
            return
        }

        shapes.remove(at: index)
        indexes[shape.id] = nil
    }
}

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

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

Итак, давайте попробуем еще раз с другой комбинацией, но на этот раз начнем с рассмотрения наших реальных требований:

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

Глядя на вышеприведенные требования, получается, что хотя нам нужен стабильный порядок перебора, нам на самом деле не нужны индексы. Это сделало бы связный список идеально подходящим для нашего варианта использования.

Связные списки состоят из узлов, где каждый узел содержит ссылку (или связь) на следующий узел в списке, что означает, что его можно перебирать предсказуемым образом — без необходимости каких-либо обновлений индекса при удалении элемента. Однако стандартная библиотека Swift (пока) не содержит тип связного списка, поэтому, если мы хотим его использовать, то его сначала нужно создать.

Создание связного списка

Давайте начнем с объявления структуры List (список), которая будет отслеживать первый и последний узлы в нашем списке. Мы сделаем оба эти свойства доступными только для чтения вне нашего типа, чтобы обеспечить согласованность данных:

struct List<Value> {
    private(set) var firstNode: Node?
    private(set) var lastNode: Node?
}

Далее, давайте создадим наш тип Node (узел), который мы сделаем классом, поскольку мы хотим иметь возможность ссылаться на узлы по ссылке, а не по значению. Наш список будет двусвязным, что означает, что каждый узел будет содержать ссылку как на своего следующего соседа, так и на предыдущего. Каждый узел также будет хранить значение — вот так:

extension List {
    class Node {
        var value: Value
        fileprivate(set) weak var previous: Node?
        fileprivate(set) var next: Node?

        init(value: Value) {
            self.value = value
        }
    }
}

Причина, по которой свойство previous мы делаем weak, состоит в том, чтобы избежать retain-циклов, которые появились бы, если бы мы сохраняли сильные ссылки в обоих направлениях. Чтобы узнать больше о том, как избежать retain-циклов, ознакомьтесь со статьей “Memory Management” (Управление памятью).

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

extension List: Sequence {
    func makeIterator() -> AnyIterator<Value> {
        var node = firstNode

        return AnyIterator {
             // Перебирает все узлы, последовательно переходя к следующему, и извлекает его значение:
            let value = node?.value
            node = node?.next
            return value
        }
    }
}

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

Далее, давайте добавим API для изменения нашего связного списка, начиная с вставок. Мы расширим List с помощью метода append, который добавляет новый узел для вставляемого значения, а затем возвращает этот узел — вот так:

extension List {
    @discardableResult
    mutating func append(_ value: Value) -> Node {
        let node = Node(value: value)
        node.previous = lastNode

        lastNode?.next = node
        lastNode = node

        if firstNode == nil {
            firstNode = node
        }

        return node
    }
}

Выше мы используем атрибут @discardableResult, который говорит компилятору не генерировать никаких предупреждений в случае, если результат вызова нашего метода не использовался, поскольку нас не всегда интересует узел, который был создан.

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

extension List {
    mutating func remove(_ node: Node) {
        node.previous?.next = node.next
        node.next?.previous = node.previous

        // Используя «тройное равенство», мы можем сравнивать два экземпляра класса по тождеству, а не по значению:
        if firstNode === node {
            firstNode = node.next
        }

        if lastNode === node {
            lastNode = node.previous
        }
    }
}

С учетом вышеизложенного начальная версия нашего List завершена, и мы готовы проверить его в деле. Давайте обновим Canvas, чтобы использовать наш новый список, а также словарь, который позволяет нам быстро искать, какой узел соответствует данному ID фигуры:

struct Canvas {
    private var shapes = List<Shape>()
    private var nodes = [Shape.ID : List<Shape>.Node]()

    func render() -> Image {
        let context = DrawingContext()
        shapes.forEach(context.draw)
        return context.makeImage()
    }

    mutating func add(_ shape: Shape) {
        nodes[shape.id] = shapes.append(shape)
    }

    mutating func remove(_ shape: Shape) {
        guard let node = nodes.removeValue(forKey: shape.id) else {
            return
        }

        shapes.remove(node)
    }
}

Теперь у нас есть как быстрые вставки и удаления, так и предсказуемый порядок перебора, без необходимости добавлять дополнительную сложность в процесс вызова — это довольно круто! И, поскольку наш новый List — полностью универсальный тип, теперь мы можем использовать его всякий раз, когда нам снова нужно будет хранить значения без индекса линейным образом.

Заключение

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

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

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

Вы можете найти меня в Твиттере или напишите мне, если у вас есть какие-либо вопросы, комментарии или отзывы.

Спасибо за внимание!

Автор: MaxRokatansky

Источник