函数内的 DELETE + SETF

Question

我正在尝试编写一个函数，该函数将破坏性地从列表中删除 N 个元素并 return 个元素。我想出的代码（见下文）看起来不错，除了 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

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

delete, delete-if, and delete-if-not return a sequence of the same type as sequence that has the same elements except that those in the subsequence bounded by start and end and satisfying the test have been deleted. Sequence may be destroyed and used to construct the result; however, the result might or might not be identical to sequence.

例如，在 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 保持旧值。

Answer 2

删除不是要求修改任何结构，只是允许。事实上，您不能总是进行破坏性删除。如果你想从(42)中删除42，你需要return空列表()，这是符号NIL，但是你没办法把列表(42)，这是一个cons 单元格 (42 . NIL) 变成不同类型的对象（符号 NIL）。因此，您可能需要 return 更新后的列表以及删除的元素。你可以用这样的东西来做到这一点，returns 多个值：

(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

在接收端，您需要使用诸如多值绑定或多值设置q之类的东西：

(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

一个（正确的）列表由 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 所看到的内容没有影响。

您需要实际更新有问题的变量绑定。你可以这样做通过将其设置为由函数编辑的值 return。既然你已经 return 不同的值，这将是一个额外的 return 值。

(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) 总体运行时间当前项目同时在列表中线性运行。然后你收集项目进入选择或休息列表。

(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))))

函数内的 DELETE + SETF

DELETE + SETF inside a function

lisp

common-lisp