Exam

Практический зачет

Иммутабельный вектор

Постановка задачи

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

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

Идея решения

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

Такое дерево объявляется следующим образом:

• type 'a Tree = Empty | Leaf of 'a | Branch of 'a Tree * 'a Tree (F#);
• data Tree a = Empty | Leaf a | Branch (Tree a) (Tree a) (Haskell).

Для удобства потребуем, чтобы in-order-обход дерева перечислял элементы вектора слева направо. Таким образом, первый элемент будет лежать в самом левом листе дерева, а последний — в самом правом. Тогда при вставке элемента в начало вектора будем опускаться налево, пока не дойдем до листа, и затем разбить этот лист на два поддерева: в левом новый элемент, а в правом старый.

Использование деревьев сокращает объем копирования. Раньше на такую операцию требовалось копировать веь вектор, но теперь ясно: лист, в котором потребуются изменения, только в одном поддереве. Следовательно, копирование второго поддерева не нужно. Действительно, можно в новом дереве сохранить ссылку на поддерево в старом дереве. И такая оптимизация происходит на каждом шаге по ходу от корня к листу.

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

Индексация элементов

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

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

1. Пусть листья лежат одной и той же глубине 32;
2. Элементы вектора заполняют нижний слой слева направо без пропусков.

Эти ограничения не нарушают условие об in-order-обходе дерева.

Теперь, чтобы дойти до заданного элемента в дереве, требуется 32 шага налево или направо. Тогда, если закодировать шаг влево нулем, а шаг вправо единицей, получится, что первый элемент вектора лежит на пути с кодом 0b0, второй — 0b1, третий — 0b10 и так далее: двоичное представление индекса элемента образует код пути к этому элементу в дереве. В результате получили префиксное дерево, где ключи — индексы элементов.

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

Внутренний индекс

Следующий шаг — чтобы удаление первого элемента не влияло на индексы остальных элементов. В каждом дереве индексы лежат в диапазоне с 0 по n - 1, и изменение этого инварианта нарушит преобразование индекса в путь — двоичное представление. Поэтому сделаем такой трюк: пусть при удалении первого элемента индексы в дереве будут не с 0 по n - 2, а с 1 по n - 1.

Следовательно, представим вектор не просто как дерево, а как дерево с диапазоном индексов с from по until - 1, а операции с вектором пусть меняют этот диапазон следующим образом:

1. appended увеличивает until на 1;
2. initV уменьшает until на 1;
3. prepended уменьшает from на 1;
4. tailV увеличивает from на 1.

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

Для пользователя индексы должны оставаться в диапазоне с 0 по n - 1, поэтому, когда к вектору будет запрос на доступ к i-му элементу, ему вернется from + i-й лист в дереве.

Отрицательные индексы

Подобная структура обязывает поддерживать отрицательные индексы, а это в свою очередь влияет на преобразование индексов в пути в дереве. На самом деле это не так страшно: будем, как и раньше, смотреть на битовое представление индекса: тогда если индекс отрицательный, то старший бит равен 1, а если неотрицательный, то 0. Так, при вставке по -1-му индексу элемент добавляется в последний правый лист дерева.

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

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

Собираем все вместе

Вектор представляется как бинарное префиксное дерево и границы диапазона индексов элементов.

Объявление вектора на F#:

type 'a PrefixTree =
    | Empty
    | Leaf of 'a
    | Branch of 'a PrefixTree * 'a PrefixTree

type 'a Vector = Vector of int * int * 'a PrefixTree
// Vector (from, until, tree)

Объявление вектора на Haskell:

data PrefixTree a = Empty
                  | Leaf a
                  | Branch (PrefixTree a) (PrefixTree a)

data Vector a = Vector Int Int (PrefixTree a)
-- Vector from until tree

Основные моменты:

1. В префиксном дереве листья лежат на глубине 32;
2. Элемент по индексу i в векторе лежит в дереве на пути, заданным двоичным представлением числа from + i. Это работает даже в случае, когда число from + i отрицательное;
3. Так как глубина дерева равняется 32, то сложность поиска, добавления или удаления в начало или в коне логарифмическая.

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

Интересующиеся могут прочитать в разделе «Реальность» способ, как улучшить производительность до «фактически константной».

Задание

Задание состоит из двух частей: дописать 1) префиксное дерево и 2) вектор на базе этого префиксного дерева.

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

