Próbuję napisać rozgałęzienie i wyszukiwanie powiązane na zbiorze wszystkich funkcji f: D -> R, gdzie rozmiar domeny jest mały (| D | ~ 20), a zakres jest znacznie większy (| R | ~ 2 ^ 20 ). Początkowo wymyśliłem następujące rozwiązanie.
(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))))))))
Tutaj parametrem condlistfunkcji builderjest lista warunków, które powinno spełnić rozwiązanie. Funkcja checkzwraca zero, jeśli dowolny element na liście warunków jest naruszony przez partial-map. Funkcja recur-on-firstprzypisuje pierwszy element w domenie do pierwszego elementu w zakresie i próbuje stamtąd zbudować rozwiązanie. W przeciwnym razie recur-on-firstwywołuje się próba zbudowania rozwiązania, które przypisuje pierwszy element w domenie do innego elementu niż pierwszy z zakresu. Musi jednak utrzymywać listę, ignoredktóra przechowuje odrzucone elementy (jak pierwszy element w zakresie), ponieważ mogą to być obrazy niektórych innych elementów w domenie.
Są dwa problemy, które widzę dzięki temu rozwiązaniu. Pierwszym z nich jest to, że listy ignoredi rangefunkcja recur-on-firstsą dość duże, a appendich wprowadzenie jest kosztowną operacją. Drugi problem polega na tym, że głębokość rekurencji rozwiązania zależy od wielkości zakresu.
Wymyśliłem więc następujące rozwiązanie, które wykorzystuje podwójnie połączone listy do przechowywania elementów w zakresie. Funkcje start, nextoraz endzapewnienia możliwości iteracyjne nad podwójnie połączonej listy.
(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))))))
Środowisko wykonawcze drugiego rozwiązania jest znacznie lepsze niż środowisko wykonawcze pierwszego rozwiązania. appendOperacji w pierwszym roztworze zastępuje elementy splicingu i obecnie podwójnie połączonej listy (operacje te są stałe w czasie) i głębokość rekursji zależy tylko od wielkości domeny. Ale moim problemem z tym rozwiązaniem jest to, że używa Ckodu stylu. Więc moje pytanie brzmi:
Czy istnieje rozwiązanie, które jest tak samo wydajne jak drugie rozwiązanie, ale nie wykorzystuje setfs i zmiennych struktur danych? Innymi słowy, czy istnieje skuteczne rozwiązanie programowania funkcjonalnego tego problemu?
źródło