Подготовка к алгоритмическим задачам

Персистентные структуры данных: доступ ко всем прошлым версиям

9 мин чтения

структуры данных

деревья

python

Коротко

Тип персистентности	Что можно
Частичная	читать любую версию, менять только последнюю
Полная	читать и менять любую версию
Конфлюэнтная	ещё и сливать версии

Персистентная структура при изменении не портит себя, а возвращает новую версию. Старая остаётся доступной.

Зачем это нужно

Отмена действий. Каждое состояние редактора — отдельная версия. Undo — просто переход к предыдущей.

Системы контроля версий. Git по своей природе персистентен: коммит не изменяет историю, а надстраивает её.

Функциональные языки. В Haskell и Clojure все структуры неизменяемы, и персистентность там не опция, а основа.

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

Алгоритмические задачи. Запросы вида «какой был k-й элемент на отрезке в версии номер 5».

Наивный подход и почему он не работает

Простейший способ сделать структуру персистентной — копировать её целиком при каждом изменении.

versions = [[1, 2, 3]]

new = versions[-1][:]      # копия
new[1] = 99
versions.append(new)

Каждое изменение стоит O(n) времени и памяти. Тысяча изменений массива на миллион элементов — гигабайты. Неприемлемо.

Ключевая идея: путь копирования

Настоящее решение опирается на два наблюдения:

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

Если хранить данные в дереве, то изменение одного листа затрагивает только путь от корня до него — это O(log n) узлов. Все остальные поддеревья переиспользуются по ссылке.

версия 1:        A
                / \
               B   C
              / \
             D   E

меняем D → D'

версия 2:       A'          новые узлы: A', B', D'
                / \         переиспользованы: C, E
               B'  C ←──────── та же ссылка
              / \
             D'  E ←────────── та же ссылка

Создаётся log n новых узлов вместо n. Обе версии остаются полностью рабочими.

Персистентный массив

Реализуем массив как двоичное дерево, где листья — элементы.

class Node:
    __slots__ = ('left', 'right', 'value')

    def __init__(self, left=None, right=None, value=None):
        self.left = left
        self.right = right
        self.value = value


class PersistentArray:
    def __init__(self, values: list):
        self.n = len(values)
        self.root = self._build(values, 0, self.n - 1)

    def _build(self, values, lo, hi):
        if lo == hi:
            return Node(value=values[lo])
        mid = (lo + hi) // 2
        return Node(
            left=self._build(values, lo, mid),
            right=self._build(values, mid + 1, hi),
        )

    def get(self, root: Node, index: int):
        lo, hi = 0, self.n - 1
        node = root
        while lo != hi:
            mid = (lo + hi) // 2
            if index <= mid:
                node, hi = node.left, mid
            else:
                node, lo = node.right, mid + 1
        return node.value

    def set(self, root: Node, index: int, value) -> Node:
        """Возвращает КОРЕНЬ НОВОЙ версии, старая не тронута."""
        return self._set(root, 0, self.n - 1, index, value)

    def _set(self, node, lo, hi, index, value) -> Node:
        if lo == hi:
            return Node(value=value)       # новый лист

        mid = (lo + hi) // 2
        if index <= mid:
            # копируем только левый путь, правое поддерево переиспользуем
            return Node(left=self._set(node.left, lo, mid, index, value),
                        right=node.right)
        else:
            return Node(left=node.left,
                        right=self._set(node.right, mid + 1, hi, index, value))


pa = PersistentArray([1, 2, 3, 4])
v1 = pa.root
v2 = pa.set(v1, 1, 99)
v3 = pa.set(v2, 3, 77)

print([pa.get(v1, i) for i in range(4)])   # [1, 2, 3, 4]
print([pa.get(v2, i) for i in range(4)])   # [1, 99, 3, 4]
print([pa.get(v3, i) for i in range(4)])   # [1, 99, 3, 77]

