Managing displaced arrays...

Discussion of Common Lisp
Post Reply
starfleet
Posts: 8
Joined: Sun Jun 30, 2013 12:36 pm
Location: Mexico city

Managing displaced arrays...

Post by starfleet » Sun Jul 27, 2014 5:46 pm

Greetings everyone,

I need to write a small program for handling numeric 2D arrays...

As a special requirement I need to reorder certain rows and columns within an array...
I think the right way to do it is by creating a new displaced array but I don't have the expertise needed for the task... :(

I'd like something like:
(reorder-row <array> <current-row-index> <new-row-index> )
(reorder-col <array> <current-col-index> <new-col-index>)
preferably destructive versions, although I think using displacement requires non-destructive...

Can someone give an example of how to implement these?

Thanks in advance

pjstirling
Posts: 166
Joined: Sun Nov 28, 2010 4:21 pm

Re: Managing displaced arrays...

Post by pjstirling » Mon Jul 28, 2014 7:59 am

Displaced arrays don't do what you want, sadly. A displaced array is like a pointer into a C string. You can use it to read and modify the underlying array, but there's no way to make it do anything column major.

logxor
Posts: 20
Joined: Tue May 27, 2014 10:56 am
Location: Portland, OR

Re: Managing displaced arrays...

Post by logxor » Mon Jul 28, 2014 1:43 pm

It's hard to think about this without a strict definition of what "reordering" means in this case, or what the reordering is for, but I'll take a quick whack at this with the standard ROTATEF macro. With that we can define a function to swap rows destructively. This function, having been tested, can then be used to implement a reordering function as a series of swaps:

Code: Select all

(defun swap-rows (array current-row-index new-row-index)
  (let ((columns (second (array-dimensions array))))
    (loop for i from 0 below columns
          do (rotatef (aref array new-row-index i)
                      (aref array current-row-index i)))))

(defun reorder-row (array current-row-index new-row-index)
  (if (> new-row-index current-row-index)
      ;; Backward shift.
      (loop for row-index from current-row-index below new-row-index
            do (swap-rows array row-index (1+ row-index)))
      ;; Forward shift.
      (loop for row-index from current-row-index above new-row-index
            do (swap-rows array row-index (1- row-index))))
  array)
This'll give you an idea of how to make the REORDER-COL function, and whatever it is that you want to do with it.

starfleet
Posts: 8
Joined: Sun Jun 30, 2013 12:36 pm
Location: Mexico city

Re: Managing displaced arrays...

Post by starfleet » Tue Jul 29, 2014 1:02 pm

Thanks LOGXOR...

I hadn't think about ROTATEF... and looks like it is a very good point to start with these reordering functions...

As I can see now, the problem seems to be tackling the column-wise operations...But your code is definitely a solid start-point...

Just to clraify a little, what I need is to do some column and row reordering to some matrices in order to make them suitable for particular search algorithms (in Testor Theory)...Maybe, what I need is to define some class that can handle rows and columns in the same manner (as I've seen it work on some widgets in Delphi)... Such widgets allow you to specify if you want to operate on rows or on columns, as well as element-by-element...

Any good advice in how to start with that idea?

logxor
Posts: 20
Joined: Tue May 27, 2014 10:56 am
Location: Portland, OR

Re: Managing displaced arrays...

Post by logxor » Tue Jul 29, 2014 3:40 pm

Numerical stuff isn't my specialty, but I'll give a couple of suggestions that have nothing to do with numerical arrays in particular. There's an accessor, ROW-MAJOR-AREF, which is useful for operating on arrays "element-by-element" (as you mentioned) regardless of the dimensions.

Another thing to consider is that if you have to write a lot of code that deals with "slices" of multidimensional arrays, it might be worth designing some sort of lightweight object that can represent those slices without needing to copy the array contents. I've heard that the Lisp Machine had "conformal displacement" which did this—but in Common Lisp, a displaced array is restricted to being a flat, sequential slice of the original array. I guess this is partly because the conformal displacement makes it tricky to calculate an index efficiently, but also because Common Lisp wasn't designed to compete with the numerical languages, like Fortran, on their own ground.

starfleet
Posts: 8
Joined: Sun Jun 30, 2013 12:36 pm
Location: Mexico city

Re: Managing displaced arrays...

Post by starfleet » Tue Jul 29, 2014 4:23 pm

I see...
I'm not sure if "conformal displacement" is what I need , yet... but ROW-MAJOR-AREF looks promising as the base for a wrap class that allows the processing of "slices" (either columns or rows) in matrices...

It really doesn't matter if the arrays contain numeric data... it's just a matter of adapting the program's behavior to the theoretical model...

I thank you very much for your insights... And I promise, as soon as I have the implementation of this idea I will share it in this forum...

LIVE LONG AND PROSPER...

Post Reply