Я пытаюсь написать поиск ветвей и границ на множестве всех функций f: D -> R, где размер домена мал (| D | ~ 20), а диапазон намного больше (| R | ~ 2 ^ 20 ). Изначально я придумал следующее решение.
(builder (domain range condlist partial-map)
(let ((passed? (check condlist partial-map)))
(cond
((not passed?) nil)
(domain (recur-on-first domain range condlist partial-map '()))
(t partial-map))))
(recur-on-first (domain range condlist partial-map ignored)
(cond
((null range) nil)
(t (let ((first-to-first
(builder (cdr domain)
(append ignored (cdr range))
condlist
(cons (cons (car domain) (car range)) partial-map))))
(or first-to-first
(recur-on-first domain
(cdr range)
condlist
partial-map
(cons (car range) ignored))))))))
Здесь параметр condlist
функции builder
- это список условий, которым должно удовлетворять решение. Функция check
возвращает ноль, если какой-либо элемент в списке условий нарушается partial-map
. Функция recur-on-first
назначает первый элемент в домене первому элементу в диапазоне и пытается построить решение оттуда. В противном случае он recur-on-first
сам пытается создать решение, которое назначает первый элемент в домене некоторому элементу, отличному от первого в диапазоне. Однако он должен поддерживать список, в ignored
котором хранятся эти отброшенные элементы (например, первый элемент в диапазоне), поскольку они могут быть изображениями некоторых других элементов в домене.
Есть две проблемы, которые я вижу с этим решением. Во-первых, списки ignored
и range
функции recur-on-first
довольно велики, и append
их использование является дорогостоящей операцией. Вторая проблема заключается в том, что глубина рекурсии решения зависит от размера диапазона.
Поэтому я пришел к следующему решению, которое использует двусвязные списки для хранения элементов в диапазоне. Функции start
, next
и end
обеспечивают средства перебрать двусвязный список.
(builder (domain range condlist &optional (partial-map nil))
(block builder
(let ((passed? (check condlist partial-map)))
(cond
((not passed?) nil)
(domain (let* ((cur (start range))
(prev (dbl-node-prev cur)))
(loop
(if (not (end cur))
(progn
(splice-out range cur)
(let ((sol (builder (cdr domain)
range
condlist
(cons (cons (car domain) (data cur)) partial-map))))
(splice-in range prev cur)
(if sol (return-from builder sol)))
(setq prev cur)
(setq cur (next cur)))
(return-from builder nil)))))
(t partial-map))))))
Время выполнения второго решения намного лучше, чем время выполнения первого решения. append
Операции в первом растворе заменяются сплайсинг элементы в и из дважды связанного списка (эти операции являются постоянным временем) , а глубина рекурсии зависит только от размера домена. Но моя проблема с этим решением заключается в том, что он использует C
код стиля. Итак, мой вопрос заключается в следующем.
Есть ли решение, которое является таким же эффективным, как и второе, но не использует setf
s и изменяемые структуры данных? Другими словами, есть ли эффективное функциональное программирование для решения этой проблемы?
источник