Все три версии живы одновременно. Каждое изменение создало три новых узла вместо четырёх элементов — при большом массиве экономия становится радикальной.

Плата: доступ по индексу стал O(log n) вместо O(1). Это неизбежная цена персистентности на дереве.

Персистентное дерево отрезков

Самое частое применение в алгоритмических задачах. Позволяет отвечать на вопросы о состоянии массива в любой момент истории.

class SegNode:
    __slots__ = ('left', 'right', 'total')

    def __init__(self, left=None, right=None, total=0):
        self.left = left
        self.right = right
        self.total = total


def build(arr, lo, hi):
    if lo == hi:
        return SegNode(total=arr[lo])
    mid = (lo + hi) // 2
    left = build(arr, lo, mid)
    right = build(arr, mid + 1, hi)
    return SegNode(left, right, left.total + right.total)


def update(node, lo, hi, pos, value):
    if lo == hi:
        return SegNode(total=value)

    mid = (lo + hi) // 2
    if pos <= mid:
        left = update(node.left, lo, mid, pos, value)
        right = node.right
    else:
        left = node.left
        right = update(node.right, mid + 1, hi, pos, value)

    return SegNode(left, right, left.total + right.total)


def query(node, lo, hi, l, r) -> int:
    if r < lo or hi < l:
        return 0
    if l <= lo and hi <= r:
        return node.total
    mid = (lo + hi) // 2
    return (query(node.left, lo, mid, l, r)
            + query(node.right, mid + 1, hi, l, r))


arr = [1, 2, 3, 4, 5]
n = len(arr)
v0 = build(arr, 0, n - 1)
v1 = update(v0, 0, n - 1, 2, 100)

print(query(v0, 0, n - 1, 0, 4))   # 15 — исходная версия
print(query(v1, 0, n - 1, 0, 4))   # 112 — после изменения

На этой конструкции решается классическая задача: k-я порядковая статистика на отрезке. Строим версию дерева для каждого префикса массива, а запрос на отрезке [l, r] получаем вычитанием версии l-1 из версии r.

Персистентность в реальных языках

Clojure — все коллекции персистентны по умолчанию. Внутри используется HAMT (hash array mapped trie) с ветвлением 32, что делает глубину дерева практически константной.

Scala — неизменяемые коллекции в стандартной библиотеке.

Immer, Immutable.js — библиотеки для JavaScript, широко применяются с Redux, где неизменяемость состояния — архитектурное требование.

Git — дерево объектов, где коммит ссылается на переиспользуемые деревья и блобы.

Общий приём везде один: структурное разделение неизменяемых частей.

Ограничения

Память растёт. Каждая версия добавляет O(log n) узлов. Тысяча изменений массива на миллион элементов — около 20 тысяч узлов, это приемлемо. Но версии накапливаются, и старые нужно уметь отпускать.

Константа больше. Персистентная структура всегда медленнее изменяемой по константе: аллокации, косвенность, нагрузка на сборщик мусора.

Не всё легко сделать персистентным. Хеш-таблицу — сложно (нужен HAMT), массив с O(1) доступом — невозможно без потерь.

Частые ошибки

Изменение старых узлов. Ломает все версии, которые их переиспользуют. Узлы должны быть неизменяемыми строго.

Копирование поддерева вместо ссылки. Убивает всю экономию, возвращая O(n) на изменение.

Хранение всех версий без нужды. Если старые версии не используются, они всё равно занимают память. Освобождайте ссылки.

Ожидание O(1) доступа. Персистентный массив на дереве даёт O(log n) — это цена, а не недоработка.

Что запомнить

Персистентная структура при изменении создаёт новую версию, не портя старую.
Приём «путь копирования»: копируются только узлы на пути от корня, остальное переиспользуется по ссылке.
Одно изменение стоит O(log n) памяти вместо O(n).
Основа undo, систем контроля версий, функциональных языков и запросов «к состоянию в прошлом».
Узлы обязаны быть неизменяемыми — иначе рушатся все версии сразу.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→