Структуры данных: строим из четырёх кирпичей

В Janet нет зоопарка коллекций: массив, кортеж, таблица, структура и буфер. Этого хватает, чтобы за экран кода собрать стек, очередь, кучу, множество, префиксное дерево и систему непересекающихся множеств. Урок открывает блок алгопрактики: всё, что мы здесь построим, будет работать в следующих трёх уроках.

Что уже дано бесплатно

Прежде чем строить, посмотри, что лежит в коробке. Классические структуры из учебника частично уже встроены в язык, просто называются иначе.

Учебник	В Janet	Стоимость операций
Динамический массив	@[]	доступ по индексу O(1), array/push и array/pop O(1)
Хеш-таблица	@{}	get, put, in в среднем O(1)
Строка байтов	@"" буфер	добавление в конец O(1), запись по индексу O(1)
Неизменяемая запись	{} и []	структурное сравнение и хеширование

Слово «O(1)» у array/push на самом деле означает амортизированную константу: изредка массив переезжает в больший кусок памяти, но в среднем по серии операций это O(1). Для алгозадач такой оценки достаточно.

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

В JavaScript для ключа-пары пришлось бы клеить строку "3,4". Здесь координата, ребро графа или состояние игры кладутся в таблицу как есть. В алгозадачах этот приём будет всплывать постоянно.

Стек: массив и договорённость

Стек не нужно строить, он уже есть. array/push кладёт в конец, array/pop снимает с конца, array/peek подглядывает не снимая:

Стек это не тип, а дисциплина: трогаем только конец массива. Проверим на классике, сбалансированы ли скобки:

Здесь всё из пройденного: строка перебирается по байтам, chr из урока про литералы даёт байт символа, label с return из урока про переходы обрывают проверку на первой ошибке.

Очередь: три попытки

С очередью интереснее. Снять элемент с конца дёшево, а вот с начала…

Попытка первая, наивная. (array/remove q 0) убирает первый элемент, но сдвигает все остальные: O(n) на каждое извлечение. Для десятка элементов сойдёт, для ста тысяч нет.

Попытка вторая, указатель головы. Не удаляем ничего. Держим индекс головы и двигаем его вперёд, а хвост подчищаем изредка, целым куском:

Каждое извлечение O(1), а редкая уборка амортизируется по той же логике, что и переезды array/push.

Попытка третья, два стека. Функциональная классика: входной стек принимает, выходной отдаёт. Когда выходной пуст, переливаем в него входной целиком, и порядок переворачивается сам:

Каждый элемент проходит ровно два push и два pop за свою жизнь, значит снова амортизированное O(1). Обрати внимание на деструктуризацию таблицы прямо в параметрах: приём из урока про поток выполнения отлично сокращает такой код.

Связный список: персистентность из кортежей

В языке с быстрыми массивами связный список нужен редко. Но у него есть суперспособность, которой нет у массива: персистентность. Соберём его из вложенных кортежей: ячейка это пара из головы и хвоста, пустой список это nil.

Добавление в голову не трогает старый список: (node 0 list) создаёт одну новую ячейку, хвост общий. Обе версии живы одновременно, и раз кортежи неизменяемы, никто никому ничего не сломает. На этой идее стоят структуры Clojure и Immutable.js, подробный разбор есть в уроке про персистентные структуры. А ещё это ровно то, как ты строил список захватов в PEG-грамматиках: парсер тоже не мутирует, а наращивает.

Куча: инвариант в массиве

Куча отвечает на вопрос «дай минимум» за O(log n), не сортируя всё целиком. Понадобится в задачах вида «топ-k» и в алгоритме Дейкстры из последнего урока блока.

Хитрость кучи в том, что дерево хранится в плоском массиве: у элемента с индексом i дети лежат в 2i + 1 и 2i + 2, а родитель в (div (- i 1) 2). Инвариант: родитель не больше детей, значит минимум всегда в корне.

Новый элемент падает в конец и всплывает до своего места; при извлечении последний элемент встаёт в корень и тонет. Оба пути не длиннее высоты дерева, отсюда O(log n).

Компаратор в :less? делает кучу универсальной. Минимальная по умолчанию, максимальная через >, куча пар «частота и слово» через сравнение первых элементов:

Помнишь топ слов из CLI-проекта? Там мы сортировали все частоты целиком за O(n log n). Куча размера k даёт топ-k за O(n log k): прогоняешь частоты через кучу и выкидываешь минимум, как только размер превысил k.

Множество: таблица, где важны только ключи

Множество это таблица, у которой нас интересуют одни ключи. Значением кладём true, потому что put со значением nil удаляет ключ, и этим же удобно удалять из множества:

Операции над множествами это циклы по ключам:

Если хочется готового, в реестре пакетов есть janet-set: та же идея, вылизанная до полного набора операций. Реализация занимает около сотни строк, прочитай её целиком, это быстрый способ откалибровать вкус к идиоматичному Janet.

Префиксное дерево: таблицы в таблицах

Trie хранит множество слов так, чтобы искать по префиксу. Узел это таблица «байт, дальше поддерево», конец слова помечаем ключом :end:

Никакого класса Node: вложенные таблицы и есть дерево. Распечатай t в REPL и увидишь структуру насквозь, это одно из главных удовольствий Janet.

Непересекающиеся множества: два массива

Последняя структура блока отвечает на вопрос «в одной ли компоненте эти два элемента» почти за O(1). Она пригодится в задачах на связность: острова, друзья друзей, циклы в графе.

Два массива и две идеи: сжатие пути распрямляет дерево при каждом поиске, объединение по рангу не даёт ему вытянуться. Вместе они дают практически константное время на операцию.

Что почитать в экосистеме

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

• janet-set: множества на таблицах, эталон маленького пакета.
• tarray: типизированные массивы из нативного кода. Когда миллион чисел не влезает в обычный массив по памяти, это ответ.
• gapbuffer: буфер с разрывом, структура из текстовых редакторов. Хороший пример того, как буфер Janet работает строительным материалом.
• tsort: топологическая сортировка, встретится нам в уроке про графы.

Остальное, как ты видел, быстрее написать, чем найти: куча уложилась в полсотни строк.

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

• Четыре кирпича закрывают базу: массив это стек и динамический массив, таблица это хеш-таблица, буфер это изменяемая строка байтов.
• Кортежи и структуры хешируются по содержимому, поэтому годятся в ключи таблиц. Координаты и состояния кладём в таблицу без склейки строк.
• Быстрая очередь: указатель головы с редкой уборкой или два стека. Оба варианта амортизированное O(1).
• Cons-список из кортежей персистентен: новая голова не копирует хвост, старые версии живы.
• Куча живёт в плоском массиве, инвариант «родитель не больше детей», добавление и извлечение O(log n). Компаратор делает её универсальной.
• Множество это таблица со значениями true, удаление через put с nil.
• Trie это таблицы в таблицах, ДНМ это два массива со сжатием пути и рангом.

Упражнения

Дальше

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