Persistant vector

Предисловие

Иммутабельность — фундаментальный принцип Clojure, означающий, что значения и структуры данных неизменяемы после создания. Вместо модификации существующих объектов операции возвращают новые объекты, сохраняя оригинальные данные неизменными. Рассмотрим ключевые аспекты.

Основные принципы

• Отсутствие переменных
  В Clojure нет "переменных" в традиционном понимании. Символы (например, def, let) связываются со значениями однократно:

(def numbers [1 2 3]) ; numbers всегда [1 2 3]
(conj numbers 4)      ; => [1 2 3 4] (новый вектор)

Попытка изменить numbers вызовет ошибку.

• Персистентные структуры данных
  Коллекции (векторы, мапы, множества) реализованы как персистентные структуры:

При "изменении" создаётся новая версия, переиспользующая неизмененные части оригинала.

Например, добавление элемента в вектор копирует только путь к новому элементу, а не весь массив.

Преимущества

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

• Детерминированность
  Код становится предсказуемым: функция всегда возвращает одинаковый результат для одних и тех же входных данных.

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

Примеры операций

;; Создание вектора
(def v1 [1 2 3])

;; "Добавление" элемента (возвращает новый вектор)
(def v2 (conj v1 4)) ; => [1 2 3 4]

;; Исходный вектор остаётся неизменным
(println v1) ; => [1 2 3]

;; Обновление значения в мапе
(def m1 {:a 1, :b 2})
(def m2 (assoc m1 :b 3)) ; => {:a 1, :b 3}

---

Оригнал - статья на английском с картинками(!): https://hypirion.com/musings/understanding-persistent-vector-pt-1

---

Что такое persistent vector?

В Clojure вектор — это не просто массив, как в JavaScript, а особая неизменяемая структура данных. Каждый раз, когда ты добавляешь или меняешь элемент, создаётся новый вектор, но при этом старый не копируется целиком. Это достигается благодаря умной структуре данных — сбалансированному дереву с высоким branching factor (обычно 32).

Почему нельзя просто копировать массив?

В JavaScript, если ты хочешь изменить массив "иммутабельно", приходится делать копию всего массива (например, через slice). Это быстро для маленьких массивов, но становится очень неэффективно для больших: копировать тысячи элементов ради одной вставки — дорого.

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

Как это выглядит внутри?

Дерево вместо массива

• Представь дерево, где каждый узел может содержать до 32 ссылок на поддеревья или элементы.
• Элементы хранятся только в листьях, а внутренние узлы — просто навигация.
• Все листья находятся на одной глубине (сбалансированность).
• Чтобы найти элемент по индексу, ты идёшь по дереву, используя части индекса как "адрес" (например, как биты в числе).

Пример: обновление значения

Допустим, у тебя есть вектор [0 1 2 3 4 5 6 7 8]. Если ты делаешь (assoc v 5 "beef"), то:

• Копируются только те узлы, которые лежат на пути к элементу с индексом 5.
• Всё остальное (остальные ветви дерева) остаётся неизменным и переиспользуется новым вектором.
• В результате, старый и новый вектор разделяют большую часть структуры, но выглядят как независимые значения.

Пример: добавление элемента (append)

Когда ты делаешь (conj v 9):

• Если в правом самом листе есть место — просто копируется путь и добавляется элемент.
• Если места нет, создаются новые узлы, чтобы вместить новый элемент.
• Если и в корне нет места, создаётся новый корень, глубина дерева увеличивается на 1.

Пример: удаление элемента (pop)

• Если в правом самом листе больше одного элемента — копируется путь, удаляется элемент.
• Если после удаления лист становится пустым, он убирается, а дерево "схлопывается" вверх.
• Если в корне осталась только одна ссылка, корень заменяется на своего единственного потомка, чтобы не было лишнего уровня.

Почему это быстро?

В теории, доступ к элементу — это O(log₃₂ N), потому что дерево очень "плоское": даже для миллиарда элементов глубина дерева — не больше 6. На практике это почти O(1), потому что число переходов по дереву очень маленькое.

Краткое сравнение с JavaScript

| | JavaScript Array (иммутабельно) | Clojure Persistent Vector |

| :-- | :-- | :-- |

| Изменение | Копия всего массива | Копия только пути |

| Добавление | Копия всего массива | Копия только пути |

| Производительность | O(N) | O(log₃₂ N) ≈ O(1) |

| Память | Много лишних копий | Эффективное переиспользование |

Ключевые идеи

• Persistence — старые версии коллекции всегда доступны, новые создаются быстро и экономно.
• Path copying — копируется только путь к изменяемому элементу, остальное переиспользуется.
• Высокий branching factor — дерево очень плоское, операции быстрые.
• Иммутабельность — никакой гонки данных, безопасно для многопоточности.

Если ты хочешь погрузиться глубже:

• В следующих частях автор разбирает, как именно по индексу выбирается путь по дереву, как реализованы быстрые операции типа subvec, и как устроены оптимизации (например, transients для временной мутабельности).

Persistent vector в Clojure — это очень умная альтернатива массиву, которая позволяет эффективно работать с большими коллекциями иммутабельно, не жертвуя скоростью и памятью, благодаря дереву с высокой ветвистостью и переиспользованию структуры.