Suppose I have a simple-array (rank not known beforehand), and I want
to traverse its elements in column-major order (for example, I want to
print the elements, or do something like reduce, etc).
If the rank was known beforehand, I would simply write nested loops
with dotimes, but I am looking for a general solution.
Thanks,
Tamas
On Aug 9, 5:40 pm, Tamas Papp <······@gmail.com> wrote:
> Suppose I have a simple-array (rank not known beforehand), and I want
> to traverse its elements in column-major order (for example, I want to
> print the elements, or do something like reduce, etc).
>From the message it is not clear whether you know about the prescribed
storage model for multidimensional arrays, which is row-major order.
http://www.lisp.org/HyperSpec/Body/sec_15-1-1-3-2-1.html
If you knew about this but want column-major order, then I can't help
you. But if row-major is also acceptible because you just want a way
to access elements one by one, this is possible: create a 1-
dimensional array displaced to the original array, and loop across the
vector. Look up the :displaced-to argument of make-array, and function
array-total-size.
Apropos, O'Reilly has just published an enjoyable book titled
"Beautiful Code", and in there is a chapter by Travis E. Oliphant on
implementing iterators for subarrays of multi-dimensional arrays, as
part of NumPy (numerical lib for Python).
http://www.oreilly.com/catalog/9780596510046/toc.html
ISBN 10: 0-596-51004-7
ISBN 13: 9780596510046
- Willem
From: Thomas A. Russ
Subject: Re: algorithm question: how to traverse an array column-major
Date:
Message-ID: <ymips1w49z7.fsf@blackcat.isi.edu>
Willem Broekema <········@gmail.com> writes:
> On Aug 9, 5:40 pm, Tamas Papp <······@gmail.com> wrote:
> > Suppose I have a simple-array (rank not known beforehand), and I want
> > to traverse its elements in column-major order (for example, I want to
> > print the elements, or do something like reduce, etc).
>
> >From the message it is not clear whether you know about the prescribed
> storage model for multidimensional arrays, which is row-major order.
>
> http://www.lisp.org/HyperSpec/Body/sec_15-1-1-3-2-1.html
>
> If you knew about this but want column-major order, then I can't help
> you. But if row-major is also acceptible because you just want a way
> to access elements one by one, this is possible: create a 1-
> dimensional array displaced to the original array, and loop across the
> vector. Look up the :displaced-to argument of make-array, and function
> array-total-size.
Even easier is to use ROW-MAJOR-AREF together with ARRAY-TOTAL-SIZE.
--
Thomas A. Russ, USC/Information Sciences Institute
Hi,
I wonder whether the following, which I arrived at by pure
experimentation and with the least amount of reasoning possible, is
completely broken :)
(defun column-major-aref (a i)
(apply #'aref a
(nreverse (loop for dimension in (reverse (array-dimensions
a))
for dim-no downfrom (1- (array-rank a))
for mod-size = (reduce #'* (butlast (array-
dimensions a)))
then (/ mod-size (array-dimension a dim-
no))
collect (truncate i mod-size)
do (setf i (mod i mod-size))))))
It wouldn't surprise me to see that this is complete nonsense. I have
to admit I'm actually not sure I understand what exactly COLUMN-MAJOR-
AREF is supposed to do.
SEQUENCES> (let ((a #2A((1 2 3 4) (5 6 7 8) (9 10 11 12))))
(format nil "~{~A~^, ~}" (loop for i from 0 to (1- (array-
total-size a))
collect (column-major-aref
a i))))
"1, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8, 12"
SEQUENCES> (let ((a #3A(((1 2 3 4) (5 6 7 8) (9 10 11 12)) ((13 14 15
16) (17 18 19 20) (21 22 23 24)))))
(format nil "~{~A~^, ~}" (loop for i from 0 to (1- (array-
total-size a))
collect (column-major-aref
a i))))
"1, 13, 5, 17, 9, 21, 2, 14, 6, 18, 10, 22, 3, 15, 7, 19, 11, 23, 4,
16, 8, 20, 12, 24"
Mata ne,
Matthias
From: Pascal Bourguignon
Subject: Re: algorithm question: how to traverse an array column-major
Date:
Message-ID: <87y7gkjrlh.fsf@informatimago.com>
Tamas Papp <······@gmail.com> writes:
> Suppose I have a simple-array (rank not known beforehand), and I want
> to traverse its elements in column-major order (for example, I want to
> print the elements, or do something like reduce, etc).
>
> If the rank was known beforehand, I would simply write nested loops
> with dotimes, but I am looking for a general solution.
I already have this macro:
(defmacro rloop (clauses &rest body)
(if (null clauses)
`(progn ,@body)
`(loop ,@(car clauses) do (rloop ,(cdr clauses) ,@body))))
(rloop ((for i from 0 to 3)
(for j from 0 to 3)
(for k from 0 to 3))
(print (aref array i j k)))
But you want column-major, so:
(rloop ((for i from 0 to 3)
(for j from 0 to 3)
(for k from 0 to 3))
(print (aref array k j i)))
Now the real problem is to build these embedded loops at run-time,
since you don't know before hand the dimensions of the array. One
quick and dirty solution is to keep the macro, and use EVAL:
(let ((indices (loop repeat (length (array-dimensions array)) collect (gensym))))
(eval `(rloop ,(mapcar (lambda (index dimension)
`(for ,index from 0 below ,dimension))
indices (array-dimensions array))
(print (aref array ,@(reverse indices))))))
Of course, it's not a good idea to use eval, since the body (the
"print") will probably need to refer to some lexical variables.
What you need to implement, is an iterator.
(defun make-column-major-iterator (array)
(let* ((dims (coerce (array-dimensions array) 'vector))
(indices (make-list (length dims) :initial-element 0))
(done nil))
(lambda ()
(if done
(values nil nil)
(multiple-value-prog1 (values (apply (function aref) array indices) t)
(loop
:for i :from 0 :below (length dims)
:for index :on indices
:do (incf (car index))
:while (= (car index) (aref dims i))
:do (setf (car index) 0)
:finally (setf done (<= (length dims) i))))))))
C/CV[90]> (let ((a #3A(((1 2 3) (4 5 6)) ((7 8 9) (10 11 12)))))
(loop with iter = (make-column-major-iterator a)
for (i p) = (multiple-value-list (funcall iter))
while p
do (print i)))
1
7
4
10
2
8
5
11
3
9
6
12
NIL
C/CV[91]>
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Aug 9, 5:40 pm, Tamas Papp <······@gmail.com> wrote:
> Suppose I have a simple-array (rank not known beforehand), and I want
> to traverse its elements in column-major order (for example, I want to
> print the elements, or do something like reduce, etc).
>
> If the rank was known beforehand, I would simply write nested loops
> with dotimes, but I am looking for a general solution.
I would do it by converting the column-major number to a row-major
one. Something like the following:
(defun column-major-accessor (array)
(let* ((dims (array-dimensions array))
(rdims (reverse dims))
(rm-scales (reverse (maplist (lambda (l) (apply #'* (or (cdr l)
'(1))))
dims)))
(cm-scales (maplist (lambda (l) (apply #'* (or (cdr l) '(1))))
rdims)))
(labels ((ref (i)
(row-major-aref
array
(loop with source = i
with result = 0
for rm in rm-scales
for cm in cm-scales
do (multiple-value-bind (dim rest) (floor source cm)
(setf result (+ result (* dim rm))
source rest))
finally (return result)))))
#'ref)))
On 9 Aug, 16:40, Tamas Papp <······@gmail.com> wrote:
> Suppose I have a simple-array (rank not known beforehand), and I want
> to traverse its elements in column-major order (for example, I want to
> print the elements, or do something like reduce, etc).
>
> If the rank was known beforehand, I would simply write nested loops
> with dotimes, but I am looking for a general solution.
>
> Thanks,
>
> Tamas
Given an array, you can write a do loop something like this:
(do init-clause
((= (last counter) (last (array-dimensions array))))
...body...
(incf (Aref counter 0))
(dotimes (tick (array-rank array)
(if (= (elt counter tick) (elt (array-dimensions array) tick))
(progn
(setf (elt counter tick) 0)
(incf (elt counter (1+ tick))))
(return)))))))
Where array is your array, and counter a list of your current
position.
You can then access the appropriate element inside the loop with
(apply #'aref array counter)
The all-singing, all-dancing macro I used to implement a base layer
for APL/J style array access is below.
But it's uncommented, needs rewriting, and probably overkill for what
you need.
However it should be relatively obvious how it is used, upper-bound,
init and lower-bound all take arrays as arguments and array can be
either the name of an array used to keep track of where you are or a
list of individual bindings for the co-ordinates.
Apologies for google groups destructuring of whitespace.
(defmacro meta-dotimes((array upper-bound &key (init nil) (lower-bound
nil) (reverse nil) (increment 1)) &rest body)
(let* ((last (gensym)) (final (gensym)) (tick (gensym)) (lower
(gensym)) (temp (gensym)) (upper (gensym))
(lbound (if (null lower-bound)
`(:initial-element ,(if reverse -1 0) :element-type 'fixnum)
`(:initial-contenets ,(if reverse `(mapcar #'1- ,lower-bound)
lower-bound) :element-type 'fixnum)))
(int (if (null init)
(if reverse
`(:initial-contents (mapcar #'1- ,temp) :element-type
'fixnum)
`(:initial-element 0 :element-type 'fixnum))
`(:initial-contents ,init :element-type 'fixnum)))
(name-binds))
(when (listp array)
(let ((tick -1) (new-array-name (gensym)))
(setf name-binds (mapcar (lambda(x) (list x (list 'aref new-array-
name (incf tick)) (list 'aref new-array-name tick)) array))
(setf array new-array-name)))
(when reverse
(! - increment))
`(do* ((,temp ,upper-bound)
(,last (1- (length ,temp)))
(,upper ,(if reverse
`(make-array (1+ ,last) ,@lbound)
`(make-array (length ,temp) :initial-contents ,temp :element-type
'fixnum)))
(,lower ,(if reverse
`(make-array (length ,temp) :initial-contents (mapcar
#'1- ,temp) :element-type 'fixnum)
`(make-array (1+ ,last) ,@lbound)))
(,array (make-array (1+ ,last) ,@int))
,@name-binds
(,final (elt ,upper ,last)))
((= (aref ,array ,last) ,final))
,@body
(incf (Aref ,array 0) ,increment)
(dotimes (,tick ,last)
(if (= (aref ,array ,tick) (aref ,upper ,tick))
(progn
(setf (aref ,array ,tick) (aref ,lower ,tick))
(incf (Aref ,array (1+ ,tick)) ,increment))
(return))))))