[Matrix-SIG] Fast sorting many lists together...?

[William Park]

On Fri, Sep 15, 2000 at 11:08:53AM -0600, Tim Hochberg wrote:
> 
> > I need to sort about 50 lists (each about 500 elements) together,
> > using few of them as keys.  That is, sort the key lists first; look
> > at which indexes have changed; then, shuffle the rest of list to
> > reflect this new order.
> >
> > Does anyone know a fast fast routine for doing this?
> 
> You probably have to give more details about the way you are using
> multiple lists as keys in order to get a complete response. However,
> if you have created a single list of keys, you can do something like.

What I have is a table where "columns" are the lists and "rows" are the
elements of the lists.  So,
    x	y   z ...	<-- list names
    1	4   0		<-- i=0, ie. first elements
    1   3   2
    .	.   .
The problem is similar to sorting lines using Unix 'sort' command with
'field' options, like
    sort -n -k 1,1 -k 3,3
which means sort by x[i] first, and to break the ties, sort by z[i].

So, what I do is... I create list of tuple and sort them
    i = range(N)	# N = length of lists
    a = [(x[0],z[0],i[0]), (x[1],z[1],i[1]), ...]
    a.sort()
and I recover the index,
    index = []
    for i in a:
	index.append(z[i][-1])
Then, I shuffle every list according to this new index order.


> args = Numeric.argsort(keys)
> keys = Numeric.take(keys, args) # Sort the keys
> list1 = Numeric.take(list1, args) # Sort list 1
> list2 = Numeric.take(list2, args) # Sort list 2
> #....
> 
> -tim

I'm not familiar with NumPy.  Does your code does this?  Also, my lists
mostly contain number, but do have None to denote missing data.

--William