Saya mencoba untuk menulis pencarian cabang dan terikat pada himpunan semua fungsi f: D -> R, di mana ukuran domainnya kecil (| D | ~ 20) dan jangkauannya jauh lebih besar (| R | ~ 2 ^ 20 ). Awalnya, saya datang dengan solusi berikut.
(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))))))))
Di sini parameter condlistke fungsi builderadalah daftar kondisi yang harus dipenuhi oleh solusi. Fungsi checkmengembalikan nil jika elemen dalam daftar kondisi dilanggar oleh partial-map. Fungsi ini recur-on-firstmenetapkan elemen pertama di domain ke elemen pertama dalam rentang dan mencoba membangun solusi dari sana. Gagal ini recur-on-firstmeminta dirinya untuk mencoba dan membangun solusi yang menetapkan elemen pertama dalam domain ke beberapa elemen selain yang pertama dalam rentang. Namun, harus mempertahankan daftar ignoredyang menyimpan elemen-elemen yang dibuang ini (seperti elemen pertama dalam rentang) karena dapat berupa gambar dari beberapa elemen lain dalam domain.
Ada dua masalah yang bisa saya lihat dengan solusi ini. Yang pertama adalah bahwa daftar ignoreddan rangefungsinya recur-on-firstcukup besar dan appendmereka adalah operasi yang mahal. Masalah kedua adalah bahwa kedalaman rekursi solusi tergantung pada ukuran kisaran.
Jadi saya datang dengan solusi berikut ini yang menggunakan daftar tertaut ganda untuk menyimpan elemen dalam rentang. Fungsi-fungsinya start, nextdan endmenyediakan fasilitas untuk beralih pada daftar yang tertaut ganda.
(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))))))
Runtime dari solusi kedua jauh lebih baik daripada runtime dari solusi pertama. The appendoperasi pada solusi pertama diganti oleh unsur-unsur splicing dan keluar dari daftar ganda terkait (operasi ini waktu yang konstan) dan kedalaman rekursi hanya tergantung pada ukuran domain. Tapi masalah saya dengan solusi ini adalah menggunakan Ckode gaya. Jadi pertanyaan saya adalah ini.
Apakah ada solusi yang seefisien solusi kedua tetapi tidak menggunakan setfstruktur data s dan bisa berubah? Dengan kata lain, apakah ada solusi pemrograman fungsional yang efisien untuk masalah ini?
sumber