Главная мысль урока: задачи с собеседований на Clojure решаются теми же идеями, что на любом языке (хеш-таблица, очередь, свёртка), только без изменяемого массива под рукой. Чаще всего это помогает: нужная функция уже есть в
clojure.core, а состояние цикла видно вloopцеликом. Где неизменяемость мешает скорости, локально берут транзиент.
Студия, которая делает «Хроники Пограничья», зовёт тебя на собеседование. Интервьюер открывает редактор с REPL и говорит: «Пиши на чём удобно». Ты выбираешь Clojure, и первая задача звучит так: «В лавке список цен. Есть ли два разных предмета, которые вместе стоят ровно столько, сколько у героя золота?»
На Python ты бы завёл множество и прошёл циклом по ценам. На Clojure то же самое, только цикл это reduce, а множество не меняется, а пересобирается:
Один проход, O(n). reduced останавливает свёртку, как только пара нашлась. Вторая строка показывает ловушку, которую интервьюер заметит сразу: если пары нет, reduce вернул накопленное множество, а не false. Множество истинно, и функция соврала. Чинится обёрткой (true? ...) или явной проверкой в конце. Проговори это вслух: крайний случай «ответа нет» на собеседовании проверяют первым.
В задаче ниже ты напишешь вариант, который возвращает индексы пары. Дальше пройдём по типовым задачам и посмотрим, какой инструмент Clojure закрывает каждую.
Частоты и группировка
Половина задач с собеседований это «посчитай» или «сгруппируй». В Clojure для них есть готовые функции из урока про библиотеку последовательностей:
Группировка анаграмм уложилась в одну строку: ключ группы это отсортированные буквы слова, group-by сам собирает слова с одинаковым ключом. В уроке про паттерны на Janet то же решение заняло цикл с таблицей.
sort-by с juxt сортирует по нескольким ключам сразу: сначала по убыванию частоты, при равенстве по имени. Это сортировка «топ-N», которая встретится в финальном проекте. sorted-map держит ключи в порядке, когда ответ надо выдать отсортированным.
Два указателя без указателей
Если цены отсортированы, пару можно найти без множества: один указатель с начала, другой с конца. Сумма больше нужной, двигаем правый, меньше, левый. В Clojure указатели это два числа в loop, а вектор отдаёт элемент по индексу почти за O(1) (честно за O(log₃₂ n), как в уроке про персистентность):
Всё состояние алгоритма в двух связываниях loop, и каждый recur явно говорит, какой указатель сдвинулся. Ошибиться с «забыл увеличить i» здесь труднее, чем в while с изменяемыми переменными: recur требует назвать оба новых значения.
Обход в ширину
Карта Пограничья это граф: области и тропы между ними. «За сколько переходов дойти от деревни до замка?» это обход в ширину. Граф удобно хранить мапой из вершины в множество соседей. Классический BFS держит очередь, но в Clojure его часто пишут слоями: текущий фронт это множество, следующий собирается из соседей фронта.
Каждый виток loop это один слой, steps считает слои. Множество seen не даёт вернуться назад, иначе обход ходил бы между деревней и лесом вечно.
Если нужна настоящая очередь, она в Clojure тоже есть и тоже неизменяемая. На JVM это clojure.lang.PersistentQueue/EMPTY, в ClojureScript литерал #queue []:
(def trails {:village #{:forest :river} :forest #{:ruins} :river #{:bridge}
:bridge #{:castle} :ruins #{} :castle #{}})
(defn bfs-order [graph start]
(loop [queue (conj clojure.lang.PersistentQueue/EMPTY start)
seen #{start}
order []]
(if-let [node (peek queue)]
(let [fresh (remove seen (sort (graph node)))]
(recur (into (pop queue) fresh) (into seen fresh) (conj order node)))
order)))
(def order (bfs-order trails :village))
(println order)
(assert (= [:village :forest :river :ruins :bridge :castle] order))peek смотрит голову, pop возвращает очередь без неё, into добавляет в хвост. Все три операции не трогают старую очередь.
Динамика: reduce и memoize
Динамическое программирование в императивном языке это массив, который заполняется в цикле. В Clojure массив становится вектором, а цикл свёрткой. «Сколькими способами собрать 10 золотых монетами 1, 2 и 5?»:
Внешняя свёртка идёт по монетам, внутренняя по суммам. (w (- a coin)) берёт уже посчитанное число способов для суммы поменьше. Та же задача в уроке про графы и динамику на Janet решена изменяемым массивом, сравни, насколько близки решения.
Второй способ это рекурсия сверху вниз с запоминанием. memoize превращает функцию в такую, которая помнит прошлые ответы. Рекурсивную функцию для этого объявляют через def, чтобы внутренний вызов шёл уже в запомненную версию:
Без memoize вызов (stairs 80) считался бы дольше, чем живёт сервер: дерево вызовов растёт как числа Фибоначчи. С ним каждый n считается один раз.
Когда честнее транзиент
Неизменяемость стоит памяти: каждый conj создаёт новую версию, пусть и разделяя структуру со старой. Внутри одной функции, где промежуточные версии никто не видит, это лишняя работа. Для таких мест есть транзиент:
Снаружи функция чистая: вход число, выход обычный вектор. Изменяемость живёт только между transient и persistent!. Так устроены frequencies, into и group-by внутри clojure.core, поэтому сами они уже быстрые. Транзиент пишут руками, когда профилировщик показал горячий цикл. На собеседовании хватит сказать, что такой приём есть и когда он оправдан.
Шпаргалка
| Задача | Инструмент |
|---|---|
| Посчитать повторы | frequencies |
| Сгруппировать по признаку | group-by |
| «Видели ли мы это раньше» | множество в reduce, reduced для выхода |
| Топ-N с правилом для равных | sort-by с juxt, take |
| Два указателя, окно | loop с индексами и recur |
| Кратчайший путь по шагам | BFS слоями множеств или PersistentQueue |
| Динамика снизу вверх | reduce над вектором ответов |
| Динамика сверху вниз | memoize |
| Горячий цикл | transient и persistent! |
Попробуй руками
Две задачи. В первой лавка: найти индексы пары предметов на сумму золота и самую длинную серию дней подряд, когда игрок заходил в игру. Во второй подземелье: кратчайший путь по сетке и число путей до выхода.
Проверь себя
Задание
Дальше
Разминка закончена. В финальном проекте те же frequencies, sort-by и трансдьюсеры разберут настоящий events.log курса аналитика, и ответы сойдутся с его цифрами.
домашка