我试图在Lisp中反转列表,但出现错误:“错误:异常C0000005 [flags 0] at 20303FF3 {Offset 25 inside#} eax 108 ebx 200925CA ecx 200 edx 2EFDD4D esp 2EFDCC8 ebp 2EFDCE0 esi 628 edi 628 ”
我的代码如下:
(defun rev (l)
(cond
((null l) '())
(T (append (rev (cdr l)) (list (car l))))))
谁能告诉我我在做什么错?提前致谢!
您编写的代码在逻辑上是正确的,并且会产生想要的结果:
CL-USER> (defun rev (l)
(cond
((null l) '())
(T (append (rev (cdr l)) (list (car l))))))
REV
CL-USER> (rev '(1 2 3 4))
(4 3 2 1)
CL-USER> (rev '())
NIL
CL-USER> (rev '(1 2))
(2 1)
也就是说,在性能方面存在一些问题。在附加功能产生的所有副本,但其最终的说法。例如,当您执行(追加'(1 2)'(ab)'(3 4))时,您将创建四个新的con单元格,它们的汽车分别为1,2,a和b。最后一个的cdr是现有列表(3 4)。这是因为append的实现是这样的:
(defun append (l1 l2)
(if (null l1)
l2
(cons (first l1)
(append (rest l1)
l2))))
那不是Common Lisp的append,因为Common Lisp的append可以接受两个以上的参数。它足够接近,足以说明为什么复制除最后一个列表以外的所有列表。现在来看一下对rev的实现意味着什么:
(defun rev (l)
(cond
((null l) '())
(T (append (rev (cdr l)) (list (car l))))))
这意味着当您反转(1 2 3 4)之类的列表时,就好像您在:
(append '(4 3 2) '(1)) ; as a result of (1)
(append (append '(4 3) '(2)) '(1)) ; and so on... (2)
现在,在第(2)行中,您正在复制列表(4 3)。在第一行中,您正在复制列表(4 3 2),其中包括(4 3)的副本。也就是说,您正在复制一个副本。那是对内存的非常浪费的使用。
一种更常见的方法是使用累加器变量和辅助函数。(请注意,我使用endp,rest,first和list *而不是null,cdr,car和cons,因为它使我们更清楚地知道我们正在使用列表,而不是任意的cons树。它们几乎是相同(但有一些区别)。
(defun rev-helper (list reversed)
"A helper function for reversing a list. Returns a new list
containing the elements of LIST in reverse order, followed by the
elements in REVERSED. (So, when REVERSED is the empty list, returns
exactly a reversed copy of LIST.)"
(if (endp list)
reversed
(rev-helper (rest list)
(list* (first list)
reversed))))
CL-USER> (rev-helper '(1 2 3) '(4 5))
(3 2 1 4 5)
CL-USER> (rev-helper '(1 2 3) '())
(3 2 1)
使用此辅助函数,可以轻松定义rev:
(defun rev (list)
"Returns a new list containing the elements of LIST in reverse
order."
(rev-helper list '()))
CL-USER> (rev '(1 2 3))
(3 2 1)
也就是说,与其使用外部帮助器功能,不如使用标签来定义本地帮助器功能,这可能更常见:
(defun rev (list)
(labels ((rev-helper (list reversed)
#| ... |#))
(rev-helper list '())))
或者,由于不能保证Common Lisp可以优化尾调用,因此do循环在这里也很干净:
(defun rev (list)
(do ((list list (rest list))
(reversed '() (list* (first list) reversed)))
((endp list) reversed)))
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句