Персистентность: старая версия остаётся живой

Если ты знаешь, чем персистентная структура отличается от эфемерной, что такое частичная и полная персистентность и почему стек из неизменяемых узлов персистентен бесплатно, листай до «Теперь сам».

Как думаешь, что окажется в истории

Хотели сохранить историю корзины: в цикле по товарам «хлеб», «сыр», «чай» делаем korzina.append(tovar), а потом istoriya.append(korzina) - снимок после каждого товара. Что окажется в istoriya после цикла?

Ответь себе до чтения. Если «['хлеб'], ['хлеб', 'сыр'], ['хлеб', 'сыр', 'чай']» - разбор покажет три одинаковых списка. В истории лежат три ссылки на одну и ту же корзину, а она менялась на месте.

На что это похоже

Черновик в тетради, где ты стираешь ластиком и пишешь поверх, - эфемерная структура: прошлого текста больше нет. История правок в git - персистентная: каждый коммит - версия, к любой можно вернуться, от любой можно отпочковать ветку. И git не копирует весь проект на каждый коммит: неизменившиеся файлы новая версия берёт у старой.

Механизм: неизменяемые узлы и общие части

Персистентность строят не копированием, а неизменяемостью: узел, однажды созданный, не меняется никогда. Тогда его можно смело делить между версиями - никто не испортит его под другой версией.

Стек на неизменяемых узлах [значение, следующий]:

• положить x на версию v - создать один узел [x, v], он и есть новая вершина;
• снять с версии v - взять её «следующий»: новых узлов нет вовсе;
• версия - это просто номер вершины. Две версии с одной вершиной (как 2 и 4 ниже) - одно и то же содержимое; номер в списке версий - лишь место в истории.

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

Классификация Дрисколла, Сарнака, Слейтора и Тарьяна (1989): частичная персистентность - читать любые версии, менять последнюю (история правок); полная - менять любую (ветки); слияемая - вдобавок соединять две версии в одну (слияние веток в git; для списков - например, склейка двух версий в одну последовательность).

Правило

Персистентная структура: операция возвращает новую версию, старые остаются доступны. Основа - неизменяемые узлы и общие части между версиями. Частичная персистентность - менять последнюю версию, полная - любую, слияемая - ещё и соединять версии. Стек на неизменяемых узлах полностью персистентен бесплатно: O(1) на операцию и O(1) памяти на «положить».

Разбор: корзина эфемерно и персистентно

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

# эфемерный список: «старая версия» - та же самая ссылка
istoriya = []
korzina = []
for tovar in ["хлеб", "сыр", "чай"]:
    korzina.append(tovar)
    istoriya.append(korzina)
for snimok in istoriya:
    print("эфемерно:", snimok)

# персистентный стек: узел [значение, следующий], узлы не меняются
znach = []
dalshe = []

def polozhit(verh, x):
    znach.append(x)
    dalshe.append(verh)
    return len(znach) - 1            # номер нового узла - новая вершина

def soderzhimoe(verh):
    out = []
    while verh != -1:
        out.append(znach[verh])
        verh = dalshe[verh]
    return out

versii = [-1]                        # -1 - пустой стек
for tovar in ["хлеб", "сыр", "чай"]:
    versii.append(polozhit(versii[-1], tovar))
versii.append(dalshe[versii[-1]])    # снять «чай»: просто шаг назад
versii.append(polozhit(versii[2], "кофе"))   # ветка от версии 2
for i in range(len(versii)):
    print("версия", i, soderzhimoe(versii[i]))
print("узлов создано:", len(znach))

эфемерно: ['хлеб', 'сыр', 'чай']
эфемерно: ['хлеб', 'сыр', 'чай']
эфемерно: ['хлеб', 'сыр', 'чай']
версия 0 []
версия 1 ['хлеб']
версия 2 ['сыр', 'хлеб']
версия 3 ['чай', 'сыр', 'хлеб']
версия 4 ['сыр', 'хлеб']
версия 5 ['кофе', 'сыр', 'хлеб']
узлов создано: 4

Эфемерно - три ссылки на одну корзину, все показывают последнее состояние. Персистентно - шесть версий, каждая своя, и всего четыре узла: «снять» не создало ничего, «кофе» на версию 2 - один узел. Версии 3 и 5 - две ветки от общего ствола «сыр, хлеб». Стек печатается от вершины, поэтому последний положенный товар стоит первым.

Разбор: сколько стоит общая память

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

import random

znach = []
dalshe = []
dlina = []                           # длина стека от этого узла вниз

def polozhit(verh, x):
    znach.append(x)
    dalshe.append(verh)
    if verh == -1:
        dlina.append(1)
    else:
        dlina.append(dlina[verh] + 1)
    return len(znach) - 1

random.seed(8)              # то же зерно - те же числа в Python и движке
versii = [-1]
kopij = 0                            # сколько стоило бы копировать стек
for shag in range(2000):
    otkuda = versii[-1]              # обычно - от последней версии
    if random.random() < 0.1:        # иногда - от любой старой
        otkuda = versii[random.randint(0, len(versii) - 1)]
    if otkuda != -1 and random.random() < 0.3:
        versii.append(dalshe[otkuda])            # снять
        kopij = kopij + dlina[otkuda] - 1        # копия без вершины
    else:
        versii.append(polozhit(otkuda, shag))    # положить
        if otkuda != -1:
            kopij = kopij + dlina[otkuda]
        kopij = kopij + 1
samaya = 0
for v in versii:
    if v != -1 and dlina[v] > samaya:
        samaya = dlina[v]
print("версий:", len(versii), "узлов:", len(znach))
print("самая длинная версия:", samaya)
print("копирование целиком стоило бы элементов:", kopij)

версий: 2001 узлов: 1416
самая длинная версия: 66
копирование целиком стоило бы элементов: 55421

Узлов - ровно столько, сколько было операций «положить», 1416. Копирование каждой версии целиком - 55 421 элемент, в 39 раз больше, и разрыв растёт с длиной стека: копия стоит O(n), узел - O(1). Граница правила «персистентность бесплатна»: бесплатна она для стека, где меняется только вершина. Очередь, где меняются оба конца, и дерево, где меняется середина, так просто не даются - им посвящены следующие уроки.

Что ломается без этого

История из ссылок. istoriya.append(korzina) хранит ссылку, а не снимок; так же ломаются «кеш предыдущего состояния», «отмена последнего действия» и любые снимки изменяемого объекта.

Глубокая копия на каждый шаг. Лечение copy.deepcopy(korzina) работает, но стоит O(n) на шаг и O(n) памяти на версию: на длинных историях - квадрат.

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

Зачем это в работе

Отмена и повтор в редакторах, ветки в git, снимки файловых систем (btrfs, ZFS), версии строк в базах данных (MVCC: читатель видит снимок на момент начала транзакции или запроса - смотря по уровню изоляции, пока писатель создаёт новую версию), состояние интерфейса в React и Redux, коллекции Clojure, Scala, Haskell. Ещё один бонус - потоки: неизменяемую версию можно отдать любому числу читателей без замков, её никто не поменяет.

Теперь сам

1. Стек-версия v содержит [3, 2, 1] (3 - вершина). Сколько новых узлов создадут операции «положить 4 на v», «снять с v», «положить 5 на результат снятия»?
2. Чем частичная персистентность отличается от полной?
3. Почему кортеж Python неизменяем, но список кортежей - не персистентная структура?