3.3 Рекурсивные структуры данных

В предыдущей главе мы ввели понятие пары, как механизм объединения двух объектов в один. Мы показали, что пары могут быть реализованы с использованием встроенных элементов. Замкнутость пар показывает, что каждый элемент пары сам по себе может быть парой.

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

3.3.1 Обработка рекурсивного списка

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

>>> class Rlist(object):
        """A recursive list consisting of a first element and the rest."""
        class EmptyList(object):
            def __len__(self):
                return 0
        empty = EmptyList()
        def __init__(self, first, rest=empty):
            self.first = first
            self.rest = rest
        def __repr__(self):
            args = repr(self.first)
            if self.rest is not Rlist.empty:
                args += ', {0}'.format(repr(self.rest))
            return 'Rlist({0})'.format(args)
        def __len__(self):
            return 1 + len(self.rest)
        def __getitem__(self, i):
            if i == 0:
                return self.first
            return self.rest[i-1]

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

>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.rest
Rlist(2, Rlist(3))
>>> len(s)
3
>>> s[1]
2

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

>>> def extend_rlist(s1, s2):
        if s1 is Rlist.empty:
            return s2
        return Rlist(s1.first, extend_rlist(s1.rest, s2))
>>> extend_rlist(s.rest, s)
Rlist(2, Rlist(3, Rlist(1, Rlist(2, Rlist(3)))))

Аналогично, отображение функции на рекурсивном списке демонстрирует аналогичный шаблон:

>>> def map_rlist(s, fn):
        if s is Rlist.empty:
            return s
        return Rlist(fn(s.first), map_rlist(s.rest, fn))
>>> map_rlist(s, square)
Rlist(1, Rlist(4, Rlist(9)))

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

>>> def filter_rlist(s, fn):
        if s is Rlist.empty:
            return s
        rest = filter_rlist(s.rest, fn)
        if fn(s.first):
            return Rlist(s.first, rest)
        return rest
>>> filter_rlist(s, lambda x: x % 2 == 1)
Rlist(1, Rlist(3))

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

3.3.2 Иерархическая структура

Иерархические структуры возникают из-за замкнутости данных, например, кортежи могут содержать другие кортежи. Рассмотрим представление чисел от 1 до 4 вложенным способом.

>>> ((1, 2), 3, 4)
((1, 2), 3, 4)

Этот кортеж представляет собой последовательность длиной 3, первый элемент которой также является кортежем. Диаграмма с изображением коробок и указателей показывает эту вложенную структуру, показывая, что она может рассматриваться как дерево с четырьмя листьями, каждый лист представляет собой число.

В дереве каждый поддерево само по себе является деревом. Как базовое условие, любой элемент, который не является самим кортежем, является простым деревом без каких-либо ветвей. То есть все числа являются деревьями, как в случае с (1, 2) и всей структурой.

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

>>> t = ((1, 2), 3, 4)
>>> count_leaves(t)
4
>>> big_tree = ((t, t), 5)
>>> big_tree
((((1, 2), 3, 4), ((1, 2), 3, 4)), 5)
>>> count_leaves(big_tree)
9

Подобно тому, как map является мощным инструментом для обработки последовательностей, сопоставление и рекурсия вместе обеспечивают мощный и универсальный вычислительный подход для операций с деревьями. Например, мы можем использовать высокоуровневую рекурсивную функцию map_tree для возведения в квадрат каждого листа дерева, её структура похожа на count_leaves.

>>> def map_tree(tree, fn):
        if type(tree) != tuple:
            return fn(tree)
        return tuple(map_tree(branch, fn) for branch in tree)
