Estou tentando escrever uma ramificação e pesquisa vinculada no conjunto de todas as funções f: D -> R, onde o tamanho do domínio é pequeno (| D | ~ 20) e o intervalo é muito maior (| R | ~ 2 ^ 20 ) Inicialmente, eu vim com a seguinte solução.
(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))))))))
Aqui, o parâmetro condlist
para a função builder
é uma lista de condições que devem ser satisfeitas por uma solução. A função check
retorna nulo se qualquer elemento da lista de condições for violado pelo partial-map
. A função recur-on-first
atribui o primeiro elemento no domínio ao primeiro elemento no intervalo e tenta criar uma solução a partir daí. Se isso recur-on-first
não for feito, tente criar uma solução que atribua o primeiro elemento no domínio a algum elemento que não seja o primeiro no intervalo. No entanto, ele deve manter uma lista ignored
que armazena esses elementos descartados (como o primeiro elemento do intervalo), pois podem ser imagens de alguns outros elementos no domínio.
Existem dois problemas que posso ver com esta solução. O primeiro é que as listas ignored
e range
na função recur-on-first
são bastante grandes e, append
por isso, é uma operação cara. O segundo problema é que a profundidade de recursão da solução depende do tamanho do intervalo.
Então, eu vim com a seguinte solução que usa listas duplamente vinculadas para armazenar os elementos no intervalo. As funções start
, next
e end
fornecer instalações para iterar sobre a lista duplamente ligada.
(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))))))
O tempo de execução da segunda solução é muito melhor que o tempo de execução da primeira solução. A append
operação na primeira solução é substituída por elementos de emenda dentro e fora de uma lista duplamente vinculada (essas operações são de tempo constante) e a profundidade da recursão depende apenas do tamanho do domínio. Mas o meu problema com esta solução é que ela usa C
código de estilo. Então, minha pergunta é essa.
Existe uma solução que seja tão eficiente quanto a segunda solução, mas que não use setf
estruturas de dados mutáveis? Em outras palavras, existe uma solução de programação funcional eficiente para esse problema?
fonte