Передать подмассив по ссылке (не по значению) в Common Lisp
Давайте предположим, что у меня есть массив - который я назову *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 элементов с начальной и конечной точкой во 2-м измерении
- и т.п.
Я ищу способ передать подмассив в качестве аргумента функции f по ссылке (или по указателю?) вместо значения.
(Глупый способ решить эту проблему - написать функцию, которая создает (в данном конкретном случае) массив 2*2 и циклически повторяет значения i и j, копируя значения из исходного массива. Однако, если вы имеете дело с относительно большими массивами, это было бы довольно дорого.)
Я обнаружил, что существует cl-slice пакет, но я не понимаю, копирует ли он значения или обращается к данным по ссылке.
3 ответа
Common Lisp имеет смещенные массивы, которые именно то, о чем вы спрашиваете (см. array-displacement & С).
Однако в вашем случае массивы смещений не помогают, потому что:
Многомерные массивы хранят свои компоненты в порядке следования строк; то есть внутри многомерный массив хранится в виде одномерного массива с многомерными наборами индексов, упорядоченными лексикографически, причем последний индекс изменяется быстрее всего.
Это означает, что ваш подмассив не является непрерывным разделом вашего основного массива, и, таким образом, вы не можете создать другой массив, смещенный к нему.
PS. Если вы не можете понять, как работает cl-slice, вы можете использовать time чтобы увидеть, сколько памяти он использует, и сделать из этого вывод.
PPS. На самом деле, не так уж сложно собрать что-то вроде того, что вы хотите:
(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
Как отмечали другие, вы не можете использовать смещенные массивы для матриц (возможно, вы могли бы использовать нестандартные функции). Но все, что вам нужно, это изменить способ взаимодействия с исходным массивом. Вот несколько возможностей.
Последовательности смещенных массивов
(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 аргумента. Первые два аргумента x а также y координаты относительно внутренней матрицы. Когда дан третий аргумент, замыкание устанавливает значение. В противном случае он получает значение.
Это можно сделать более общим. Я был частично вдохновлен ответом 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
Я не думаю, что можно делать именно то, что вы хотите. В памяти многомерные массивы реализованы в виде единого плоского массива с некоторыми метаданными, который используется для преобразования из многомерного интерфейса в плоский. В твоем случае *my-array* будет выглядеть так:
#(1 2 3 4 5 6 7 8 9)
Если бы у вас был подмассив, который вы хотели использовать в качестве ссылки на исходный массив, он бы выглядел так:
#(5 6 _ 8 9)
Что невозможно, так как вы пытаетесь пропустить 7 оригинального массива. Если бы все нужные элементы были частью смежной подпоследовательности, вы могли бы использовать :displaced-to аргумент make-array для того, чтобы скопировать подпоследовательность по ссылке, но, к сожалению, это не так.