>>> map_tree(big_tree, square)
((((1, 4), 9, 16), ((1, 4), 9, 16)), 25) ```
represents a recursive Fibonacci calculation.

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

3.3.3 Множества

Помимо списков, кортежей и словарей, Python имеет четвёртый тип контейнера, называемый set. Литералы множеств следуют математическому представлению элементов, заключённых в фигурные скобки. Повторяющиеся элементы удаляются при построении. Множество является неупорядоченным контейнером, поэтому распечатанный порядок может отличаться от порядка элементов в литерале множества.

>>> s = {3, 2, 1, 4, 4}
>>> s
{1, 2, 3, 4}

Множества Python поддерживают различные операции, включая проверку принадлежности элемента, вычисление длины и стандартные операции пересечения и объединения множеств.

>>> 3 in s
True
>>> len(s)
4
>>> s.union({1, 5})
{1, 2, 3, 4, 5}
>>> s.intersection({6, 5, 4, 3})
{3, 4}

В дополнение к union и intersection, множества Python также поддерживают множество других операций. Утверждения isdisjoint, issubset и issuperset предоставляют операции сравнения множеств. Множество изменчиво, и вы можете использовать add, remove, discard и pop для изменения одного элемента за раз. Дополнительные методы обеспечивают изменение нескольких элементов, например clear и update. Документация по множествам Python (http://docs.python.org/py3k/library/stdtypes.html#set) очень подробна и достаточно проста для понимания.

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

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

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

>>> def empty(s):
        return s is Rlist.empty
>>> def set_contains(s, v):
        """Return True if and only if set s contains v."""
        if empty(s):
            return False
        elif s.first == v:
            return True
        return set_contains(s.rest, v)
>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> set_contains(s, 2)
True
>>> set_contains(s, 5)
False

Эта реализация set_contains требует времени Θ(n) для проверки принадлежности элемента, где n — размер множества s. Используя эту линейную функцию времени проверки принадлежности, мы также можем добавлять элементы во множество линейным временем.

>>> def adjoin_set(s, v):
        """Return a set containing all elements of s and element v."""
        if set_contains(s, v):
            return s
        return Rlist(v, s)
>>> t = adjoin_set(s, 4)
>>> t
Rlist(4, Rlist(1, Rlist(2, Rlist(3))))

Теперь возникает вопрос: должны ли мы сосредоточиться на эффективности при проектировании представления? Вычисление пересечения двух множеств set1 и set2 требует проверки принадлежности каждого элемента set1, но на этот раз каждый элемент set1 должен быть проверен на принадлежность set2, что приводит к квадратичному росту длины Θ(n^2) для двух множеств размера n.

>>> def intersect_set(set1, set2):
        """Return a set containing all elements common to set1 and set2."""
        return filter_rlist(set1, lambda v: set_contains(set2, v))
>>> intersect_set(t, map_rlist(s, square))
Rlist(4, Rlist(1))

При вычислении объединения двух множеств мы должны быть осторожны, чтобы не включать один и тот же элемент дважды. Функция union_set также требует линейного количества проверок принадлежности и также приведёт к процессу, включающему Θ(n^2) шагов.

>>> def union_set(set1, set2):
        """Return a set containing all elements either in set1 or set2."""
        set1_not_set2 = filter_rlist(set1, lambda v: not set_contains(set2, v))
        return extend_rlist(set1_not_set2, set2)
>>> union_set(t, s)
Rlist(4, Rlist(1, Rlist(2, Rlist(3))))

Множество как упорядоченный кортеж. Одним из способов ускорить наши операции над множествами является изменение представления таким образом, чтобы элементы множества были расположены в порядке возрастания. Для этого нам нужны некоторые средства сравнения двух объектов, чтобы мы могли определить, какой из них больше. В Python многие типы объектов могут сравниваться с использованием операторов < и >, но мы сосредоточимся на примере с числовыми значениями. Мы будем представлять числовые множества, располагая элементы в порядке возрастания.

Преимущество упорядочивания проявляется в set_contains: при проверке существования объекта нам больше не нужно перебирать всё множество. Если мы достигли элемента в множестве, который больше искомого элемента, мы знаем, что этот элемент не принадлежит множеству:

>>> def set_contains(s, v):
        if empty(s) or s.first > v:
            return False
        elif s.first == v:
            return True
        return set_contains(s.rest, v)
>>> set_contains(s, 0)
False

Сколько шагов это экономит? В худшем случае искомый элемент может быть самым большим элементом в множестве, так что количество шагов такое же, как и в неупорядоченном представлении. С другой стороны, если мы ищем много разных элементов разного размера, мы можем ожидать, что иногда мы сможем остановить поиск в начале списка, а в других случаях нам всё равно придётся проверять весь список. В среднем мы должны ожидать проверки половины элементов множества. Поэтому среднее количество шагов должно быть n/2. Это всё ещё Θ(n), но это действительно сэкономит нам половину количества шагов по сравнению с предыдущей реализацией.

Мы можем добиться более заметного улучшения скорости, повторно реализовав intersect_set. В неупорядоченном представлении эта операция требует Θ(n^2) шагов, потому что мы проверяем каждый элемент set1 на всём set2. Но используя упорядоченное представление, мы можем использовать более умный подход. Мы одновременно перебираем два множества и отслеживаем элемент e1 в set1 и элемент e2 в set2. Когда e1 и e2 равны, мы добавляем этот элемент в пересечение.

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

>>> def intersect_set(set1, set2):
        if empty(set1) or empty(set2):
            return Rlist.empty
        e1, e2 = set1.first, set2.first
        if e1 == e2:
            return Rlist(e1, intersect_set(set1.rest,
                                           set2.rest))
        elif e1 < e2:
            return intersect_set(set1.rest, set2)
        else:
            return intersect_set(set1, set2.rest) **Текст запроса:**

set2.rest)) elif e1 < e2: return intersect_set(set1.rest, set2) elif e2 < e1: return intersect_set(set1, set2.rest)

intersect_set(s, s.rest) Rlist(2, Rlist(3))

**Перевод:**

Для оценки количества шагов, необходимых для этого процесса, заметим, что на каждом шаге мы уменьшаем размер хотя бы одного из множеств. Поэтому количество шагов не превышает суммы размеров множеств $set1$ и $set2$, а не произведения их размеров, как было бы при неупорядоченном представлении. Это даёт рост $Θ(n)$, а не $Θ(n^2)$ — даже если размеры множеств средние, это значительное ускорение. Например, пересечение двух множеств размером 100 требует 200 шагов, а не 10 000 при неупорядоченном представлении.

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

* *В качестве бинарного дерева.* Мы можем улучшить представление с помощью упорядоченного списка, перегруппировав несколько элементов в древовидную структуру. Используем ранее введённый класс $Tree$. Корень дерева содержит элемент множества. Элементы левого поддерева включают все элементы, меньшие, чем элемент корня. Элементы правого поддерева включают все элементы, большие, чем элемент корня. На следующих рисунках показаны деревья, представляющие множество {1, 3, 5, 7, 9, 11}. Одно и то же множество может быть представлено разными деревьями. Единственное условие для эффективного представления — все левые поддеревья должны содержать элементы, меньшие элемента корня, а все правые поддеревья — элементы, большие элемента корня.

![](img/set_trees.png)

Преимущество древовидного представления заключается в том, что если мы хотим проверить, содержится ли элемент $v$ во множестве, мы начинаем с сравнения $v$ с элементом корня. Если $v$ меньше него, мы знаем, что нам нужно искать только в левом поддереве. Если $v$ больше него, нам нужно искать только в правом поддереве. Теперь, если дерево «сбалансировано», каждое из этих поддеревьев примерно вдвое меньше всего дерева. Таким образом, на каждом этапе мы можем уменьшить размер задачи поиска в дереве размера $n$ до поиска в поддереве размера $n/2$. Поскольку размер дерева уменьшается вдвое на каждом шаге, можно ожидать, что поиск по дереву будет иметь сложность $Θ(log n)$. По сравнению с предыдущим представлением, скорость значительно выше для больших множеств. Функция $set_contains$ использует упорядоченную структуру древовидных множеств:

```py
>>> def set_contains(s, v):
        if s is None:
            return False
        elif s.entry == v:
            return True
        elif s.entry < v:
            return set_contains(s.right, v)
        elif s.entry > v:
            return set_contain(s.left, v)

