lisp - 函数内的 DELETE + SETF

标签 lisp common-lisp

我正在尝试编写一个函数,该函数将从列表中破坏性地删除 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 无法正常工作(即,如果我改用 REMOVEFOO 根本不会改变)。

是否存在我不知道的任何范围规则?

最佳答案

(正确的)列表由 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/

相关文章:

list - 常用 lisp 函数中的表达式和算术

LISP 回溯

c - 如何以编程方式写下这个数学表达式?

方案:列表计数器

common-lisp - 如何在 sbcl (common-lisp) 中使用 sb-ext :run-program? 的参数

lisp - 作为函数参数传递时如何停止评估 lisp 形式?

macros - 宏发出 : Eval of a macro body works, 但宏没有

common-lisp - 无论如何, "probe"是普通 lisp 中的一种方法吗?

lisp - 为什么 uninterned 符号用于 Common Lisp 中的包名和导出?

lisp - 子集总和 - lisp