iteration over multidimensional array
Kent M Pitman
Sam Steingold <s...@usa.net> writes:
> to iterate over a 2-dim array AA, we do
>
> (let ((dims (array-dimensions AA)))
> (dotimes (ii (first dims)) (dotimes (jj (second dims)) do something)))
>
> what if the dimension (length (array-dimensions AA)) is unknown?
> how hard would it be to write ...
It would be hard to write something which knew the value of N indexes
without actually keeping N store cells and incrementing them.
HOWEVER, for most realistic applications that isn't what you need.
And you probably want ROW-MAJOR-AREF. e.g.,
(defun fillarray (to-array from-array)
(let ((s1 (array-total-size to-array))
(s2 (array-total-size from-array)))
(unless (= s1 s2) (error "The arrays are not of compatible size."))
(dotimes (i s1)
(setf (row-major-aref to-array i)
(row-major-aref from-array i)))))
Erann Gat
> to iterate over a 2-dim array AA, we do
>
> (let ((dims (array-dimensions AA)))
> (dotimes (ii (first dims)) (dotimes (jj (second dims)) do something)))
>
> what if the dimension (length (array-dimensions AA)) is unknown?
> how hard would it be to write a macro
You can't do it with a macro (at least not in any straightforward way)
because the array dimensions would need to be known when the macro
was expanded. But there are several ways to iterate over an arbitrary
array with a function. The most succinct is to create a one-dimensional
array displaced to the array over which you want to iterate, e.g.:
(defun iterate-array (fn a)
(map nil fn (make-array (apply #'* (array-dimensions a)) :displaced-to a)))
For example:
(iterate-array #'print #4a((((0 1) (2 3)) ((4 5) (6 7)))
(((8 9) (10 11)) ((12 13) (14 15)))))
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
NIL
Erann Gat
g...@jpl.nasa.gov
Furious activity is no substitute for understanding.
-- H. H. Williams
--
Erann Gat gat at jpl.nasa.gov or gat at jetcafe.org
Barry Margolin
In article <m3btucz...@mute.eaglets.com>,
Sam Steingold <s...@usa.net> wrote:
>1. array-row-major-index doesn't really need array as the first
>argument, it's array-dimensions should be enough. Why does it require an
>array?
Probably because it just seemed more natural to do it that way.
Array-total-size doesn't need the array, either, but it would seem silly to
call it that if all it does is (reduce #'* <arg>).
Some implementations may also optimize array index calculation, using
thunks associated with the array.
>2. How do I revert array-row-major-index? How do I get the index list
>from the row-major index? Is there a better way than this?
>
>(defun major-to-index (arr mi)
> (do ((dims (nreverse (array-dimensions arr)) (cdr dims)) res vv)
> ((endp dims) res)
> (setf (values mi vv) (floor mi (car dims)))
> (push vv res)))
I haven't checked the code for correctness, but it looks like the right
general approach. How often do you need to do this?
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Barry Margolin
In article <m3ra36y...@mute.eaglets.com>,
Sam Steingold <s...@usa.net> wrote:
>BTW, is it okay to modify the result of array-dimensions?
I was wondering the same thing when I saw your NREVERSE. Neither CLtL nor
the CLHS says that the list that ARRAY-DIMENSIONS returns is fresh, and I
can easily imagine an implementor using this as license to store a list in
the array object and simply return that list. So you should not depend on
being able to modify it.
>You see, this whole thing strikes me as unusual (I want to say
>"underdesigned", but I won't dare to :-). There is this function,
>array-row-major-index, which has an important and simple inverse,
>array-index-row-major (taking the array and the row-major index and
>returning the real indexes as multiple values), which is not specified
>by the standard.
For any language that supports arrays with dynamic sizes, the runtime
library has to include an operation to translate a list of indices to the
offset in memory, since most hardware only supports one-dimensional
indexing. So ARRAY-ROW-MAJOR-INDEX is simply an API into that existing
function that all Common Lisp implementations have to have. It's unusual
having to go the other way, so no one thought at the time that the opposite
function was needed.
What do you use it for?
Barry Margolin
In article <m3hg42z...@mute.eaglets.com>,
Sam Steingold <s...@usa.net> wrote:
>>>>> In a very interesting message
><bE8X.21$Fb2.3...@cam-news-reader1.bbnplanet.com>
>>>>> Sent on Thu, 09 Apr 1998 18:42:15 GMT
>>>>> Honorable Barry Margolin <bar...@bbnplanet.com> writes
>>>>> on the subject of "Re: iteration over multidimensional array":
> >>
> >> What do you use it for?
>
>
>(iterate (index-list '(1 2 3)) (print index-list))
> => prints:
> (0 0 0)
> (0 0 1)
> (0 0 2)
> (0 1 0)
> (0 1 1)
> (0 1 2)
This doesn't really answer my question. Your original posting asked how to
iterate over an array, and presupposed the need for a function like this.
Then we explained that the way to iterate over a multi-dimensional array is
by using ROW-MAJOR-AREF.
So given the existence of ROW-MAJOR-AREF, why do you need a function to go
from a linear index to a set of indexes? If you have a linear index you
can use ROW-MAJOR-AREF, and if you have a set of indexes you use AREF.
David D. Smith
In article <bE8X.21$Fb2.3...@cam-news-reader1.bbnplanet.com>, Barry
Margolin <bar...@bbnplanet.com> wrote:
> In article <m3ra36y...@mute.eaglets.com>,
> Sam Steingold <s...@usa.net> wrote:
> >BTW, is it okay to modify the result of array-dimensions?
>
> I was wondering the same thing when I saw your NREVERSE. Neither CLtL nor
> the CLHS says that the list that ARRAY-DIMENSIONS returns is fresh, and I
> can easily imagine an implementor using this as license to store a list in
> the array object and simply return that list. So you should not depend on
> being able to modify it.
>
> >You see, this whole thing strikes me as unusual (I want to say
> >"underdesigned", but I won't dare to :-). There is this function,
> >array-row-major-index, which has an important and simple inverse,
> >array-index-row-major (taking the array and the row-major index and
> >returning the real indexes as multiple values), which is not specified
> >by the standard.
I didn't see the question but this might be one answer -d
(defvar *a* (make-array '(7 4 9 5)))
(array-row-major-index *a* 3 2 8 1) => 671
(defun array-index-row-major (array rmi)
(reduce #'(lambda (dim x)
(nconc
(multiple-value-list (truncate (car x) dim))
(cdr x)))
(cdr (array-dimensions array))
:initial-value (list rmi)
:from-end t))
(array-index-row-major *a* 671) => (3 2 8 1)
;;; End.
Erik Naggum
* Barry Margolin
| So given the existence of ROW-MAJOR-AREF, why do you need a function to go
| from a linear index to a set of indexes? If you have a linear index you
| can use ROW-MAJOR-AREF, and if you have a set of indexes you use AREF.
it appears that he wants the indexes printed alongside the value.
#:Erik
--
religious cult update in light of new scientific discoveries:
"when we cannot go to the comet, the comet must come to us."
David D. Smith
In article <dds-100498...@p65.bit-net.com>, d...@flavors.com (David
D. Smith) wrote:
(time (dotimes (i 1000) (array-index-row-major *a* 671)))
(DOTIMES (I 1000) (ARRAY-INDEX-ROW-MAJOR *A* 671)) took 35 milliseconds
(0.035 seconds) to run.
Of that, 13 milliseconds (0.013 seconds) was spent in GC.
112,008 bytes of memory allocated.
;;;I made this faster:
;;; This conses less, and runs faster in MCL.
(defun array-index-row-major (array rmi)
(reduce #'(lambda (dim x)
(multiple-value-bind (q r) (truncate (car x) dim)
(cons q (rplaca x r))))
(cdr (array-dimensions array))
:initial-value (list rmi)
:from-end t))
(time (dotimes (i 1000) (array-index-row-major *a* 671)))
(DOTIMES (I 1000) (ARRAY-INDEX-ROW-MAJOR *A* 671)) took 23 milliseconds
(0.023 seconds) to run.
Of that, 8 milliseconds (0.008 seconds) was spent in GC.
88,008 bytes of memory allocated.
NIL
;;; End.
David D. Smith
In article <dds-100498...@p94.bit-net.com>, d...@flavors.com (David
D. Smith) wrote:
> > In article <bE8X.21$Fb2.3...@cam-news-reader1.bbnplanet.com>, Barry
> > Margolin <bar...@bbnplanet.com> wrote:
> >
> > > In article <m3ra36y...@mute.eaglets.com>,
> > > Sam Steingold <s...@usa.net> wrote:
> > > >BTW, is it okay to modify the result of array-dimensions?
> > >
> > > I was wondering the same thing when I saw your NREVERSE. Neither CLtL nor
> > > the CLHS says that the list that ARRAY-DIMENSIONS returns is fresh, and I
> > > can easily imagine an implementor using this as license to store a list in
> > > the array object and simply return that list. So you should not depend on
> > > being able to modify it.
> > >
> > > >You see, this whole thing strikes me as unusual (I want to say
> > > >"underdesigned", but I won't dare to :-). There is this function,
> > > >array-row-major-index, which has an important and simple inverse,
> > > >array-index-row-major (taking the array and the row-major index and
> > > >returning the real indexes as multiple values), which is not specified
> > > >by the standard.
I didn't see the question but this might be three answers -d
;;;I made this faster:
;;; The explicit iterative version
(defun array-index-row-major (array rmi)
(do ((subs (list rmi) (cons q (rplaca subs r)))
(dims (reverse (cdr (array-dimensions array))) (cdr dims))
q r)
((null dims) subs)
(multiple-value-setq (q r) (truncate (car subs) (car dims)))))
(time (dotimes (i 1000) (array-index-row-major *a* 671)))
(DOTIMES (I 1000) (ARRAY-INDEX-ROW-MAJOR *A* 671)) took 17 milliseconds
(0.017 seconds) to run.
Of that, 6 milliseconds (0.006 seconds) was spent in GC.
88,008 bytes of memory allocated.
NIL
?
;;; End.