J'essaie d'écrire une branche et une recherche liée sur l'ensemble de toutes les fonctions f: D -> R, où la taille du domaine est petite (| D | ~ 20) et la plage est beaucoup plus grande (| R | ~ 2 ^ 20 ). Au départ, j'ai trouvé la solution suivante.
(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))))))))
Ici, le paramètre condlistde la fonction builderest une liste de conditions qui doivent être satisfaites par une solution. La fonction checkrenvoie nil si aucun élément de la liste de conditions n'est violé par le partial-map. La fonction recur-on-firstaffecte le premier élément du domaine au premier élément de la plage et essaie de créer une solution à partir de là. A défaut, cela recur-on-firstinvoque pour essayer de construire une solution qui affecte le premier élément du domaine à un élément autre que le premier de la plage. Cependant, il doit conserver une liste ignoredqui stocke ces éléments supprimés (comme le premier élément de la plage) car ils pourraient être des images de certains autres éléments du domaine.
Il y a deux problèmes que je peux voir avec cette solution. Le premier est que les listes ignoredet rangedans la fonction recur-on-firstsont assez grandes et les appending est une opération coûteuse. Le deuxième problème est que la profondeur de récursivité de la solution dépend de la taille de la plage.
J'ai donc trouvé la solution suivante qui utilise des listes doublement liées pour stocker les éléments dans la plage. Les fonctions start, nextet endfournir des installations sur la liste itérer doublement chaînée.
(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))))))
Le temps d'exécution de la deuxième solution est bien meilleur que celui de la première solution. L' appendopération dans la première solution est remplacée par des éléments d'épissage dans et hors d'une liste doublement liée (ces opérations sont à temps constant) et la profondeur de récursivité ne dépend que de la taille du domaine. Mais mon problème avec cette solution est qu'elle utilise du Ccode de style. Voici donc ma question.
Existe-t-il une solution aussi efficace que la deuxième solution mais qui n'utilise pas de setfstructures de données s et mutables? En d'autres termes, existe-t-il une solution de programmation fonctionnelle efficace à ce problème?
la source