Главная мысль урока: новая версия коллекции в Clojure не копирует старую. Вектор и мапа устроены как широкие деревья, и изменение копирует только путь от корня до изменённого места, а всё остальное новая версия делит со старой. Поэтому неизменяемость стоит
O(log₃₂ n)на операцию, а не копию всей коллекции.
Ты делаешь в «Хрониках Пограничья» кнопку «отменить ход». Самый прямой способ: перед каждым ходом сохранять копию мира. Мир это десяток героев, сотня квестов и десять тысяч предметов на карте. Тысяча ходов, и ты хранишь десять миллионов предметов, из которых почти все одинаковые. На JavaScript так никто не делает, вместо этого пишут журнал изменений и откатывают их по одному.
В Clojure кнопку «отменить» делают в лоб: кладут каждую версию мира в вектор истории. И это дёшево. Посмотри, что происходит, когда Тим лечится:
identical? проверяет не равенство по значению, а то, что слева и справа один и тот же объект в памяти. Новых объектов три: мапа мира, вектор героев и мапа Тима. Всё остальное, включая десять тысяч предметов и мапу Ирмы, у двух версий общее. Этот приём называется структурным разделением, а сам процесс копирования пути от корня до изменения копированием пути.
Общую теорию, с картинками и реализацией на JavaScript, разбирали в уроке про персистентные структуры. Здесь посмотрим, как это сделано в самом Clojure.
Дерево на ладони
Начнём с игрушки. Возьмём вектор из шестнадцати элементов и разложим его в дерево с ветвлением 4: четыре узла по четыре элемента. Чтобы найти элемент по номеру, номер делят на 4: частное это номер узла, остаток номер внутри узла.
Замена шестого элемента создала новый корень и новый второй узел. Три других узла новая версия взяла у старой. В картинке это выглядит так:
tree tree2
[ n0 n1 n2 n3 ] [ n0 n1' n2 n3 ] новый корень
| | | | | | | |
| | | +------ общий ---------|---|---|---+
| | +---------- общий ---------|---|---+
| | | |
| [4 5 6 7] | [4 5 :x 7] новый узел
+-------------------- общий -------+Это и есть весь фокус. Настоящий вектор Clojure устроен так же, только узлы шире и номер разбирается на куски по-другому.
Настоящий вектор: ветвление 32
В векторе Clojure каждый узел хранит до 32 детей. Число 32 выбрано не случайно: это 2⁵, поэтому номер элемента не делят, а режут на куски по 5 бит. Старшие 5 бит выбирают ребёнка корня, следующие 5 бит ребёнка на втором уровне, младшие 5 бит место в листе. Такое дерево называют битовым префиксным деревом.
Тысячный элемент лежит в нулевом ребёнке корня, в его 31-м ребёнке, на восьмом месте. Никакого поиска: путь вычисляется из номера тремя сдвигами.
Широкое ветвление делает дерево очень низким. Вот сколько уровней нужно вектору:
| Элементов до | Уровней | Сколько узлов копирует assoc |
|---|---|---|
| 32 | 0, всё лежит в хвосте (о нём ниже) | 1 |
| 1 024 | 2 | 2 |
| 32 768 | 3 | 3 |
| 1 048 576 | 4 | 4 |
| 33 554 432 | 5 | 5 |
| 1 073 741 824 | 6 | 6 |
Отсюда O(log₃₂ n): у вектора из миллиона элементов assoc копирует четыре узла по 32 ссылки, 128 ссылок вместо миллиона. На практике это почти константа, поэтому в уроке про коллекции get по номеру и называли быстрым.
Хвост вектора
Есть одна хитрость, без которой conj был бы медленнее. Вектор держит последние до 32 элементов не в дереве, а в отдельном массиве, хвосте:
вектор из 70 элементов
дерево хвост
[ лист0 лист1 ] [64 65 66 67 68 69]
| |
[0..31] [32..63]
conj 70 → копируется только хвост: [64 .. 70], дерево общееconj копирует только хвост, а дерево новая версия берёт целиком. Когда хвост наполнится до 32 элементов, он переезжает в дерево готовым листом, и начинается новый хвост. Поэтому conj в конец вектора стоит в среднем константу, а не O(log₃₂ n).
Мапа: то же дерево по хешу
Мапа не может резать на биты номер элемента, номера у неё нет. Она режет хеш ключа. Каждый ключ превращается в 32-битное число, и дальше всё как у вектора: 5 бит на уровень, до 32 детей у узла. Такую структуру называют HAMT. Чтобы не тратить память на пустые места, узел хранит битовую маску «какие из 32 детей есть» и плотный массив только из существующих.
Маленькие мапы устроены проще. До восьми пар Clojure хранит мапу плоским массивом «ключ, значение, ключ, значение»: на таких размерах пробежать восемь пар быстрее, чем считать хеш и спускаться по дереву. На девятой паре мапа сама превращается в HAMT. В браузере имена классов не показать, а на JVM видно:
(println (class {:a 1})) ; clojure.lang.PersistentArrayMap
(println (class (zipmap (range 8) (range 8)))) ; clojure.lang.PersistentArrayMap
(println (class (zipmap (range 9) (range 9)))) ; clojure.lang.PersistentHashMap
(println (class #{:mill :ford})) ; clojure.lang.PersistentHashSet
(assert (= (zipmap (range 9) (range 9)) (into {} (map vector (range 9) (range 9)))))Для тебя разницы нет: обе мапы равны по значению и работают с одними функциями. Множество устроено как мапа, у которой есть только ключи.
identical? и =
У персистентных структур есть приятное следствие для сравнения. = сравнивает по значению и в худшем случае обходит обе коллекции. Но если две версии делят узлы, сравнение может пропустить общую часть: одинаковый объект равен сам себе без обхода. С этой проверки = в Clojure и начинает. Библиотеки интерфейса на ClojureScript, например Reagent, этим пользуются: перед перерисовкой они сравнивают старые данные с новыми, и общие ветки сравниваются мгновенно.
assoc создал новый вектор даже тогда, когда положил на место тот же элемент. Равенство по значению сохранилось, а объект стал другим. Помни об этом, когда сравниваешь через identical?: он отвечает на вопрос «тот же ли это объект», а не «изменились ли данные».
Транзиенты: стройка без свидетелей
Иногда коллекцию строят с нуля из тысяч элементов: читают файл, собирают индекс. Каждый conj создаёт новую версию и копирует путь, хотя промежуточные версии никому не нужны. Для такого случая есть транзиенты:
Запусти и сравни время: транзиентная версия обычно быстрее в несколько раз. Правила работы с транзиентом:
transientпревращает коллекцию во временную изменяемую заO(1), старая остаётся нетронутой.- Меняют транзиент функциями с восклицательным знаком:
conj!,assoc!,dissoc!,disj!,pop!. - Пользуются только возвращённым значением, как с обычным
conj. Старую ссылку на транзиент после изменения не трогают. - В конце
persistent!возвращает неизменяемую коллекцию, и транзиент больше использовать нельзя.
Транзиент живёт внутри одной функции и не выходит наружу, поэтому снаружи она остаётся чистой. Часто писать транзиенты руками не придётся: into, mapv, frequencies и group-by уже пользуются ими внутри.
Проверь себя
Задание
Дальше
Неизменяемые значения отвечают на вопрос «как хранить версии дёшево». Вопрос «где лежит текущая версия мира» решают ссылки, о них в уроке про значения и ссылки. А в следующем уроке вернёмся к практике и научимся разбирать вложенные мапы и векторы прямо в аргументах функции.
домашка