Кроме того, есть константа empty представляет пустой вектор. Этот объект будет доступен пользователю, так как лучше скрыть внутренний индекс вектора как деталь реализации.

Каждая из функций оценивается в 1 или 2 балла, полное решение оценивается в 20 баллов.

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

Организационная информация

API вектора предполагает много функций, но часть функций похожа друг на друга. Поэтому весь набор делится на 4 варианта, а если объединить код четырех вариантов, то получится более-менее полноценный вектор.

Задание разрешается выполнять только на F# или Haskell. Шаблоны решений лежат в файлах Variant[1-4].[fh]s. Решения отправляйте по ссылке на Google Forms в чате.

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

Непосредственно перед отправкой проверьте, что код запускается при отправке в REPL:

• https://repl.it/languages/fsharp
• https://repl.it/languages/haskell

Если это не так, то решение не оценивается. Выгоднее закомментировать или удалить нереализованные части, а не пытаться в самом конце доделать одну функцию за 1-2 балла.

Прохождение тестов не гарантирует получение полного балла, поскольку тесты не покрывают возможные случаи и не оценивают асимптотику.

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

При грубых нарушениях код-стайла оценка за работу снижается на 10% — следуйте рекомендациям.

При списывании решения соучастников не оцениваются.

Заметки по реализации

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

• toIndexT — преобразует число в 32-элементный список логических констант. Ложное значение трактуется как поворот в дереве налево, истинное — направо. Эта функция уже реализована в шаблоне.

• insert — функция также реализована за вас. Сначала смотрим на индекс: если пустой список, то возвращаем лист с указанным элементом, так как это нижний уровень дерева, а для непустого списка: либо узел внутренний, и тогда в зависимости индекса повернуть налево или направо, либо это лист или пустое дереве — такой ситуации быть не должно, поэтому вставка невозможна, и возвращается дерево в неизменном виде.

• sizeT — количество листьев в префиксном дереве. При желании реализуйте функцию через хвостовую рекурсию. Это будет оцениваться в дополнительный балл за работу в семестре, так как на семинаре хвостовую рекурсию разобрали некорректно. Для вдохновения пройдите по ссылке на Stack Overflow.

• remove и updateT — как и для вставки, если при разборе индекса дерева попадаем в вершину неправильного типа, то дерево оставляем неизменным. Для вдохновения используйте функцию insertT.

• foldLeftT и foldLeftV — обратите внимание на левую свертку в Haskell.

• dropBefore и dropAfter — как следует из названия, требуется удалить вершины слева и справа. В обоих случаях сама вершина по этому индексу остается.

• tailV и initV — удаление первого или последнего элемента вектора. На пустом векторе ошибки не происходит: возвращается пустой вектор.

• dropV, takeV, takeRight и dropRight — не бросают ошибок на отрицательных количествах или когда отбрасывается или запрашивается больше элементов, чем размер вектора.

Остальные функции не требуют комментариев: на вопросы помогут ответить тесты.

Реальность

В жизни векторы устроены намного сложнее. В Scala вектор строится не на базе двоичного дерева, а на базе 32-ичного: дерево содержит либо до 32-х поддеревьев, либо массив, который содержит до 32-х элементов.

Это усложняет отображение индекса на путь в дереве, но улучшает производительность: двоичный логарифм заменяется на 32-ичный. Для описания 32-х значений нужно 5 знаков, а значит, для 32-битного индекса потребуется 7 уровней: 32 = 5 + 5 + 5 + 5 + 5 + 5 + 2. Таким образом, чтобы получить элемент вектора из 1000000000 элементов требуется до 7 операций — и это несмотря на древесную природу вектора. Говорят, что операции с вектором работают за «фактически константное» время.

Кроме того, хранить в листьях не отдельные элементы, а массивы — оптимизация количества промахов по кешу из-за локальности памяти.

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

Похожие векторы используются в языках Scala и Clojure. Принятого названия для этой структуры данных пока нет: встречаются имена bitmapped vector trie, bit-partitioned vector trie, digit-partitioned vector trie и так далее.

Полезные ссылки:

• серия статей ‘Understanding Clojure's Persistent Vectors’;
• доклад ‘Extreme Cleverness: Functional Data Structures in Scala’.