Добавление элементов во множество аналогично и также имеет сложность $Θ(log n)$. Чтобы добавить значение $v$, мы сравниваем его с элементом $entry$, чтобы определить, следует ли добавить его в правое или левое поддерево, и добавили ли мы уже $v$ в подходящее поддерево. Мы объединяем новое поддерево с исходным элементом $entry$ и другими поддеревьями. Если $v$ равен элементу $entry$, мы можем вернуть этот узел. Если нас просят добавить $v$ к пустому дереву, мы создаём дерево, содержащее $v$ как элемент $entry$, а левое и правое поддеревья являются пустыми. Вот эта функция:

>>> def adjoin_set(s, v):
        if s is None:
            return Tree(v)
        if s.entry == v:
            return s
        if s.entry < v:
            return Tree(s.entry, s.left, adjoin_set(s.right, v))
        if s.entry > v:
            return Tree(s.entry, adjoin_set(s.left, v), s.right)

>>> adjoin_set(adjoin_set(adjoin_set(None, 2), 3), 1)
Tree(2, Tree(1), Tree(3))

Поиск по этому дереву можно выполнить за логарифмическое число шагов, но наше утверждение основано на предположении, что дерево «сбалансированное». То есть левое и правое поддеревья содержат одинаковое количество соответствующих элементов, так что каждое поддерево содержит половину элементов родительского дерева. Но как мы узнаем, что построенное нами дерево сбалансировано? Даже если мы начнём со сбалансированного дерева, добавление элементов с помощью $adjoin_set$ может привести к несбалансированному результату. Поскольку новое местоположение добавленного элемента зависит от того, как он сравнивается с существующими элементами множества, мы можем предсказать, что при «случайном» добавлении элементов дерево в среднем будет стремиться к сбалансированности.

Однако это не гарантировано. Например, если мы начнем с пустого множества и добавим элементы от 1 до 7, в итоге мы получим очень несбалансированное дерево, где все левые поддеревья пусты, поэтому оно не имеет преимущества перед простым упорядоченным списком. Один из способов решить эту проблему — определить операцию, которая преобразует любое дерево в сбалансированное дерево с теми же элементами. Мы можем выполнять это преобразование после каждой операции $adjoin_set$, чтобы гарантировать, что наше множество сбалансировано.

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

Реализация множеств в Python. Встроенное множество Python не использует ни одно из описанных представлений. Вместо этого Python использует реализацию, в которой проверка принадлежности и добавление элементов занимают (приблизительно) постоянное время, основанное на механизме, называемом хешированием. Встроенные множества Python не могут содержать изменяемые типы данных, такие как списки, словари или другие множества. Для возможности вложения множеств Python также предоставляет встроенный неизменяемый класс $frozenset$, который имеет те же методы, что и множество $set$, за исключением изменяющих операций и операторов.