通用Lisp: delete-if和setf + remove-if是一样的吗？

Question

以下代码生成从1到n的质数：

(defun prime-list(n)
  (let ((a)(b)(x (floor (sqrt n))))
    (loop for i from (floor n 6) downto 1 do
          (push (1+ (* 6 i)) a)
          (push (1- (* 6 i)) a))
    (loop while (<= (car a) x) do
          (push (car a) b)
          (setf a (remove-if #'(lambda(m)(or (= 0 (mod m (car a))) (> m n))) a)))
    (append '(2 3) (reverse b) a)))

It seems to me the part

(setf a (remove-if #'XXX a)) 

可以被替换为

(delete-if #'XXX a)

我希望这样做能够加快速度。然而，当我进行了更改后，该函数进入了无限循环，永远不会返回。为什么会这样呢？

- h__

---

错误1： 应该是 while (<= (car a) x)。 错误2： 由于任何质数都可以表示为 6i+-1 的形式，因此任何质数的平方模6余1。如果对于某个质数 p，有 n == p^2-1，则有 n == 6i 对于某个 i 成立。Q 中的代码将 6i+1 == p^2 加入到列表中；但是会通过 x = sqrt(n) < p 进行测试，因此会将 p^2 包含在输出中。因此，当使用 n=p^2-1 调用时，上述代码将产生 p^2 作为其输出中的最后一个元素。（我没有编辑这个原因是 Q 不涉及代码的有效性）。 - Will Ness

另外，这是一种试除法筛选算法，比厄拉多塞筛法效率低得多（后者会“按等差递增的方式”找到倍数，而不是通过除法测试）。 - Will Ness

@WillNess 确实。我当时只是在玩，没有考虑效率。后来我使用了位数组，你可以在这里找到代码：http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Common_Lisp（第二个。欢迎评论。） - h__

明白了。我只是为了普通读者的好处做个记录。（错误1已经修复；错误2仍然存在）。 - Will Ness

@WillNess已更改。但这可能不是修复它的最佳方法。;) - h__

Answer 1

如评论中所提到的，您需要设置变量。 DELETE-IF 是 REMOVE-IF 的破坏性版本。 REMOVE-IF 返回一个新建的序列，其中不包含已删除的元素。 DELETE-IF 可能返回一个被重用的序列。

如果您有一个绑定到列表的变量，仍然需要设置结果。上述函数返回结果，但它们不会将变量设置为结果。在列表的情况下，DELETE-IF 操作的结果可以是空列表，并且当它指向非空列表时，没有办法将副作用设置为变量可以指向它的情况。

- Rainer Joswig

---

此外，当需要移除第一个元素时，返回的值总是与原序列不同（在仍然具有对该 cons 的指针的情况下，没有明智的方法可以手术式地移除列表的第一个 cons，因此返回第一个未被移除的 cons）。 - Vatine

Answer 2

我没有太多的CL经验，但我在Scheme方面做了很多工作。

在第二个版本（不带setf a），remove-if表达式被评估，但它实际上并没有改变a。loop是CL中的一个宏，它只评估表达式，但不像递归函数那样使用这些表达式的结果。

因此，在第一个版本中，由于setf，每次循环运行时a的值都会改变，但在第二个版本中，a的值始终保持不变。因此(car a)永远不会改变，循环永远不会终止。

我们可以比较一下两个loop语句的macroexpand结果：

不带setf：

(MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
 (BLOCK NIL
  (LET NIL
   (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
    (TAGBODY SYSTEM::BEGIN-LOOP
     (PROGN (UNLESS (< (CAR A) X) (LOOP-FINISH))
      (PROGN (PUSH (CAR A) B) (REMOVE-IF #'(LAMBDA (M) (= 0 (MOD M (CAR A)))) A)))
     (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
     (MACROLET
      ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN) '(GO SYSTEM::END-LOOP))))))))) ;

使用setf：

(MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
 (BLOCK NIL
  (LET NIL
   (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
    (TAGBODY SYSTEM::BEGIN-LOOP
     (PROGN (UNLESS (< (CAR A) X) (LOOP-FINISH))
      (PROGN (PUSH (CAR A) B)
       (SETF A (REMOVE-IF #'(LAMBDA (M) (= 0 (MOD M (CAR A))))) A)))
     (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
     (MACROLET
      ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN) '(GO SYSTEM::END-LOOP))))))))) ;

你可以看到在第一个循环中，remove-if表达式被评估了，但它的结果没有被使用。

- cdk

---

哎呀，我想我问错问题了，我的意思是"(setf a (remove-if #'XXX a))可以被替换为(delete-if #'XXX a)"。 - h__

Answer 3

克里斯是正确的。

你可以使用delete-if代替remove-if来加快速度。

- Doug Currie

---

抱歉，我的意思是询问delete-if（我在标题中写了delete-if），我发现delete-if不起作用。我正在使用Lispworks，当我尝试delete-if时，发生了一些非常奇怪的事情：即使第一个条目应该被删除，delete if也不会删除第一个条目。请参见链接：https://dl.dropbox.com/u/9034084/Screen-shot%203.png - h__

你仍然需要使用 setf：(setf foo (delete-if #'some-pred foo))。 - Hugh

你仍然需要 (setq a (delete-if ...)。 - Doug Currie