Що таке persistent data structures

У Computer Science термін «Persistent Data Structure» (Персистентна структура даних) НЕ має жодного стосунку до запису даних на диск чи в базу даних (це називається Data Persist...

🟢 Junior Level

30-секундна відповідь

У Computer Science термін «Persistent Data Structure» (Персистентна структура даних) НЕ має жодного стосунку до запису даних на диск чи в базу даних (це називається Data Persistence).

Персистентна структура даних — це незмінна (ім’ютабельна) структура в оперативній пам’яті, яка при будь-яких операціях модифікації (додавання, видалення, оновлення) завжди зберігає всі свої попередні версії доступними для читання.

Під час зміни створюється нова версія структури, при цьому:

Стара версія залишається на 100% недоторканою.
Нова версія перевикористовує переважну більшість пам’яті старої версії завдяки принципу структурного розділення (Structural Sharing).

Наочна аналогія з життя: Git

Уявіть систему контролю версій Git:

Коли ви фіксуєте новий коміт, змінивши один рядок у файлі, Git не копіює заново весь репозиторій на 10 гігабайтів.
Git створює об’єкт нового коміту і повторно використовує незмінені дерева та файли з попередніх комітів.
Ви можете в будь-який момент перемкнутися на старий коміт або працювати з новим паралельно.

Наочний приклад (на бібліотеці Vavr)

// Персистентний список із бібліотеки Vavr:
io.vavr.collection.List<String> v1 = io.vavr.collection.List.of("B", "C");

// "Додаємо" елемент на початок:
io.vavr.collection.List<String> v2 = v1.prepend("A");

System.out.println(v1); // List("B", "C")      <-- Стара версія не змінилася!
System.out.println(v2); // List("A", "B", "C") <-- Нова версія перевикористовує v1

🟡 Middle Level

Наївна незмінність (наприклад, new ArrayList<>(oldList) або List.copyOf()) при додаванні одного елемента змушена повністю копіювати масив за $O(N)$ за часом та пам’яттю.

Персистентні структури даних вирішують цю проблему через Structural Sharing:

1. Персистентний зв’язний список (Singly Linked List)

Версія 1 (v1):                    [Node "B"] ──► [Node "C"] ──► null
                                        ▲
                                        │ (Спільний хвіст)
Версія 2 (v2 = v1.prepend("A")):  [Node "A"] ──┘

Операція prepend виконується за $O(1)$ за часом і виділяє пам’ять рівно під один новий вузол Node "A".
Вузли "B" і "C" безпечно розділяються між обома версіями в пам’яті купи (Heap).

2. Персистентні дерева: Копіювання шляху (Path Copying)

При модифікації вузла у збалансованому дереві створюються копії лише тих вузлів, які лежать на шляху від кореня до цільового листка ($O(\log N)$ вузлів). Усі інші піддерева (до 99% дерева) залишаються спільними:

Старий корінь (Root v1) ──► [Left Subtree (Спільне)]    [Node B (Старий)]
                                                              ▲
                                                              │
Новий корінь (Root v2)  ──► [Left Subtree (Спільне)]    [Node B (Новий)] ──► [New Leaf]

Класифікація персистентності в Computer Science

Частково персистентні (Partially Persistent): можна читати будь-які минулі версії, але модифікувати дозволено лише найостаннішу версію (лінійна історія).
Повністю персистентні (Fully Persistent): будь-яку версію з минулого можна модифікувати, створюючи розгалуження історії версій (дерево версій, як гілки в Git).
Конфлуентно персистентні (Confluently Persistent): підтримують злиття двох різних версій в одну (аналог git merge).

Різниця між колекціями JDK та Vavr

🔴 Senior Level

HAMT (Hash Array Mapped Trie) — Стандарт функціональних структур

У бібліотеках Vavr (Java), Clojure та Scala персистентні Map і Set реалізовані на базі структури HAMT (Hash Array Mapped Trie):

32-кове префіксне дерево (32-way Branching):
- 32-бітний hashCode() ключа розбивається на фрагменти по 5 бітів ($2^5 = 32$).
- Кожен рівень дерева відповідає за свої 5 бітів хешу.
- Максимальна глибина дерева для 4 мільярдів елементів становить лише $\lceil 32 / 5 \rceil = 7$ рівнів!
Бітове стиснення (Bitmap Indexing) та інструкція POPCNT:
- Щоб вузли дерева не зберігали масив із 32 порожніх вказівників, кожен вузол зберігає 32-бітне число-маску (bitmap) та масив лише реально існуючих дочірніх посилань.
- Позиція дитини обчислюється за 1 такт CPU через апаратну інструкцію процесора POPCNT (підрахунок встановлених бітів у масці):
```
int index = Integer.bitCount(bitmap & ((1 << bitPos) - 1));
```
Складність:
- Пошук та додавання займають $O(\log_{32} N) \le 7$ переходів, що на практиці працює так само швидко, як $O(1)$ у стандартній HashMap, проте забезпечує повну незмінність та збереження попередніх версій.

Lock-Free керування станом через `AtomicReference`

Персистентні структури даних ідеальні для моделювання високонавантаженого реактивного стану:

public class MarketOrderBook {
    // Незмінна персистентна мапа стакана заявок
    private final AtomicReference<io.vavr.collection.Map<String, Order>> orders = 
        new AtomicReference<>(io.vavr.collection.HashMap.empty());

    public void placeOrder(Order order) {
        // Lock-Free атомарна зміна версій за O(log32 N) без м'ютексів:
        orders.updateAndGet(current -> current.put(order.id(), order));
    }

    public io.vavr.collection.Map<String, Order> getSnapshot() {
        // Миттєвий знімок усього стакана за O(1) (копіювання 1 посилання на Root):
        return orders.get();
    }
}

4 Tricky Questions

1. У чому фундаментальна різниця між частково персистентними (Partially Persistent) та повністю персистентними (Fully Persistent) структурами даних?

Відповідь:

Partially Persistent (Частково персистентні): дозволяють читати стан структури на будь-який момент часу в минулому, але операція запису дозволена лише до найостаннішої (актуальної) версії. Історія модифікацій строго лінійна ($V_0 \to V_1 \to V_2$).
Fully Persistent (Повністю персистентні): дозволяють виконувати операції запису до будь-якої версії з минулого. При модифікації версії $V_1$ породжується нова гілка $V_1’$, перетворюючи історію версій на дерево (як розгалуження гілок branch у Git). Майже всі функціональні структури в Java (Vavr, PCollections) є повністю персистентними.

2. Як структура HAMT уникає витрат пам’яті на 32-елементні масиви в кожному вузлі, якщо у вузла лише 2 нащадки? Поясніть роботу `bitmap` та `POPCNT`.

Відповідь: Замість масиву Node[32] вузол HAMT зберігає 32-бітний примітив int bitmap та компактний масив Node[], чий розмір точно дорівнює кількості реальних нащадків (у цьому випадку 2). Кожен біт у bitmap показує, чи зайнятий відповідний із 32 слотів (1 — вузол є, 0 — вузла немає). Щоб дізнатися індекс потрібного нащадка в компактному масиві:

Обчислюється бітова маска для всіх слотів, розташованих праворуч від потрібного: mask = (1 << bitPosition) - 1.
Виконується побітове І: bitmap & mask.
Кількість одиниць у результаті дає точний індекс у компактному масиві. Цей підрахунок компілюється в одну апаратну інструкцію процесора POPCNT (у Java: Integer.bitCount(...)), що виконується за 1 такт CPU без циклів та розгалужень.

3. Чому в стандартній бібліотеці Java (JDK) досі немає вбудованих персистентних структур даних?

Відповідь:

Історична прихильність до імперативної парадигми: Java з самого початку проєктувалася навколо змінних масивів (Object[]) та мутабельних колекцій (ArrayList, HashMap) для максимальної продуктивності на однопотокових процесорах кінця 90-х.
Локальність даних у кеші CPU (Cache Locality): Стандартний ArrayList використовує неперервний блок пам’яті, що ідеально утилізує кеш-лінії L1/L2 процесора та апаратний prefetcher. Деревоподібні структури (HAMT, дерева) мають більше посилальних переходів (pointer chasing), що при однопотокових обчисленнях може поступатися пласким масивам за швидкістю доступу.
Складність API: Персистентні колекції вимагають повернення нового посилання на колекцію при кожній операції (list = list.append(x)), що ламає звичний контракт інтерфейсів java.util.Collection.

4. Як персистентні вектори (Persistent Vector у Clojure / Vavr) забезпечують швидке довільне читання за індексом за $O(1)$?

Відповідь: Персистентний вектор реалізований не як зв’язний список, а як 32-кове збалансоване дерево (32-way B-tree / Trie), де всі дані зберігаються в листках.

Читання за індексом $i$ розбиває двійкове представлення індексу на блоки по 5 бітів.
Кожен 5-бітний блок використовується як прямий індекс у масиві вузла відповідного рівня.
Оскільки максимальна глибина дерева фіксована і не перевищує 6–7 рівнів (навіть для мільярдів елементів), перехід за фіксованою кількістю посилань вважається алгоритмічно $O(\log_{32} N) \approx O(1)$ константним доступом.

🎯 Шпаргалка для інтерв’ю

Головне про Persistent Data Structures

Визначення: незмінні структури в RAM, які зберігають усі попередні версії при будь-яких змінах.
Головний механізм: Structural Sharing (перевикористання вузлів між старою та новою версією замість повного $O(N)$ копіювання).
HAMT (Hash Array Mapped Trie): основа швидких персистентних Map/Set (32-кові дерева, бітові маски, інструкція POPCNT).
Складність: додавання/пошук за $O(1)$ для списків та $O(\log_{32} N)$ для Map/Set.
Де застосовувати: Lock-Free керування станом (AtomicReference), Event Sourcing, Undo/Redo, реактивні системи.
Бібліотеки для Java: Vavr, PCollections.

Порівняння зі звичайними підходами

Червоні прапорці на співбесіді (Чого говорити не можна)

❌ «Персистентні структури даних — це таблиці, що зберігаються на жорсткий диск через Hibernate/JPA» — фатальна плутанина термінів CS та Enterprise Java.
❌ «Персистентна структура при додаванні копіює весь масив цілком» — ні, копіюються лише змінені вузли (Structural Sharing).
❌ «List.of() у Java — це персистентна структура» — ні, він позбавлений механізму ефективного створення версій.