在Common Lisp中通过引用(而不是值)传递子数组

3

假设我有一个数组,我会叫它*my-array*,看起来像这样:

#2A((1 2 3)
    (4 5 6)
    (7 8 9))

我希望你能在子数组上应用一些函数f。

#2A((5 6)
    (8 9))

我希望能够写出优秀的技术文章

(f (subarray *my-array* '(1 2) '(1 2))

subarray作为参数传递,需要包含以下内容:

  • 原始数组
  • 一个包含起始点和结束点的2元列表,表示在第一维上的范围
  • 另一个包含起始点和结束点的2元列表,表示在第二维上的范围
  • 等等

我正在寻找一种将subarray以引用(或指针?)的方式传递给函数f而不是按值传递。

(解决这个问题的笨方法是编写一个函数,在这种特定情况下创建一个2*2数组并循环i和j从原始数组复制值。但是,如果你处理相对较大的数组,这将非常昂贵。)

我发现已经有一个cl-slice包,但我不确定它是复制值还是通过引用访问数据。


你确定数组是按值传递的吗? - Will Ness
1
@WillNess OP并没有说数组是按值传递的。但是如果有人想要将多维数组的子集作为另一个(可能是多维的)数组,那么这些元素必须被复制。 - coredump
如果我编写一个子数组函数来创建一个n*m的二维数组(在我的例子中,n=m=2),并循环i和j从原始数组复制值,我几乎可以确定数组将按值传递。 - Danny Zuko
1
@DannyZuko 所有东西都是按值传递的,但这个值可以是原始类型(如整数、字符),也可以是指向某些内存的隐式指针(如数组、结构体),在这种情况下,你将共享对原始数组及其副本中相同元素的引用。 - coredump
@coredump 但我并不是在询问,而是提供了一个 ideone 条目的链接,该条目清楚地显示数组是按引用传递的。 :) -- 你的答案列出了(共享的)子数组列表,对吧?我认为即使这样做也是多余的。将它们放入向量中的添加很好。 - Will Ness
显示剩余4条评论
3个回答

6

Common Lisp有Displaced Arrays,这正是你所询问的内容(请参阅array-displacement等)。

然而,在你的情况下,位移数组没有帮助,因为

多维数组将其组件按行主序存储;也就是说,多维数组在内部被存储为一维数组,其中多维索引集按字典顺序排序,最后一个索引变化最快。

这意味着你的子数组不是主数组的连续部分,因此你不能创建另一个位移数组。

附:如果你无法弄清楚cl-slice的工作原理,可以使用time查看它使用了多少内存,并从中推断出结论。

另外,实际上制作出类似你想要的东西并不太难:

(defmacro slice (array &rest ranges)
  "Return an accessor into ARRAY randing in RANGES."
  (let ((args (loop for r in ranges collect (gensym "SLICE-ARG-")))
        (arr (gensym "SLICE-ARRAY-")))
    `(let ((,arr ,array))
       (lambda ,args
         (aref ,arr
               ,@(loop for arg in args and (lo hi) in ranges
                   for range = (- hi lo)
                   collect
                     `(progn
                        (unless (<= 0 ,arg ,range)
                          (error "~S is out of range [0;~S]" ,arg ,range))
                        (+ ,lo ,arg))))))))

(defparameter *my-array*
  #2A((1 2 3)
      (4 5 6)
      (7 8 9)))

(defparameter f (slice *my-array* (1 2) (1 2)))

(loop for i from 0 to 1 do
    (loop for j from 0 to 1 do
        (format t " ~S" (funcall f i j)))
    (terpri))
 5 6
 8 9

你可以写成 (lo hi) in ranges 的形式;此外,如果给定的范围比维度少,也可以让匿名 lambda 接受 &rest others 参数,并使用 (apply #'aref ,@(...) others)。顺便说一下,这是一个不错的宏。 - coredump
是的,你可以写那个,但它并不意味着我想要的。此外,我喜欢宏执行隐式错误检查的事实。 - sds
我感到困惑。你有没有一个例子,其中使用 first/second 或解构会导致结果不同? - coredump
1
看起来你是对的(我在宏的早期版本中尝试过解构,但它没有起作用 - 现在我意识到原因不同)。谢谢。 - sds

4

正如其他人指出的那样,您不能使用位移数组来表示矩阵(也许可以使用非标准函数)。但是您需要做的就是改变与原始数组的交互方式。以下是一些可能的选择。

位移数组序列

(defun area (matrix tlx tly brx bry)
  ;; you may also want to check that all coordinates are valid
  ;; inside current matrix. You could generalize this function for
  ;; more dimensions.
  (assert (<= tlx tly))
  (assert (<= brx bry))
  (loop
     for y from tly upto bry
     collect (make-array (1+ (- brx tlx))
             :displaced-to matrix
             :displaced-index-offset
             (array-row-major-index matrix y tlx))))

(tl 意思是左上角,br 意思是右下角)。

接着,假设你将矩阵定义如下:

(defparameter *matrix* #2A((1 2 3)
                           (4 5 6)
                           (7 8 9)))

...子矩阵的获取方法如下:

