Зипперы в Clojure (часть 7). Обход в ширину. Улучшенный обмен валют
Оглавление
- Зипперы (часть 1). Азы навигации
- Зипперы (часть 2). Автонавигация
- Зипперы (часть 3). XML-зипперы
- Зипперы (часть 4). Поиск в XML
- Зипперы (часть 5). Редактирование
- Зипперы (часть 6). Виртуальные деревья. Обмен валют
- Зипперы (часть 7). Обход в ширину. Улучшенный обмен валют
- Зипперы (часть 8). Заключение
В прошлый раз мы работали с деревом валют, чтобы построить цепочку обмена. Мы
нашли решение задачи, но упомянули, что в особых случаях дерево может получиться
бесконечным. Объясним, как это возможно. Для этого вспомним, как zip/next
обходит дерево.
Алгоритм называется depth first search или обход в глубину. При таком обходе код стремится в первую очередь вниз, а уже потом — в сторону (в нашем случае вправо). В этом легко убедиться, если разложить данные на части с помощью зиппера:
(->> [1 [2 [3] 4] 5]
zip/vector-zip
iter-zip
(map zip/node)
(map println))
;; 1
;; [2 [3] 4]
;; 2
;; [3]
;; 3
;; 4
;; 5
Цифра 3
, идущая перед 4
, говорит о том, что зиппер следует вглубь (внутрь
вектора [3]
) и только потом право.
Ещё более интересен случай с деревом, где у каждого узла потомки [1 2 3]
. При
обходе такого дерева зиппер будет стремиться вниз, каждый раз спускаясь в
очередной вектор [1 2 3]
и становясь на единицу. Покажем это на схеме:
(def zip-123
(zip/zipper any?
(constantly (seq [1 2 3]))
nil
1))
┌───────┐
│[1 2 3]│
└───────┘
│
┌───────┐ │
│[1 2 3]│◀──┘
└───────┘
│
┌───────┐ │
│[1 2 3]│◀─┘
└───────┘
│
│
... ◀─┘
Поскольку в зиппере нет условия, по которому производство потомков
останавливается, их вложенность неограничена. Функция iter-zip
вернёт
бесконечную цепочку локаций, в каждой из которых единица. Неважно, сколько
единиц мы возьмём от неё – сто или тысячу – получим столько же единиц.
(->> zip-123
iter-zip
(take 10)
(map zip/node))
;; (1 1 1 1 1 1 1 1 1 1)
Вернёмся к обмену валют. Предположим, банк меняет рубли на доллары, доллары на евро и евро на рубли. Выразим это в коде:
(def rules
[[:rub :usd]
[:usd :eur]
[:eur :rub]])
Читатель заметит, что получился замкнутый круг:
┌───────┐
┌───▶│ rub │────┐
│ └───────┘ │
│ ▼
┌───────┐ ┌───────┐
│ eur │◀────────│ usd │
└───────┘ └───────┘
Недостаток прошлого решения в том, что оно не учитывает цикличность правил. Предположим, клиент хочет обменять рубли на лиры. Начнём строить дерево от рубля. Начало цепочки:
┌───────┐
│ rub │
└───────┘
│
┌───────┐ │
│ usd │◀──┘
└───────┘
│
┌───────┐ │
│ eur │◀─┘
└───────┘
│
┌───────┐ │
│ rub │◀─┘
└───────┘
Мы снова пришли к рублю. Для него мы получим доллар, для доллара евро, затем рубль. Если продолжить итерацию, будем бесконечно погружаться в эту цепочку.
Логика подсказывает, что нужно пресечь обход вглубь, если очередная валюта равна
исходной. Проще говоря, у элемента :rub
, который стоит не на вершине, не
может быть потомков. Но функции branch?
и make-children
не знают, какое
место в дереве занимает элемент. Они принимают значения, а не локации, и не
могут ответить на вопрос, вершина это или нет.
Проблему можно исправить с помощью состояния, например атома, который хранил бы
список валют, которые мы обошли. Другой вариант – проверять, в какой раз мы
обращаемся к валюте from
для поиска потомков. Если в первый раз, мы на вершине
дерева. Найдём потомков и изменим атом, на котором замкнута функция
children
. Если это последующий раз (атом изменён), мы наткнулись на цикл, и
для него потомков нет.
Оба способа имеют право на жизнь, но хотелось бы решить задачу без состояния и изменяемых средств.
Если посмотреть на дерево, станет ясно: проблема в порядке обхода. Поскольку мы стремимся вглубь, велика вероятность попасть в кротовую нору, из которой нельзя выбраться. Нам может повезти, когда мы удачно шагнули в ветку с решением (слева), а бесконечная ветка (справа) осталась нетронутой:
┌───────┐
│ rub │
└───────┘
│
┌───────┐ │ ┌───────┐
│ yen │◀──┴──▶│ usd │
└───────┘ └───────┘
│ │
┏━━━━━━━┓ │ │ ┌───────┐
┃ lir ┃◀──┘ └──▶│ eur │
┗━━━━━━━┛ └───────┘
│
│ ┌───────┐
└──▶│ rub │
└───────┘
│
│
└──▶ ...
Однако это везение, и на него нельзя полагаться в решении задач.
Предположим теперь, зиппер обходит локации не вглубь, а вширь и вправо. С таким порядком нам не страшны бесконечные ветки. Если таковая закралась в дерево, она не оттянет на себя обход. Вместо этого мы спускаемся по этажам и читаем все элементы этого уровня. Даже если один из них относится к бесконечной ветви, это не помешает исследовать остальные. Рисунок ниже показывает, как горизонтальный обход поможет добраться до цели. Вертикальный обход ушёл бы вы бесконечность, потому что обе ветви цикличны.
┌───────┐
┌─│ rub │
│ └───────┘
▼
┌───────┐ ┌───────┐
│ yen │──▶│ usd │
└───────┘ └───────┘
│
┌─────────────────┘
▼
┏━━━━━━━┓ ┌───────┐
┃ lir ┃───────────────▶│ eur │
┗━━━━━━━┛ └───────┘
│
┌─────────────────────────────────┘
▼
┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐
│ rub │──▶│ tug │────────▶│ yen │──▶│ rub │
└───────┘ └───────┘ └───────┘ └───────┘
│ │
│ │
... ◀─┘ └─▶ ...
Проблема в том, что модуль clojure.zip
предлагает только один способ обхода —
в глубину с помощью zip/next
. Другого алгоритма не предусмотрено. Мы напишем
свою функцию, чтобы обойти зиппер “послойно”. Говоря иначе, для дерева как на
рисунке:
┌───────┐
1 │ 1 │
└───────┘
│
┌───────┐ │ ┌───────┐
2 │ 2 │◀────────┴────────▶│ 3 │
└───────┘ └───────┘
│ │
┌───────┐ │ ┌───────┐ ┌───────┐ │ ┌───────┐
3 │ 4 │◀──┴──▶│ 5 │ │ 6 │◀──┴──▶│ 7 │
└───────┘ └───────┘ └───────┘ └───────┘
мы получим слои:
[1]
[2 3]
[4 5 6 7]
, при этом каждый элемент будет не примитивом, а локацией. Это значит, элемент помнит свое положение в дереве, от него можно переходить к другим элементам, получить его путь и так далее.
Для начала нужна функция, которая вернёт дочерние локации исходной. Её логика проста: погружаемся вниз, и если результат не пуст, двигаемся вправо.
(defn loc-children [loc]
(when-let [loc-child (zip/down loc)]
(->> loc-child
(iterate zip/right)
(take-while some?))))
Обратите внимание, что это не то же самое, что zip/children
. Последняя вернёт
значения, а не локации, а нам нужны именно локации. Сравните выражения:
(-> [1 2 3]
zip/vector-zip
zip/children)
(1 2 3)
и
(-> [1 2 3]
zip/vector-zip
loc-children)
([1 {:l [] :pnodes [[1 2 3]] :ppath nil :r (2 3)}]
[2 {:l [1] :pnodes [[1 2 3]] :ppath nil :r (3)}]
[3 {:l [1 2] :pnodes [[1 2 3]] :ppath nil :r nil}])
Во втором случае получили локации, в то время как zip/children
просто
обращается к функции для нахождения потомков, которую передали в зиппер.
Предположим, что для некоторой локации loc-children
вернула список её
потомков. Чтобы спуститься на уровень ниже, нужно найти потомков для них и
объединить результат. Проще всего это это сделать выражением:
(mapcat loc-children locs)
, где locs
— локации текущего уровня. Если передать в locs
результат
mapcat
, продвинемся ещё дальше, и так до тех пор, пока не получим пустую
последовательность. Всё вместе даёт нам функцию loc-layers
:
(defn loc-layers [loc]
(->> [loc]
(iterate (fn [locs]
(mapcat loc-children locs)))
(take-while seq)))
Она принимает корневую локацию, от которой начинается итерация по слоям. Первый слой мы задали явно как вектор одной локации. Затем идут его потомки, затем потомки потомков и так далее. Мы остановимся лишь когда получим пустой слой. Быстрая проверка:
(def data [[[[1]]] 2 [[[3]]] 3])
(let [layers (-> data
zip/vector-zip
loc-layers)]
(for [layer layers]
(->> layer
(map zip/node)
println)))
;; ([[[[1]]] 2 [[[3]]] 3])
;; ([[[1]]] 2 [[[3]]] 3)
;; ([[1]] [[3]])
;; ([1] [3])
;; (1 3)
Чтобы соединить слои в цепь, воспользуемся apply
и concat
. Эта функция не
понадобится в решении задачи, но может оказаться полезной:
(defn loc-seq-layers [loc]
(apply concat (loc-layers loc)))
Вернёмся к обмену валют. Подберём правила обмена так, чтобы в них были циклические зависимости:
(def rules2
[[:rub :usd]
[:usd :eur]
[:eur :rub]
[:rub :lir]
[:lir :eur]
[:eur :din]
[:din :tug]])
Зиппер не изменится, но теперь мы обходим его по-другому: не с помощью
zip/next
, а функцией loc-layers
. На каждом шаге получим слои обмена. Наша
задача — найти в очередном слое локации, чей узел равен конечной валюте. Если
нашли хотя бы одну, задача решена. Останется вычислить до них путь.
(defn exchange2 [rules from to]
(letfn [(get-children [value]
(seq (for [[v1 v2] rules
:when (= v1 value)]
v2)))
(loc-to? [loc]
(-> loc zip/node (= to)))
(find-locs-to [layer]
(seq (filter loc-to? layer)))
(->exchange [loc]
(conj (zip/path loc) (zip/node loc)))]
(let [zipper (zip/zipper keyword?
get-children
nil
from)]
(->> zipper
loc-layers
(some find-locs-to)
(map ->exchange)))))
Заметим, что теперь не нужно сравнивать длины цепочек: если локации относятся к одному уровню, число шагов до них одинаково. По условию задачи мы заинтересованы в самых коротких вариантах обмена. Если на третьем уровне нашлась одна цепочка, а на четвертом их три, последние нам не интересны — обход завершится на третьем слое.
Примеры обмена с правилами, заданными в rules2
:
(exchange2 rules2 :rub :eur)
([:rub :usd :eur] [:rub :lir :eur])
(exchange2 rules2 :rub :tug)
([:rub :usd :eur :din :tug] [:rub :lir :eur :din :tug])
(exchange2 rules2 :lir :din)
([:lir :eur :din])
Решение все ещё не идеально. Если указать пару валют, для которых нет цепочки,
получим бесконечный цикл. Чтобы пресечь его, ограничьте число слоев каким-то
разумным числом, например пятью. С точки зрения финансов обмен с таким числом
операций будет невыгодным, а потому лишен смысла. Технически это значит добавить
форму (take N)
сразу после loc-layers
:
(->> zipper
loc-layers
(take 5)
(some find-locs-to)
(map ->exchange))
Теперь для неверной пары получим пустой результат:
(exchange2 rules2 :tug :yen)
()
Задачу можно развить еще дальше. Скажем, для каждой цепочки считать издержки и
комиссию за операцию. Для этого в вектор [:from :to]
добавим обменный курс и
вознаграждение. В зависимости от того, на чьей мы стороне — клиента или банка —
будем искать самые затратные или оптимальные обмены. Предлагаем читателю
придумать свои вариации к этой задаче.
На этом мы закончим с валютами и двинемся дальше. Мы рассмотрели, как порядок
обхода влияет на решение задачи. В разных случаях применяют методы в глубину и в
ширину. Это важно для бесконечных деревьев, когда алгоритм может зациклиться при
обходе. В поставке clojure.zip
нет обхода вширь, но легко написать функцию
деления зиппера на слои. Возможно, loc-layers
пригодится вам в других случаях,
связанных с графами и вершинами.
(Продолжение следует)
Оглавление
- Зипперы (часть 1). Азы навигации
- Зипперы (часть 2). Автонавигация
- Зипперы (часть 3). XML-зипперы
- Зипперы (часть 4). Поиск в XML
- Зипперы (часть 5). Редактирование
- Зипперы (часть 6). Виртуальные деревья. Обмен валют
- Зипперы (часть 7). Обход в ширину. Улучшенный обмен валют
- Зипперы (часть 8). Заключение
Нашли ошибку? Выделите мышкой и нажмите Ctrl/⌘+Enter