我已经完成了Graham Common Lisp第5章练习5,它需要一个带有对象X和向量V的函数,并返回紧接在V中的X之前的所有对象的列表.
它的作用如下:
> (preceders #\a "abracadabra")
(#\c #\d #r)
我做了递归版:
(defun preceders (obj vec &optional (result nil) &key (startt 0))
(let ((l (length vec)))
(cond ((null (position obj vec :start startt :end l)) result)
((= (position obj vec :start startt :end l) 0)
(preceders obj vec result
:startt (1+ (position obj vec :start startt :end l))))
((> (position obj vec :start startt :end l) 0)
(cons (elt vec (1- (position obj vec :start startt :end l)))
(preceders obj vec result
:startt (1+ (position obj vec
:start startt
:end l))))))))
它工作正常,但我的老师给了我以下批评:
"这反复调用长度.对于向量来说不是那么糟糕,但仍然是不必要的.更高效和更灵活(对于用户而言)代码就像定义其他序列处理函数一样.使用:start和:end关键字参数,其他方式序列函数具有相同的默认初始值.长度最多应该被调用一次."
我正在咨询Common Lisp教科书和谷歌,但似乎对这一点似乎没什么帮助:我不知道他的意思是"使用:start和:end关键字参数",我不知道如何"呼叫长度只有一次".如果你们能让我知道如何改进我的代码以满足我老师发布的要求,我将不胜感激.非常感谢!
更新:
嗨伙计们,现在我想出了以下代码:
(defun preceders (obj vec
&optional (result nil)
&key (start 0) (end (length vec)) (test #'eql))
(let ((pos (position obj vec :start start :end end :test test)))
(cond ((null pos) result)
((zerop pos) (preceders obj vec result
:start (1+ pos) :end end :test test))
(t (preceders obj vec (cons (elt vec (1- pos)) result)
:start (1+ pos) :end end :test test)))))
我得到了批评:
"当你有一个复杂的递归调用在多个分支中重复相同时,首先执行调用通常更简单,将其保存在局部变量中,然后在更简单的IF或COND中使用该变量."
另外,对于我的函数的迭代版本:
(defun preceders (obj vec)
(do ((i 0 (1+ i))
(r nil (if (and (eql (aref vec i) obj)
(> i 0))
(cons (aref vec (1- i)) r)
r)))
((eql i (length vec)) (reverse r))))
我得到了批评
"在更好的位置启动DO并删除重复的> 0测试"
能否请您与我分享您的想法,我认为这是我迈向成功的最后一步!非常感谢!
这种函数的典型参数列表是:
(defun preceders (item vector
&key (start 0) (end (length vector))
(test #'eql))
...
)
如您所见,它有START和END参数.
TEST是默认的比较函数.使用(funcall测试项目(aref vector i)).通常还有一个KEY参数......
对于PRECEDERS的每次递归调用,都会重复调用LENGTH.
我会做非递归版本并在向量上移动两个索引:一个用于第一个项目,另一个用于下一个项目.每当下一个项目是您正在寻找的项目的EQL时,然后将第一个项目推送到结果列表(如果它不是那里的成员).
对于递归版本,我会写一个由PRECEDERS调用的第二个函数,它接受两个以0和1开头的索引变量,然后使用它.我不打电话给POSITION.通常这个函数是通过PRECEDERS中的LABELS的本地函数,但是为了使它更容易编写,辅助函数也可以在外面.
(defun preceders (item vector
&key (start 0) (end (length vector))
(test #'eql))
(preceders-aux item vector start end test start (1+ start) nil))
(defun preceders-aux (item vector start end test pos0 pos1 result)
(if (>= pos1 end)
result
...
))
这有帮助吗？
这是使用LOOP的迭代版本:
(defun preceders (item vector
&key (start 0) (end (length vector))
(test #'eql))
(let ((result nil))
(loop for i from (1+ start) below end
when (funcall test item (aref vector i))
do (pushnew (aref vector (1- i)) result))
(nreverse result)))
既然你已经有了一个有效的解决方案,我将放大Rainer Joswig的解决方案,主要是为了做出相关的风格评论.
(defun preceders (obj seq &key (start 0) (end (length seq)) (test #'eql))
(%preceders obj seq nil start end test))
具有单独辅助函数的主要原因(我称之为%PRECEDERS,指示函数是"私有"的常用约定)是消除结果的可选参数.一般来说使用可选参数很好,但是可选和关键字参数可以一起播放,并且在单个函数中同时使用它们是创建各种难以调试错误的极其有效的方法.
无论是使辅助函数全局(使用DEFUN)还是本地(使用LABELS)都是一种品味问题.我更喜欢将其设为全局,因为它意味着更少的缩进和更容易的交互式调试.因人而异.
辅助函数的可能实现是:
(defun %preceders (obj seq result start end test)
(let ((pos (position obj seq :start start :end end :test test)))
;; Use a local binding for POS, to make it clear that you want the
;; same thing every time, and to cache the result of a potentially
;; expensive operation.
(cond ((null pos) (delete-duplicates (nreverse result) :test test))
((zerop pos) (%preceders obj seq result (1+ pos) end test))
;; I like ZEROP better than (= 0 ...). YMMV.
(t (%preceders obj seq
(cons (elt seq (1- pos)) result)
;; The other little bit of work to make things
;; tail-recursive.
(1+ pos) end test)))))
而且,毕竟,我想我应该指出,我也同意Rainer的建议,即使用显式循环而不是递归,只要递归地执行它不是练习的一部分.
编辑:我切换到辅助函数更常见的"%"约定.通常,您使用的任何约定都会增加以下事实:您只显式导出构成公共接口的函数,但某些标准函数和宏使用尾随"*"来表示变体功能.
我改变了使用标准DELETE-DUPLICATES函数删除重复的先行者的事情.这必须是潜在的多(即,指数)比的重复使用更快ADJOIN或PUSHNEW,因为它可以使用一个散列集表示在内部,至少对于像常见的测试功能EQ,EQL和EQUAL.