(area *matrix* 1 1 2 2)
=> (#(5 6) #(8 9))

...并且可以像这样访问:

(aref (nth ROW *) COL)

任何对*matrix*的更改都会反映在两个被替换的数组中之一,反之亦然。但是,如果您将结果列表强制转换为vector,那么您将获得一个数组向量。这与多维数组不同,但为您提供了行的常数时间访问:
(aref (aref area ROW) COL)

包装器闭包

提供原矩阵受限视图的另一种方法是创建一个访问函数,该函数仅适用于感兴趣的范围:

(defun sub-matrix (matrix tlx tly brx bry)
  ;; again, you should do more checks
  (assert (<= tlx tly))
  (assert (<= brx bry))
  (lambda (x y &optional (value nil valuep))
    (incf x tlx)
    (incf y tly)
    (assert (<= tlx x brx))
    (assert (<= tly y bry))
    (if valuep
        (setf (aref matrix y x) value)
        (aref matrix y x))))

这将返回一个闭包函数,接受 2 或 3 个参数。前两个参数是相对于内部矩阵的 xy 坐标。当给定第三个参数时,闭包函数会 设置 值。否则,它 获取 值。

这可以进一步泛化。我部分参考了 sds 的答案,但尝试以稍微不同的方式进行处理;这里我可以生成设置器或获取器函数。在创建函数之前和执行已创建的函数期间,我还添加了一些检查:

(defun slice-accessor (array ranges mode)
  (let* ((dimensions (array-dimensions array))
         (max-length (length dimensions)))
    (check-type array array)
    (loop
       with r = (copy-list ranges)
       for range = (pop r)
       for (lo hi) = range
       for d in dimensions
       for x from 0
       for $index = (gensym x)
       collect $index into $indices
       when range
       do (assert (<= 0 lo hi d))
       and collect `(check-type ,$index (integer 0 ,(- hi lo))) into checks
       and collect `(incf ,$index ,lo) into increments
       finally (let ((body `(apply #'aref ,array ,@$indices ())))
                 (return
                   (compile nil
                    (ecase mode
                      (:read `(lambda ,$indices
                                ,@checks
                                ,@increments
                                ,body))

                      (:write (let (($v (make-symbol "VALUE")))
                                `(lambda (,$v ,@$indices)
                                   (check-type ,$v ,(array-element-type array))
                                   ,@checks
                                   ,@increments
                                   (setf ,body ,$v)))))))))))

CLOS

一旦您拥有上述内容,就可以通过对象提供一个漂亮的界面。每当我们更改范围或被切片的数组时,setter和getter函数都会更新:

(defclass array-slice ()
  ((array :initarg :array :accessor reference-array)
   (ranges :initarg :ranges :accessor slice-ranges :initform nil)
   (%fast-getter :accessor %fast-getter)
   (%fast-setter :accessor %fast-setter)))

(flet ((update-fast-calls (o)
         (setf (%fast-setter o)
               (slice-accessor (reference-array o) (slice-ranges o) :write)

               (%fast-getter o)
               (slice-accessor (reference-array o) (slice-ranges o) :read))))

  (defmethod initialize-instance :after ((o array-slice) &rest k)
             (declare (ignore k))
             (update-fast-calls o))

  (defmethod (setf reference-array) :after (new-array (o array-slice))
             (declare (ignore new-array))
             (update-fast-calls o))

  (defmethod (setf slice-ranges) :after (new-ranges (o array-slice))
             (declare (ignore new-ranges))
             (update-fast-calls o)))  

(defgeneric slice-aref (slice &rest indices)
  (:method ((o array-slice) &rest indices)
    (apply (%fast-getter o) indices)))

(defgeneric (setf slice-aref) (new-value slice &rest indices)
  (:method (new-value (o array-slice) &rest indices)
    (apply (%fast-setter o) new-value indices)))

示例

(defparameter *slice*
  (make-instance 'array-slice :array *matrix*))

;; no range by default
(slice-aref *slice* 0 0)
=> 1

;; update ranges
(setf (slice-ranges *slice*) '((1 2) (1 2)))

(slice-aref *slice* 0 0)
=> 5

(incf (slice-aref *slice* 0 0) 10)
=> 15

*matrix*
=> #2A((1 2 3) (4 15 6) (7 8 9))

;; change array
(setf (reference-array *slice*) (make-array '(3 3) :initial-element -1))

(slice-aref *slice* 0 0)
=> -1

3

我不认为你想要做的事情是可能的。在内存中,多维数组被实现为一个单一的平面数组,其中包含一些元数据用于将多维接口转换为平面接口。在你的情况下,*my-array*看起来像这样:

#(1 2 3 4 5 6 7 8 9)

如果您想要一个子数组作为原始数组的参考,它将如下所示:
#(5 6 _ 8 9)

这是不可能的,因为您正在尝试跳过原始数组中的7。如果所有所需元素都是连续的子序列的一部分,您将能够使用make-array:displaced-to参数按引用复制子序列,但不幸的是,情况并非如此。


4
顺便提一下:Kalman Reti展示了如何在Lisp Machine上实现这一点。请从视频的10:20开始观看。它允许位移2D光栅数组...... https://www.youtube.com/watch?v=o4-YnLpLgtk - Rainer Joswig

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接