Автор статьи: Павел Плотников
iOS-разработчик в BestDoctor. Преподаватель в OTUS
Протоколы иерархии Sequence/Collection имеют одно из самых важных значений в Swift, начиная со встроенности в язык (например, конструкция цикла for in) и заканчивая популярными функциями высшего порядка map, reduce и т.п. Часто разработчики путаются в особенностях, не осознавая возможности, предоставляемые отдельными протоколами иерархии коллекций. Давайте попробуем разобраться с этими особенностями на примере одной функции, которая по разному реализуется в этих протоколах — функция suffix.
Функция suffix возвращает массив из заданного количества элементов взятых с конца последовательности. Мы рассмотрим работу этой функции на основе реализации по умолчанию у протоколов Sequence, Collection, BidirectionalCollection и RandomAccessCollection. Все эти протоколы последовательно наследуются друг от друга и на каждом уровне наследования добавляются новые возможности начиная с примитивного последовательного доступа и заканчивая прямым индексным доступом за время O(1).
Прежде всего хотелось бы отметить, что исходники протоколов и реализации функций по умолчанию доступные Open Source и вы сами можете изучить многие особенности работы этих протоколов. Я думаю это прекрасная стартовая возможность входа в изучение внутренностей библиотек в Swift.
Протокол Sequence
Базовый протокол всей иерархии коллекционных протоколов. Основная возможность протокола — способность перебирать элементы последовательности один за другим посредством итератора, который вы получаете через вызов функции makeIterator. Именно таким образом работает цикл for in, когда под капотом вызывается функция makeIterator и затем в цикле на полученном итераторе вызывается next(). Количество элементов в последовательности может быть ограниченным или неограниченным. Итерирование может быть деструктивным (при повторной итерации элементов может не быть в последовательности) или не деструктивным. Из-за этих особенностей у протокола нет свойства count, но для оптимизационных целей есть свойство underestimatedCount, которое при реализации функций по умолчанию позволяет зарезервировать память заранее, чтобы уменьшить вероятность ее выделения динамически в процессе работы.
Однако, такой простой принцип — перебор по одному элементов последовательности позволяет реализовать большую часть всеми известных функций. Именно на протоколе Sequence определены такие функции как map, prefix, suffix, contains, first, min, max, drop, sorted, и т.д. Для всех этих функций протокол имеет реализацию по умолчанию. Эти реализации могут быть далеко не оптимальными, но и требовать большего от протокола который реализует только перебор мы не можем. Мы привыкли получать мгновенный доступ, например, к последнему элементу в наших привычных массивах (которые являются дальними наследниками протокола Sequence), но в протоколе Sequence, вам придется последовательно перебрать все элементы, чтобы получить последний элемент. Простота этого протокола ограничивается только перебором и единственное что вы должны сделать, если хотите реализовать протокол — реализовать итератор.
Поскольку мы имеем только возможность итерации элементов, то чтобы добраться до последних n элементов (которые должна вернуть функция suffix(k)), нам нужно перебрать все элементы и складывать все элементы в структуру RingBuffer, которая будет хранить все последние пройденные элементы. Первый элемент последовательности сохранится в нулевой ячейке массива RingBuffer, второй во первой, k-ый элемент в k-1-ую ячейку RingBuffer, k+1 элемент мы опять кладем в нулевую ячейку и так далее. В итоге, когда мы переберем все элементы последовательности в нашем RingBuffer будут хранится k последних элементов и нам останется только правильно склеить эти k элементов из массива RingBuffer. Вся эта работа, чтобы вернуть k элементов будет стоить O(n), — нам нужно в цикле пройти по всем элементам последовательности. Дороговато!
Реализацию функции suffix для Sequence можно найти здесь.
Протокол Collection
Collection — следующий протокол в иерархии, который наследуется напрямую от Sequence. К простому перебору элементов у этого протокола появляются новые способности. Во-первых декларируется недеструктивный доступ к элементам (перебор), во-вторых обеспечивается доступ по индексам в том-же порядке что и перебор. Кроме того, добавляются основные функции для работы с индексами — получение индекса на основе предыдущего index(after:), стартовый startIndex и последний endIndex (особенность которого заключается в том, что если хотите получить последний элемент, то вам нужно обратится по предыдущему индексу от endIndex, возможности subscript на endIndex нет) индексы коллекции.
Несмотря на то, что мы индексы часто воспринимаем просто как числа, в протоколе это не декларируется и требуемые индексы нужно отдельно вычислять. Мы не можем получить сразу пятый элемент коллекции, нам сначала нужно вычислить пятый индекс коллекции, а это тоже может быть не простым делом. Сначала нам нужно получить 0-ой индекс, потом на основе первого, получить 1-ый индекс и так далее. В итоге чтобы получить k-ый индекс коллекции нам нужно проделать последовательно k-операций. Еще раз повторю — у нас нет мгновенного доступа к k-ому элементу, у нас есть мгновенный доступ к элементу который находится по k-ому индексу, но чтобы этот индекс получить, нам все равно нужно проделать много работы — перебрать все предыдущие индексы начиная со стартового индекса.
Более того, получить следующий индекс мы можем только на основе предыдущего, но мы не можем получить индекс k-1 на основе индекса k (т.е. в обратно порядке). Работа по получению индексов (а это как вы уже поняли одна из основных функциональностей для этого протокола и последующих) работает в одном направлении — с начала в конец. Чтобы получить индекс последнего элемента с конца (который предшествует endIndex), нам нужно перебрать со стартового индекса n-1 индексов.
Протокол Collection дал нам возможность обращаться по индексам, и кажется это то что нам нужно, чтобы вернуть suffix(k) — достаточно просто обратится по индексам к последним k элементам — что-то типа collection[startSuffix..<endIndex], но дьявол как раз кроется в том, что чтобы получить индексы этих последних элементов — нам все равно нужно перебрать все индексы начиная со startIndex, последовательно вызывая index(after:). Да, в исходниках реализации вы увидите вызов index(:offsetBy:), но внутри этой функции все равно последовательно вызываются index(after:) один за другим и начиная со startIndex, пока мы не доберемся до n-k-го индекса. Получается итоговая дефолтная реализация suffix у Collection опять получается со сложностью O(n), но она уже основана не на переборе самих элементов, а на вычислении последовательно индексов с начала до конца, что выглядит уже не так тяжело.
Реализацию функции suffix для Collection можно найти здесь.
Протокол BidirectionalCollection
Если предыдущий протокол Collection заявлял возможность вычисления индексов в одном направлении, то протокол BidirectionalCollection, который наследуется от Collection, как вы уже наверное поняли из названия добавляет простую возможность — функция получения индексов в обратном направлении — с конца в начало (старая возможность получения с начала в конец конечно же остается, как и все фишки Sequence перебора элементов). Таким образом, у нас появилась функция index(before:) и по сути это единственное из новшеств, что дает этот протокол. Такая простая возможность дает нам достаточно быстро получить последний элемент last — он находится по индексу index(before: endIndex). Кроме того, теперь мы достаточно легко можем получить reversed — перевернутую в обратном порядке последовательность.
Давайте теперь посмотрим что это значит для нашей функции suffix(k). Итак, чтобы получить последние k элементов, мы также должны вычислить их индексы последовательно с конца вызывая index(before:). Эти последовательные вызовы скрыты в вызове функции index(endIndex, offsetBy:-k) и затем получить эти элементы по вычисленным индексам с помощью обращения по subscript (с использование квадратных скобок, — например collection[startSuffix..<endIndex]). Но, как мы понимаем, в данном случае нам уже нужно выполнить k операций, а не n (равное количеству элементов в коллекции). Получаем вычислительную сложность этого подхода — O(k).
Реализацию функции suffix для BidirectionalCollection можно найти здесь.
Протокол RandomAccessCollection
Последний протокол в нашей статье (но протоколов последовательностей в Swift гораздо больше, мы лишь остановились на основных), который никаких новых функций не привносит в наш мир, но дает нам иную полезность ("это другое"). Смысл этого протокола — в объявлении, что основные функции работы с индексами index(_:offsetBy:) и distance(from:to:) должны работать за время O(1), т.е. протокол говорит, что теперь никаких переборов индексов — все индексы должны вычисляться сразу за O(1). Если мы хотим получить 5-ый индекс коллекции RandomAccessCollection, то мы просто вызываем index(startIndex,offsetBy:5) и мгновенно без перебора под капотом получаем этот индекс. Именно так работают массивы, когда мы хотим получить 5-ый элемент массива, мы просто передаем в subscript число 5 и получаем нужный элемент. Именно этот протокол реализуют привычные нам массивы Array.
Что касается функции suffix, то вы не найдете отдельной реализации этой функции и будет использоваться предыдущая реализация из BidirectionalCollection, основанная на вычислении индекса стартового элемента суффикса начиная с конца index(endIndex, offsetBy:-k). Но, как мы уже говорили, эта функция теперь не перебирает индексы один за другим, а за время O(1) может определить нужный индекс. Упрощенно говоря, чтобы вычислить n-k-ый индекс в массиве, нам нужно сделать одну операцию вычисления "n-k", которая выполняется, как мы знаем, моментально за O(1).
Заключение
Как мы увидели базовые последовательности развиваются постепенно от банального перебора элементов в Sequence (что уже дает великое множество известных нам операций), далее в Collection добавляется возможность работы с индексами с некоторыми ограничениями (нужно вычислять индексы, притом только в одном направлении).
После Collection идет BidirectionalCollection, который добавляет дополнительную "ачивку" перебора индексов в обратном порядке. А завершает нашу базовую иерархию RandomAccessCollection, который не дает новых функций, но налагает ограничения на функции работы с индексами, которые должны быть реализованы за время O(1). Именно эту коллекцию реализуют известные нам обычные массивы в Swift.
Статью подготовил преподаватель OTUS Павел Плотников в преддверии старта курса «iOS Developer. Professional».
Всех желающих приглашаем на бесплатное demo-занятие «Пишем выразительный код на Swift 5.x». В версиях 5.0, 5.1, 5.2, 5.3, 5.4, 5.5 языка программирования Swift появилось много нововведений, позволяющих программировать более эффективно. На этом занятии рассмотрим на практических примерах самые важные из них и обзорно все оставшиеся.