Признаюсь. Я не очень любил курс структур данных и алгоритмов в университете. Все эти стеки, очереди, кучи, деревья, графы (будь они не ладны) и прочие “остроумные” названия непонятных и сложных структур данных ни как не хотели закрепляться в моей голове. Как истинный “прагматик”, я уже на втором — третьем курсе свято верил в стандартную библиотеку классов и молился на дарованные нам (простым смертным) коллекции и контейнеры, бережно реализованные отцами и благородными донами CS. Казалось, все что можно было придумать — уже давно придумано и реализовано.
Все изменилось примерно год назад, когда я узнал, что есть другой мир. Мир отличный от нашего с вами. Более чистый и предсказуемый мир. Мир без побочных эффектов, мутаций, массивов и деструктивных апдейтов (переприсваиваний в переменную). Мир, где всем правит мудрейшая королева персистетность и ее прекрасные сестры — функция и рекурсия. Я говорю о чисто функциональном мире, где гармонично существуют, или даже живут, проекции почти всех известных нам структур данных.
И сейчас, я хочу показать вам небольшую частицу этого мира. Через замочную скважину, мы на секунду заглянем в этот удивительный мир, чтобы рассмотреть одного из наиболее ярких его обитателей — функциональное красно-черное дерево (КЧД).
О чисто функциональных структурах данных
Чисто функциональные структуры данных (ЧФСД) как класс существуют по двум причинам. Во-первых, для 99% императивных реализаций, камнем преткновения являются так называемые деструктивные апдейты (присваивание в переменную с потерей предыдущего значения). Понятно, что такой сценарий в функциональном мире невозможен, потому как мы всегда имеем дело с неизменяемыми объектами (immutable objects). Во вторых, в функциональном мире, после изменения коллекции мы ожидаем, что ее предыдущая версия нам остается доступной. Отсюда термин “персистетность” (persistent object) — поддержка множества версий объекта.
Таким образом, нельзя просто взять и портировать известную императивную реализацию в функциональный мир. Необходимо помнить о его ограничениях (нет апдейтов) и требованиях (персистентность). Поэтому, процесс адаптации императивной реализации к функциональной среде — несколько более сложный и даже таинственный. И непревзойденным мастером в этом нелегком деле вот уже 15 лет считается Крис Окасаки со своим фундаментальным трудом — Purely Functional Data Structures.
О Крисе и его книге
В 1998 году Крис защитил диссертацию на тему ЧФСД и год спустя издал тезисы в виде книги. Книга Криса — это 200 страниц очень плотного (по информативности) и увлекательнейшего чтива. Текст, стиль которого граничит между научной работой и неформальным разговором с другом в баре, буквально читается как художественный роман. Труд Криса объединяет в себе лучшие практики и подходы в реализации ЧФСД, подкрепленные примерами широко известных (и не очень) структур данных на языках Standard ML и Haskell.
О двух ключах
Внимательный читатель скажет, что с такими требованиями и ограничениями все будет жутко тормозить. Создается впечатление, что любое изменение функциональной коллекции сопровождается ее полными копированием, дабы поддержать персистетность. Это не совсем так. Точнее — совсем не так. Копирование действительно присутствует, но в самых минимальных масштабах. Более формально — копируется только то, что действительно меняется. Остальная часть коллекции (как привило бОльшая) — расшаривается между версиями. Эти два предложения — ключи к пониманию чисто функциональных структур данных. Это уникальные инструменты, которые придуманы и отточены острейшими умами ФП. Имя этим инструментам — path copying (копирование только того, что затрагивается в операции) и structural sharing (общие части можно безопасно расшаривать между версиями, так как каждая такая часть сама является неизменяемой).
О деревьях бинарного поиска
Для начала рассмотрим обычные несбалансированные деревья бинарного поиска (ДБП), которые очень просто портируются в функциональный мир. Структура их выглядит так:
abstract sealed class Tree {
def value: Int
def left: Tree
def right: Tree
def isEmpty: Boolean
}
case object Leaf extends Tree {
def value: Int = fail("Empty tree.")
def left: Tree = fail("Empty tree.")
def right: Tree = fail("Empty tree.")
def isEmpty: Boolean = true
}
case class Branch(value: Int, left: Tree = Leaf, right: Tree = Leaf) extends Tree {
def isEmpty: Boolean = false
}
Нас интересует операция вставки, которая позволит нам сполна оценить силу и красоту инструментов path copying и structural sharing.
def add(x: Int): Tree =
if (isEmpty) Branch(x)
else if (x < value) Branch(value, left.add(x), right)
else if (x > value) Branch(value, left, right.add(x))
else this
Как и в императивном алгоритме, задача вставки сводится к задаче поиска подходящего места для нового узла. Однако, наша функциональная реализация будет слегка интереснее. Операция вставки в функциональное дерево объединяет два прохода — нисходящая (top-down) цепочка вызовов add (поиск места для вставки) и восходящая (bottom-up) цепочка вызовов конструктора Branch (копирование измененной части дерева вдоль search path). Первый проход (нисходящий поиск места вставки) является очевидной проекцией императивного алгоритма. Нас же интересует второй проход (восходящий path copying), который и делает нашу реализацию полностью функциональной (персистентной).
Для сохранения свойства персистетности, необходимо поддерживать две версии коллекции — “до” и “после” вставки. Поэтому, любые изменения внутренней структуры узлов должны осуществляться над их копиями. В результате вставки в дерево, возникает своего рода “цепная реакция” обновления узлов (изменение ссылок на левого/правого потомка), распространяющаяся вдоль search path от места вставки к корню дерева. Именно так можно описать ту “магию”, которую реализует восходящий проход, объединяя в себе идеи и path copying (узлы «5» и «7» скопированы) и structural sharing (поддерево с ключами «1», «2», «3» содержится в обоих версиях коллекции).
О красно-черных деревьях
Красно-черное дерево (КЧД) — это самобалансирующееся дерево бинарного поиска для которого справедливы два инварианта:
- Красный инвариант: никакой красный узел не имеет красного предка
- Черный инвариант: каждый путь из корня в лист имеет одинаковое количество черных узлов
Выполнение этих инвариантов гарантирует, что дерево будет сбалансированным с высотой log n, где n — количество узлов в дереве. Другими словами, основные операции над КЧД гарантированно выполняются за логарифмическое время.
До 1999 года о КЧД в функциональном мире не было и речи. Императивная реализация имела дурную славу трудно портируемой, так как была полностью построена на сложных манипуляциях с указателями (pointers hell). Так, например, в Кормене рассмотрено восемь возможных случаев нарушения инвариантов и соответствующие меры по их устранению. Слегка отклоняясь от темы, можно добавить что именно из-за излишней сложности КЧД всячески старались заменить альтернативными вещами. Например, Седжевик предложил LLRB дерево в качестве упрощенной версии КЧД.
Тем не менее, в 1999 Крис Окасаки опубликовал статью, в которой представил чисто функциональную реализацию КЧД. Эта статья до сих пор пользуется большим спросом как среди функциональных программистов так и императивных. Дело в том, что в статье представлена очень простая и понятная идея реализации, которую любой программист сможет понять и запрограммировать за 15 минут. Крис сказал, что есть всего 4 паттерна (см. картинку ниже), которые нарушают один из инвариантов. И наша задача — найти эти паттерны и перестроить их в одну и туже конструкцию с красным корнем и двумя черными детьми (см. картинку). И это все. Т.е. для того, чтобы получить КЧД из ДБП нам достаточно изменить второй (восходящий) проход алгоритма вставки. Теперь второй проход должен не просто копировать узлы вдоль search path, но также в случае соответствия поддерева одному из четырех паттернов, перестраивать его в безопасную конструкцию. Другими словами, фаза копирования в алгоритме совмещается с фазой балансировки.
Добавляя к этому два простых факта о том что корень КЧД — всегда черный, а новый узел всегда красный, получаем следующий код:
def add(x: Int): Tree = {
def balancedAdd(t: Tree): Tree =
if (t.isEmpty) Tree.make(Red, x)
else if (x < t.value) balanceLeft(t.color, t.value, balancedAdd(t.left), t.right)
else if (x > t.value) balanceRight(t.color, t.value, t.left, balancedAdd(t.right))
else t
def balanceLeft(c: Color, x: Int, l: Tree, r: Tree) = (c, l, r) match {
case (Black, Branch(Red, y, Branch(Red, z, a, b), c), d) =>
Tree.make(Red, y, Tree.make(Black, z, a, b), Tree.make(Black, x, c, d))
case (Black, Branch(Red, z, a, Branch(Red, y, b, c)), d) =>
Tree.make(Red, y, Tree.make(Black, z, a, b), Tree.make(Black, x, c, d))
case _ => Tree.make(c, x, l, r)
}
def balanceRight(c: Color, x: A, l: Tree, r: Tree) = (c, l, r) match {
case (Black, a, Branch(Red, y, b, Branch(Red, z, c, d))) =>
Tree.make(Red, y, Tree.make(Black, x, a, b), Tree.make(Black, z, c, d))
case (Black, a, Branch(Red, z, Branch(Red, y, b, c), d)) =>
Tree.make(Red, y, Tree.make(Black, x, a, b), Tree.make(Black, z, c, d))
case _ => Tree.make(c, x, l, r)
}
def blacken(t: Tree) = Tree.make(Black, t.value, t.left, t.right)
blacken(balancedAdd(this))
}
В рассмотренной реализации есть еще пара моментов, которые требуют дополнительных комментариев. Во-первых, каждый узел дерева содержит дополнительную информацию — свой цвет (функция color). Во-вторых, функция balance, реализующая балансировку и копирование, разбита на две функции (пара balanceLeft и balanceRight), которые ожидают найти нарушение инвариантов в левом или правом поддереве (только вдоль search patch), и обрабатывают по два паттерна для каждой стороны соответственно.
О сложности императивной реализации
Возникает справедливый вопрос — почему реализация КЧД в императивном мире выглядит намного сложнее? Ответ достаточно простой — виной тому производительность. Имеея дело с указателями и изменяемыми переменнымии, мы можем остановить процесс балансировки на самых ранних его итерациях (при определенных условиях), тем самым сократив время работы алгоритма. В функциональной же среде, мы вынуждены копировать все затронутые узлы (affected nodes), поэтому лишние проверки наличия паттернов в поддеревьях нас не сильно смущают. Справедливости ради, стоит заменить, что предложенный алгоритм вставки в функциональное КЧД имеет такую-же асимптотическую сложность как и оригнальный алгоритм из императивного мира — О(log n).
О дальнейших шагах
Я собрал несколько отличных ссылок для тех, кто заинтересовался темой.
Для исследователей:
- Моя обзорная презентация ЧФСД с примерами на Scala (видео доклада для Новосибирской Scala встречи тут)
- Моя попытка портирования бинарной кучи в функциональный мир
- Код КЧД и других структур на GitHub
- Удаление из КЧД от Метта Майта
- Блог Криса Окасаки
Для практиков:
- Anre Andersonin в этой статье предложил сократить количество сравнений с «2 * d» на «d + 1», где d — глубина дерева (длина search path). Модифицируйте операцию вставки в ДБП так, чтобы она использовала меньшее количество сравнений.
- Напишите функцию
fromOrderedList, которая строит сбалансированное ДБП из отсортированного списка. Hint: Hinze, Ralf. 1999 «Constructing red-black trees».
Автор: spiff
