I've got a two dimensional grid of characters.
At one stage, I need to extract strings from the grid,
either on a row by row basis, or on a column by column
basis.
I started writing the accessors, but I'm worried about
the amount of duplicate code. To wit:
(defun get-grid-row (grid row)
"Returns the given row of the grid as a string"
(let* ((length (grid-cols grid))
(s (make-array length :fill-pointer 0 :adjustable t
:element-type 'character)))
(dotimes (col length s)
(vector-push-extend (····@ grid col row) s))))
(defun get-grid-col (grid col)
"Returns the given column of the grid as a string"
(let* ((length (grid-rows grid))
(s (make-array length :fill-pointer 0 :adjustable t
:element-type 'character)))
(dotimes (row length s)
(vector-push-extend (····@ grid col row) s))))
This piece of code is exactly the same one, save for the swaping
of row & cols.
And that's a simple example. I've got a much more involved piece of code,
which I already wrote, debugged and tested for the row case, and I really
don't feel like copy-paste-patch a second instance.
The choices I see are:
1. have the coordinate include its orientation. Like > 0 for cols
and < 0 for rows.
-> this wouldn't easily scale to 3 dimensions(but I don't care)
-> this pushes an explicit test (against 0) at the lowest level
2. use an array of two elements, and transform all references
of the form (foo col), (foo row) into (foo index direction)
-> this would increase the argument list by one everywhere.
-> replacing a pair of (row, col) slots with an array of two
elements is going to be more expensive both in time and
space, but not emphatically so,
-> I can defer chosing between the :by-column and :by-row
directions until the highest level.
3. use copy-paste-patch as I've started doing. But I'm not pleased
at all. this smells.
Anyone see any other options I missed?
Many Thanks
--
JFB
Well, I'm a lisp newbie myself but it would seem to me that this only
requires a pretty trivial macro. Something like this:
(defmacro define-get-grid-function (function-name orientation)
`(defun ,function-name (grid row)
"Returns the given row of the grid as a string"
(let* ((length (,orientation grid))
(s (make-array length :fill-pointer 0 :adjustable t
:element-type 'character)))
(dotimes (col length s)
(vector-push-extend (····@ grid col row) s)))))
then you use it like this:
(define-get-grid-function get-grid-row grid-cols)
(define-get-grid-function get-grid-col grid-rows)
these two rows should expand to a two defuns which differ only in the
defined places.
There may be something wrong in this, it is not a complete solution,
but I'm pretty sure the idea is correct (to use a macro). Hope this
helps.
- Sampo
On 2005-12-31 22:54:02 +0000, ···········@gmail.com said:
> (defmacro define-get-grid-function (function-name orientation)
> `(defun ,function-name (grid row)
> "Returns the given row of the grid as a string"
> (let* ((length (,orientation grid))
> (s (make-array length :fill-pointer 0 :adjustable t
> :element-type 'character)))
> (dotimes (col length s)
> (vector-push-extend (····@ grid col row) s)))))
>
> then you use it like this:
> (define-get-grid-function get-grid-row grid-cols)
> (define-get-grid-function get-grid-col grid-rows)
>
> these two rows should expand to a two defuns which differ only in the
> defined places.
>
> There may be something wrong in this, it is not a complete solution,
> but I'm pretty sure the idea is correct (to use a macro). Hope this
> helps.
Well, I'm sorry I wasn't explicit enough.
The problem wasn't that those two functions were nearly
identical, but that *all* functions dealing with one dimension
were about to be duplicated to deal with the other dimension.
The problem isn't especially about Lisp (though I hope the
solution might be :-)
I wrote:
> 1. have the coordinate include its orientation. Like > 0 for cols
> and < 0 for rows.
> -> this wouldn't easily scale to 3 dimensions(but I don't care)
> -> this pushes an explicit test (against 0) at the lowest level
>
> 2. use an array of two elements, and transform all references
> of the form (foo col), (foo row) into (foo index direction)
> -> this would increase the argument list by one everywhere.
> -> replacing a pair of (row, col) slots with an array of two
> elements is going to be more expensive both in time and
> space, but not emphatically so,
> -> I can defer chosing between the :by-column and :by-row
> directions until the highest level.
>
> 3. use copy-paste-patch as I've started doing. But I'm not pleased
> at all. this smells.
I could construe your example as:
4. use macros.
But on first analysis, no matter *how* I have defined both get-grid-row
and get-grid-col (by hand or through your macros) I still end-uo
with TWO functions, which means that the disctinction between cols
& rows must carry through to upper levels, which is what I want to
avoid in the first place.
Ideally I would want only the top most caller to have to decide
whether to ask for rows or columns. Since the notion of "top-most"
caller is ill-defined, what I'm really getting at, is that I'd like
*all* functions to *not* commit to either rows or cols *unless* they
have a need to do so, which brings me back to options #1 and #2 above.
Many Thanks.
--
JFB
verec wrote:
> I've got a two dimensional grid of characters.
>
> At one stage, I need to extract strings from the grid,
> either on a row by row basis, or on a column by column
> basis.
[...]
> Anyone see any other options I missed?
I' m a big fan of (1) the :displaced-to feature of <make-array>, and (2)
<loop>.
Carl Taylor
(defun get-char-grid-row (row x-grid)
(declare (type fixnum row))
(let ((col-cnt (array-dimension x-grid 1)))
(map 'string #'identity
(make-array col-cnt
:element-type (array-element-type x-grid)
:displaced-to x-grid
:displaced-index-offset (* row col-cnt)))))
(defun get-char-grid-col (col x-grid)
(declare (type fixnum col))
(map 'string #'identity
(loop :for i fixnum
:repeat (the fixnum (array-dimension x-grid 0))
:collect (aref x-grid i col))))
CL-USER 13 >
(get-char-grid-row 2 #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i)))
"ghi"
CL-USER 14 >
(get-char-grid-col 1 #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i)))
"beh"
On 2005-12-31 17:24:42 +0000, "Carl Taylor" <··········@att.net> said:
> (defun get-char-grid-row (row x-grid)
> (declare (type fixnum row))
> (let ((col-cnt (array-dimension x-grid 1)))
> (map 'string #'identity
> (make-array col-cnt
> :element-type (array-element-type x-grid)
> :displaced-to x-grid
> :displaced-index-offset (* row col-cnt)))))
>
>
> (defun get-char-grid-col (col x-grid)
> (declare (type fixnum col))
> (map 'string #'identity
> (loop :for i fixnum
> :repeat (the fixnum (array-dimension x-grid 0))
> :collect (aref x-grid i col))))
>
>
> CL-USER 13 >
> (get-char-grid-row 2 #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i)))
> "ghi"
>
> CL-USER 14 >
> (get-char-grid-col 1 #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i)))
> "beh"
That's very interesting, but you still end-up with two functions,
one for row access and one for column access. That is what I wanted
to parameterize on.
Ideally, I'd have either of
(defun get-grid-string (grid position direction)
( ...
with usage:
> (get-grid-string #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i)) 1 :by-column)
"beh"
if it turns out that providing the direction (rows vs cols)
explicitely is required,
or
(defun get-grid-straing (grid position)
( ...
if the direction can be "coded into" the position itself.
with usage:
> (get-grid-string #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i))
(make-position 2 :by-row))
"ghi"
My point is that I've already got non trivial (working) code
to handle the "rows" case, and I'd rather amend it to deal
with both directions than copy-paste-patch a second instance
of every single row related function into a nearly indentical
column related function.
Many Thanks.
--
JFB
"verec" <·····@mac.com> wrote in message
·····························@nan-newsreader-05.noos.net...
> On 2005-12-31 17:24:42 +0000, "Carl Taylor" <··········@att.net> said:
[...]
> That's very interesting, but you still end-up with two functions,
> one for row access and one for column access. That is what I wanted
> to parameterize on.
The two ideas of displacement and loop can be combined into a single
function easily enough, but of course this won't help if you want to
preserve your existing "row" code. But anyway, here's a single function
that I think will do what you want. Both the reshaping of the array via
:displaced-to and the loop are efficient operations.
Carl Taylor
(defun get-row-or-col-string (r/c rc-nbr char-grid)
(declare (optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0)))
(declare (type fixnum rc-nbr))
(let* ((dim-0 (array-dimension char-grid 0))
(dim-1 (array-dimension char-grid 1))
(grid-as-vector
(make-array (* dim-0 dim-1)
:element-type (array-element-type char-grid)
:displaced-to char-grid)))
(declare (type fixnum dim-0 dim-1))
(map 'string #'identity
(ecase r/c
((r :r row :row)
(loop :for i fixnum
:from (the fixnum (* rc-nbr dim-1))
:repeat (the fixnum dim-1)
:collect (aref grid-as-vector i)))
((c :c col :col)
(loop :for i fixnum
:from (the fixnum rc-nbr)
:to (the fixnum (1- (* dim-0 dim-1)))
:by dim-1
:collect (aref grid-as-vector i)))))))
(compile *)
(defparameter *ca* #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i) (#\j #\k
#\l)))
(get-row-or-col-string :row 0 *ca*)
(get-row-or-col-string 'row 1 *ca*)
(get-row-or-col-string 'r 2 *ca*)
(get-row-or-col-string :r 3 *ca*)
(get-row-or-col-string :col 0 *ca*)
(get-row-or-col-string 'col 1 *ca*)
(get-row-or-col-string :c 2 *ca*)
"verec" <·····@mac.com> wrote in message
·····························@nan-newsreader-07.noos.net...
> On 2005-12-31 23:50:47 +0000, "Carl Taylor" <··········@att.net> said:
[...]
> Hmmmm. You've got me thinking. This is certainly not what
> I was expecting, but it seems ... much better! :-)
>
> I'll mull over the implication of this.
In my enthusiasm for array displacement I failed to see it isn't necessary
in this function. Better to use <row-major-aref> I think.
Carl Taylor
(defun get-row-or-col-string (r/c rc-nbr char-grid)
(declare (optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0)))
(declare (type fixnum rc-nbr))
(let ((dim-0 (array-dimension char-grid 0))
(dim-1 (array-dimension char-grid 1)))
(declare (type fixnum dim-0 dim-1))
(map 'string #'identity
(ecase r/c
((r :r row :row)
(loop :for i fixnum
:from (the fixnum (* rc-nbr dim-1))
:repeat (the fixnum dim-1)
:collect (row-major-aref char-grid
i)))
((c :c col :col)
(loop :for i fixnum
:from (the fixnum rc-nbr)
:to (the fixnum (1- (* dim-0
dim-1)))
:by dim-1
:collect (row-major-aref char-grid
i)))))))
Hi Verec,
verec <·····@mac.com> writes:
> On 2005-12-31 17:24:42 +0000, "Carl Taylor" <··········@att.net> said:
>
>> (defun get-char-grid-row (row x-grid)
>> (declare (type fixnum row))
>> (let ((col-cnt (array-dimension x-grid 1)))
>> (map 'string #'identity
>> (make-array col-cnt
>> :element-type (array-element-type x-grid)
>> :displaced-to x-grid
>> :displaced-index-offset (* row col-cnt)))))
>> (defun get-char-grid-col (col x-grid)
>> (declare (type fixnum col))
>> (map 'string #'identity
>> (loop :for i fixnum
>> :repeat (the fixnum (array-dimension x-grid 0))
>> :collect (aref x-grid i col))))
>> CL-USER 13 >
>> (get-char-grid-row 2 #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i)))
>> "ghi"
>> CL-USER 14 >
>> (get-char-grid-col 1 #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i)))
>> "beh"
>
> That's very interesting, but you still end-up with two functions,
> one for row access and one for column access. That is what I wanted
> to parameterize on.
>
> Ideally, I'd have either of
>
> (defun get-grid-string (grid position direction)
> ( ...
>
> with usage:
>> (get-grid-string #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i)) 1 :by-column)
> "beh"
>
> if it turns out that providing the direction (rows vs cols)
> explicitely is required,
>
> or
>
> (defun get-grid-straing (grid position)
> ( ...
>
> if the direction can be "coded into" the position itself.
>
> with usage:
>> (get-grid-string #2A((#\a #\b #\c) (#\d #\e #\f) (#\g #\h #\i))
> (make-position 2 :by-row))
> "ghi"
>
> My point is that I've already got non trivial (working) code
> to handle the "rows" case, and I'd rather amend it to deal
> with both directions than copy-paste-patch a second instance
> of every single row related function into a nearly indentical
> column related function.
AFAICS, the cleanest (and most efficient!) solution is to use
ROW-MAJOR-AREF and compute the linear indices in the 2D array
yourself (lightly tested):
,----
| (defun grid-slice (grid orientation n &key start end)
| "Extracts the Nth slice of the 2-dimensional array GRID along
| orientation ORIENTATION, which must be either :ROW or :COLUMN.
| START and END can be used to extract a sub-slice; their default
| values are 0 and the axis length respectively."
| (multiple-value-bind (axis skip stride)
| (ecase orientation
| (:row (values 0 (array-dimension grid 1) 1))
| (:column (values 1 1 (array-dimension grid 1))))
| (let* ((start (or start 0))
| (count (- (or end (array-dimension grid (- 1 axis))) start))
| (slice (make-array count
| :element-type (array-element-type grid)
| :adjustable nil
| :fill-pointer nil)))
| (do ((src (+ (* n skip) (* start stride)) (+ src stride))
| (dest 0 (1+ dest)))
| ((>= dest count) slice)
| (setf (aref slice dest)
| (row-major-aref grid src))))))
|
| #||
| (grid-slice #2a((0 1 2 3)
| (2 2 4 6)
| (4 4 8 12))
| :column 2)
|
| (grid-slice #2a((0 1 2 3)
| (2 2 4 6)
| (4 4 8 12))
| :row 1
| :start 1
| :end 3)
| ||#
`----
Generalization to higher dimensions and variable-width slices is left
as an exercise to the reader :)
> Many Thanks.
Cheers,
Damien.
--
http://foobox.net/~dash/
Quidquid latine dictum sit, altum sonatur.
Verec,
verec <·····@mac.com> writes:
> On 2006-01-01 12:53:15 +0000, Damien Diederen <····@foobox.net> said:
>
>> (defun grid-slice (grid orientation n &key start end)
>> "Extracts the Nth slice of the 2-dimensional array GRID along
>> orientation ORIENTATION, which must be either :ROW or :COLUMN.
>> START and END can be used to extract a sub-slice; their default
>> values are 0 and the axis length respectively."
[deletia]
> With so many solutions, I now have a new problem: chosing
> amongst them :-)
:)
> Now it seems that passing the pair (position, orientation)
> seems to have the favor of you all (as opposed to a position
> thing that would somehow encode the orientation)
I would keep them separated, at least in a low-level interface (but
the pseudo-keyword notation does not hamper readability in my eyes).
Even if bundling them together is desirable for practical reasons, I
would shy away from using negative numbers as columns indices (as
suggested in another post; that would be messy and could hide ugly
bugs), but rather encode the pair in a simple data structure.
Walktrough:
1. Rename the low-level interface, getting rid of the now-useless
keyword arguments:
,----
| (defun %grid-slice (grid orientation n key start)
| ...)
`----
2. Define a "slice" constructor and the high-level interface (let's
use a simple CONS for this example):
,----
| (defun slice (orientation n)
| (cons orientation n))
|
| (defun grid-slice (grid slice &key start end)
| (destructuring-bind (orientation . n) slice
| (%grid-slice grid orientation n start end)))
|
| (defun test.grid-slice (orientation n)
| (grid-slice #2a((0 1 2 3)
| (2 2 4 6)
| (4 4 8 12))
| (slice orientation n)
| :start 1
| :end 3))
`----
3. Optional; premature optimization: define a small compiler macro to
reduce "consing" in the obvious case. Once the macro is enabled,
any (DISASSEMBLE 'TEST.GRID-SLICE) following a (COMPILE
'TEST.GRID-SLICE) should show no trace of the high-level interface
being used—in any implementation offering reasonable compiler
macro support:
,----
| (define-compiler-macro grid-slice (&whole whole grid-form slice-form &key start end)
| (cond ((and (listp slice-form) (eq (first slice-form) 'slice) (= (length slice-form) 3))
| `(%grid-slice ,grid-form ,(second slice-form) ,(third slice-form) ,start ,end))
| (t
| whole)))
`----
This "optimization":
1. Is independent of the representation used for "slices": the CONS
could be replaced by a full-blown CLOS class;
2. Makes no sense, but is an example of how an high-level interface
can be usable in an inner loop yet avoid unnecessary "consing".
> Many Thanks!
Cheers,
Damien.
--
http://foobox.net/~dash/
Quidquid latine dictum sit, altum sonatur.