In article <··········@acsu.buffalo.edu> ······@acsu.buffalo.edu (John S. Lewocz) writes:
>What would be the most effiecient way to sort a two-dimensional
>array using an arbitrary column
>as a key?
I can't vouch for it being "the most efficient way", but here's a
reasonably simple way that seems like it shouldn't be too inefficient.
Make a list or vector of displaced arrays, where each elements is a vector
displaced to a row of the original array. Sort this using :KEY #'(LAMBDA
(X) (AREF X COLUMN-NUMBER)), and then combine the results into a new 2-D
array.
Some of the sources of inefficiency in this may be all the references to
displaced arrays and the copying of the elements into the result. You can
avoid the former (at the cost of more consing and copying) by copying the
rows into new vectors at the beginning instead of using displaced arrays.
If you need to avoid all copying, then you'll have to do the sorting in
place, and there's nothing built into Lisp (Common Lisp, at least) to do
this, so you'll have to write your own sort routine.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
······@acsu.buffalo.edu (John S. Lewocz) writes:
> What would be the most effiecient way to sort a two-dimensional
> array using an arbitrary column as a key?
I think that the following solution is pretty efficient, since it doesn't
require copying row data during the sort, or creating loads of new arrays.
It works by sorting a seperate vector that contains numbers of rows of the
original array. This way the SORT function just sorts an integer vector,
which should be pretty quick, using a KEY that maps onto the array being
sorted. Then we just copy the data into the appropriate rows of a new array.
Consing is limited to making one vector the side of the row-dimension of the
original array, and then making a new array to return.
** Note that this is _not_ a destructive sort (unlike CLtL SORT), but it
shouldn't be that hard to do the final copying into itself instead of into a
new array.
(defun sort-array-by-col (a c &optional (p #'<))
"Sort rows of 2-dimensional array A by value of column C using predicate P"
(let* ((num-rows (car (array-dimensions a)))
(index-vec (do ((v (make-array num-rows))
(i 0 (1+ i)))
((= i num-rows) v)
(setf (elt v i) i)))
(sorted-index (sort index-vec p :key #'(lambda (r) (aref a r c))))
(new-array (make-array (array-dimensions a)))
)
(dotimes (r (car (array-dimensions a)))
(dotimes (c (cadr (array-dimensions a)))
(setf (aref new-array r c)
(aref a (elt sorted-index r) c))))
new-array))
Enjoy!
Bruce Krulwich
········@ils.nwu.edu