在函数中删除+ SETF

Question

我正在尝试编写一个函数，它将破坏性地从列表中删除N元素并返回它们。我想出的代码(见下文)看上去很好，但SETF的工作方式与我预期的不一样。

(defun pick (n from)
  "Deletes (destructively) n random items from FROM list and returns them"
  (loop with removed = nil
     for i below (min n (length from)) do
       (let ((to-delete (alexandria:random-elt from)))
         (setf from (delete to-delete from :count 1 :test #'equal)
               removed (nconc removed (list to-delete))))
     finally (return removed)))

在大多数情况下，这种方法工作得很好：

CL-USER> (defparameter foo (loop for i below 10 collect i))
CL-USER> (pick 3 foo)
(1 3 6)
CL-USER> foo
(0 2 4 5 7 8 9)
CL-USER> (pick 3 foo)
(8 7 0)
CL-USER> foo
(0 2 4 5 9)

如您所见，PICK工作得很好(在SBCL上)，除非选择的元素恰好是列表中的第一个元素。在这种情况下，它不会被删除。这是因为唯一的重新分配是在DELETE内部进行的。SETF不能正常工作(也就是说，如果我使用REMOVE，FOO根本不会改变)。

有没有我不知道的范围界定规则？

Answer 1

一个(适当的)列表由cons单元格组成，每个单元格都包含对下一个单元格的引用。因此，它实际上是一个引用链，您的变量有一个对第一个单元格的引用。为了澄清这一点，我将函数外部的绑定重命名为var。

var ---> [a|]--->[b|]--->[c|nil]

当将变量的值传递给函数时，参数将绑定到相同的引用。

var ---> [a|]--->[b|]--->[c|nil]
        /
from --'

您可以更新链中的引用，例如消除b

var ---> [a|]--->[c|nil]
        /
from --'

这对var在外部看到的列表有影响。

如果您更改了第一个引用，例如消除了a，这只是源自from的引用

var ---> [a|]--->[b|]--->[c|nil]
                /
        from --'

这显然对var所看到的没有任何影响。

您需要实际更新有关的变量绑定。您可以通过将其设置为函数返回的值来做到这一点。因为您已经返回了一个不同的值，所以这将是一个额外的返回值。

(defun pick (n list)
  (;; … separate picked and rest, then
    (values picked rest)))

然后您可以这样使用，例如：

(let ((var (list 1 2 3)))
  (multiple-value-bind (picked rest) (pick 2 var)
    (setf var rest)
    (do-something-with picked var)))

现在来谈谈分离:除非清单长得令人望而却步，否则我会坚持非破坏性操作。我也不会使用random-elt，因为每次都需要遍历O (m )元素(m是列表的大小)，因此运行时为O(n·m)。

您可以通过确定在列表中线性运行时选择当前项的当前机会来获得O(m)总体运行时。然后，将该项目收集到选中的列表或rest列表中。

(defun pick (n list)
  (loop :for e :in list
        :and l :downfrom (length list)
        :when (or (zerop n)
                  (>= (random 1.0) (/ n l)))
            :collect e :into rest
          :else
            :collect e :into picked
            :and :do (decf n)
        :finally (return (values picked rest))))

Answer 2

删除不需要修改任何结构，它只是允许。事实上，你不能总是做一个破坏性的删除。如果要从( 42 )中删除42，则需要返回空list ()，它是符号为零，但您无法将列表(42)转成一个cons单元格(42 )。进入不同类型的对象(符号为NIL)。因此，您可能需要返回更新后的列表以及删除的元素。您可以这样做，它返回多个值：

(defun pick (n from)
  (do ((elements '()))
      ((or (endp from) (zerop n))
       (values elements from))
    (let ((element (alexandria:random-elt from)))
      (setf from (delete element from)
            elements (list* element elements))
      (decf n))))

​

CL-USER> (pick 3 (list 1 2 3 2 3 4 4 5 6))
(2 6 4)
(1 3 3 5)
CL-USER> (pick 3 (list 1 2 3 4 5 6 7))
(2 7 5)
(1 3 4 6)
CL-USER> (pick 2 (list 1 2 3))
(2 3)
(1)
CL-USER> (pick 2 (list 1))
(1)
NIL

在接收端，您需要使用类似于多值绑定或多值setq的内容：

(let ((from (list 1 2 3 4 5 6 7)))
  (multiple-value-bind (removed from)
      (pick 2 from)
    (format t "removed: ~a, from: ~a" removed from)))
; removed: (7 4), from: (1 2 3 5 6)

​

(let ((from (list 1 2 3 4 5 6 7))
      (removed '()))
  (multiple-value-setq (removed from) (pick 2 from))
  (format t "removed: ~a, from: ~a" removed from))
; removed: (3 5), from: (1 2 4 6 7)

Answer 3

delete不一定修改其序列参数。正如超石化所说：

delete、delete-if和delete-if-not作为序列返回相同类型的序列，该序列具有相同的元素，但在受start和end限制并满足测试要求的子序列中的元素除外。序列可以被销毁并用于构造结果；但是，结果可能与序列相同，也可能不相同。

例如，在SBCL中：

* (defvar f (loop for i below 10 collect i))

F
* (defvar g (delete 0 f :count 1 :test #'equal))

G
* g

(1 2 3 4 5 6 7 8 9)

* f

(0 1 2 3 4 5 6 7 8 9)
*

注意，在您的函数中，setf修改局部变量from，并且由于delete在第一个元素的情况下不会修改原始列表，所以在函数的末尾，变量foo维护旧的值。