我正在尝试编写一个函数,该函数将从列表中破坏性地删除 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
根本不会改变)。
是否存在我不知道的任何范围规则?
最佳答案
(正确的)列表由 cons 单元格组成,每个单元格都包含对下一个的引用
细胞。所以,它实际上是一个引用链,你的变量有一个
引用第一个单元格。为了清楚起见,我将绑定(bind)重命名为外部
你的函数到 var
:
var ---> [a|]--->[b|]--->[c|nil]
当你将变量的值传递给你的函数时,参数得到 绑定(bind)到相同的引用。
var ---> [a|]--->[b|]--->[c|nil]
/
from --'
您可以更新链中的引用,例如删除b
:
var ---> [a|]--->[c|nil]
/
from --'
这对 var
在外部看到的列表有影响。
如果您更改第一个引用,例如删除 a
,这只是
一个来自 from
:
var ---> [a|]--->[b|]--->[c|nil]
/
from --'
这显然对 var
看到的内容没有影响。
您需要实际更新有问题的变量绑定(bind)。你可以这样做 通过将其设置为函数返回的值。因为你已经返回了 不同的值,这将是一个额外的返回值。
(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))))
关于lisp - 函数内的 DELETE + SETF,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33423155/