Почему реализация застежки-молнии Clojure использует другие типы и структуры данных из застежки-молнии Huet?

Я сравниваю исходную статью Хуэта с реализацией Clojure и попыткой выяснить, почему были внесены изменения . Я новичок в Clojure, поэтому, если я ошибаюсь в своей интерпретации кода Clojure, поправьте меня.

В статье Хуэ тип пути (по Окамлу) Top | Node of tree list * path * tree list;;. В Clojure есть два дополнительных поля: pnodes и changed?. Для чего нужны эти поля? Прав ли я, полагая, что l и r соответствуют первой и третьей записи в типе Хуэта, а ppath - второму?

В застежке-молнии Huet используются связанные списки (обратите внимание, что я говорю о самом типе Loc, а не о структуре данных, с которой работает застежка-молния), в то время как в некоторых местах, например l, реализация Clojure использует векторы. Почему это изменение и каковы последствия временной сложности реализации Clojure?


algorithm clojure zipper
person ceridwen    schedule 02.09.2015    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Во-первых, вы правильно понимаете l, r и ppath.

pnodes и changed? работают вместе как оптимизация: когда вы переходите up, если changed? ложно, вы извлекаете узел из pnodes, а не перестраиваете его из текущего узла и левого и правого списков братьев и сестер.

Что касается использования вектора для l и списка для r. Опять же, речь идет о стоимости восстановления узла. В статье Хуэ есть (rev left) @ (t::right), который равен O (nleft), где nleft - размер слева. В Clojure у нас есть (concat l (cons node r)), который равен O (1) [1], потому что l, являющийся вектором, не нуждается в обратном (векторы в Clojure можно эффективно перемещать в любом направлении, но их можно добавлять только справа).

[1] Хорошо, это O (1) только во время создания: nleft conses будет лениво выделяться, поскольку результирующая последовательность будет использована для дальнейших вычислений.

person cgrand    schedule 03.09.2015