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

wheresubarray作为参数:

  • 原始数组
  • 一个 2 元素列表,起点和终点在第一维
  • 另一个 2 元素列表,起点和终点在第二维
  • 等等

我正在寻找某种方法f 通过引用(或通过指针?)而不是通过值将子数组作为参数传递给函数。

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

我发现存在一个cl-slice包,但我不知道它是复制值还是通过引用访问数据。

4

3 回答 3

6

Common Lisp 有置换数组,这正是您要问的(参见array-displacement&c)。

但是,在您的情况下,置换数组没有帮助,因为

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

这意味着您的子数组不是主数组的连续部分,因此,您不能创建另一个替换它的数组。

PS。如果您无法弄清楚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
于 2015-08-18T16:00:51.380 回答
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*都会反映在两个移位数组之一中,反之亦然。 但是,如果您将结果列表强制为 a 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 的回答的启发,但尝试做一些不同的事情;在这里,我可以生成一个 setter 或一个 getter 函数。我还在创建函数之前和执行创建的函数期间添加了一些检查:

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

克洛斯

一旦你有了以上这些,你就可以通过对象提供一个很好的接口。每当我们更改范围或被切片的数组时,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
于 2015-08-18T16:16:44.100 回答
3

我认为不可能完全按照您的意愿去做。在内存中,多维数组被实现为带有一些元数据的单个平面数组,这些元数据用于从多维接口转换为平面接口。在你的情况下*my-array*看起来像这样:

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

如果您将所需的子数组作为对原始数组的引用,它将如下所示:

#(5 6 _ 8 9)

这是不可能的,因为您试图跳过7原始数组的。如果所有需要的元素都是连续子序列的一部分,则可以使用:displaced-to参数 ofmake-array以通过引用复制子序列,但不幸的是,情况并非如此。

于 2015-08-18T16:01:15.950 回答