Velocity Reviews > Sorting Multidimesional array(newbie)

Sorting Multidimesional array(newbie)

Tartifola
Guest
Posts: n/a

 12-11-2006

Hi,
how can I sort an array like

array([[5, 2],
[1, 3]])

along the first column to obtain

array([[1, 3],
[5, 2]])
i.e. keeping track of the ordered couples?

Thanks,
A

Matimus
Guest
Posts: n/a

 12-11-2006
Tartifola wrote:
> Hi,
> how can I sort an array like
>
> array([[5, 2],
> [1, 3]])
>
> along the first column to obtain
>
> array([[1, 3],
> [5, 2]])
> i.e. keeping track of the ordered couples?
>
> Thanks,
> A

use a sort key:

>>>from operators import getitem
>>>a = [[5,2],[1,3]]
>>>a

[[5, 2], [1, 3]]
>>>a.sort(key=lambda x:getitem(x,0))
>>>a

[[1, 3], [5, 2]]

Peter Otten
Guest
Posts: n/a

 12-11-2006
Matimus wrote:

> Tartifola wrote:
>> Hi,
>> how can I sort an array like
>>
>> array([[5, 2],
>> [1, 3]])
>>
>> along the first column to obtain
>>
>> array([[1, 3],
>> [5, 2]])
>> i.e. keeping track of the ordered couples?
>>
>> Thanks,
>> A

>
> use a sort key:
>
>>>>from operators import getitem
>>>>a = [[5,2],[1,3]]
>>>>a

> [[5, 2], [1, 3]]
>>>>a.sort(key=lambda x:getitem(x,0))
>>>>a

> [[1, 3], [5, 2]]

Is that a faked session?

>>> from operators import getitem

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ImportError: No module named operators

>>> from operator import itemgetter
>>> a = [[5, 2], [1, 3]]
>>> a.sort(key=itemgetter(0))
>>> a

[[1, 3], [5, 2]]

Peter

Brian Mills
Guest
Posts: n/a

 12-12-2006
There's another (IMHO more readable) way to do it if you can afford
defining a short little "compare" function, and telling <list>.sort()
to use that instead of its default:

>>> def myListCmp(lst1, lst2):

.... if lst1[0] < lst2[0]: return -1
.... if lst2[0] > lst2[0]: return 1
.... return 0
....
>>> a = [[5, 2], [1, 3]]
>>> a

[[5, 2], [1, 3]]
>>> a.sort(cmp=myListCmp)
>>> a

[[1, 3], [5, 2]]
>>>

On Dec 11, 11:11 am, Peter Otten <(E-Mail Removed)> wrote:
> Matimus wrote:
> > Tartifola wrote:
> >> Hi,
> >> how can I sort an array like

>
> >> array([[5, 2],
> >> [1, 3]])

>
> >> along the first column to obtain

>
> >> array([[1, 3],
> >> [5, 2]])
> >> i.e. keeping track of the ordered couples?

>
> >> Thanks,
> >> A

>
> > use a sort key:

>
> >>>>from operators import getitem
> >>>>a = [[5,2],[1,3]]
> >>>>a

> > [[5, 2], [1, 3]]
> >>>>a.sort(key=lambda x:getitem(x,0))
> >>>>a

> > [[1, 3], [5, 2]]Is that a faked session?

>
> >>> from operators import getitemTraceback (most recent call last):

> File "<stdin>", line 1, in <module>
> ImportError: No module named operators
>
> >>> from operator import itemgetter
> >>> a = [[5, 2], [1, 3]]
> >>> a.sort(key=itemgetter(0))
> >>> a[[1, 3], [5, 2]]

>
> Peter

Fredrik Lundh
Guest
Posts: n/a

 12-12-2006
Brian Mills wrote:

> There's another (IMHO more readable) way to do it if you can afford
> defining a short little "compare" function, and telling <list>.sort()
> to use that instead of its default:
>
>>>> def myListCmp(lst1, lst2):

> ... if lst1[0] < lst2[0]: return -1
> ... if lst2[0] > lst2[0]: return 1
> ... return 0

shorter:

def myListCmp(a, b):
return cmp(a[0], b[0])

but using a compare function instead of a key mapper is not good advice,
in general. brief discussion here:

http://effbot.org/pyfaq/i-want-to-do...form-in-python

also note the OP didn't specify what to do for records where the first
column was identical, so I guess a plain sort() call, without any custom
compares or mappings, would work as well as the fancier alternatives...

</F>

Robert Kern
Guest
Posts: n/a

 12-12-2006
Fredrik Lundh wrote:
> also note the OP didn't specify what to do for records where the first
> column was identical, so I guess a plain sort() call, without any custom
> compares or mappings, would work as well as the fancier alternatives...

If the OP had lists of lists, yes. However, he seems to be using one of (numpy,
numarray, Numeric). Because of rich comparisons, just using sorted() won't work.
The cheap and cheerful approach would be to convert to lists of lists using
..tolist(), .sort() the list, and then reconstruct the array object. Depending on
the size of the array, that may be just fine.

numpy (and maybe numarray, I'd have to check) has a function lexsort(), which
unfortunately has a confusing interface.

In [2]: lexsort?
Type: builtin_function_or_method
Base Class: <type 'builtin_function_or_method'>
Namespace: Interactive
Docstring:
lexsort(keys=, axis=-1) -> array of indices. argsort with list of keys.

Return an array of indices similar to argsort, except the sorting is
done using the provided sorting keys. First the sort is done using
key[0], then the resulting list of indices is further manipulated by
sorting on key[1], and so forth. The result is a sort on multiple
keys. If the keys represented columns of a spreadsheet, for example,
this would sort using multiple columns (the last key being used for the
primary sort order, the second-to-last key for the secondary sort order,
and so on). The keys argument must be a sequence of things that can be
converted to arrays of the same shape.

This is the idiomatic way to lexicographically sort an array by columns
equivalent to the .tolist() approach I give above. I usually wrap lexsort() with
these operations so my brain doesn't explode.

In [15]: from numpy import *

In [16]: a = array([[5, 2], [1, 3], [1, 2]])

In [17]: a[lexsort(keys=a.transpose()[::-1])]
Out[17]:
array([[1, 2],
[1, 3],
[5, 2]])

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
an underlying truth."
-- Umberto Eco

Travis E. Oliphant
Guest
Posts: n/a

 12-12-2006
Tartifola wrote:
> Hi,
> how can I sort an array like
>
> array([[5, 2],
> [1, 3]])
>
> along the first column to obtain
>
> array([[1, 3],
> [5, 2]])
> i.e. keeping track of the ordered couples?
>
> Thanks,
> A

Just to add one more solution to this question that works with numpy.

You can also view the array using fields and then sort (which will do
lexicographic ordering) and convert the result back to the original view.

Something like this:

a = array([[5,2],[1,3]])
dt = a.dtype
g = a.view([('',dt),('',dt)])
g.sort(0)
a = g.view(dt)

-Travis

Brian Mills
Guest
Posts: n/a

 12-14-2006

Fredrik Lundh wrote:

> Brian Mills wrote:
>
> > There's another (IMHO more readable) way to do it if you can afford
> > defining a short little "compare" function, and telling <list>.sort()
> > to use that instead of its default:
> >
> >>>> def myListCmp(lst1, lst2):

> > ... if lst1[0] < lst2[0]: return -1
> > ... if lst2[0] > lst2[0]: return 1
> > ... return 0

>
> shorter:
>
> def myListCmp(a, b):
> return cmp(a[0], b[0])

Good point.

> but using a compare function instead of a key mapper is not good advice,
> in general. brief discussion here:
> http://effbot.org/pyfaq/i-want-to-do...form-in-python

Is this mostly because of the stability problem described here:
http://aspn.activestate.com/ASPN/Coo...n/Recipe/52234 ? Or is
it more a performance issue due having to make so many function calls?
>
> also note the OP didn't specify what to do for records where the first
> column was identical, so I guess a plain sort() call, without any custom
> compares or mappings, would work as well as the fancier alternatives...

I can't believe I didn't try this, but for the given example it works
perfectly. It even acts gracefully when you give it such sociopathic
lists as

>>> c = [[3, 1], [8, 2], [6, 3], [12, 4], [1, 5], ["oh noes!", 6], [24, 7], [ope

n("file.txt", 'r'), 8], [[1, 2, 3], 9]]
>>> c.sort()
>>> c

[[1, 5], [3, 1], [6, 3], [8, 2], [12, 4], [24, 7], [<open file
'file.txt', mode
'r' at 0x00A65608>, 8], [[1, 2, 3], 9], ['oh noes!', 6]]

Though changing the ordering system it decides to use may take some
more research.

Peter Otten
Guest
Posts: n/a

 12-14-2006
Brian Mills wrote:

>> but using a compare function instead of a key mapper is not good advice,
>> in general. brief discussion here:
>>

http://effbot.org/pyfaq/i-want-to-do...form-in-python

> Is this mostly because of the stability problem described here:
> http://aspn.activestate.com/ASPN/Coo...n/Recipe/52234 ? Or is
> it more a performance issue due having to make so many function calls?

http://docs.python.org/lib/typesseq-mutable.html

"""Starting with Python 2.3, the sort() method is guaranteed to be
stable."""

So performance it is. It is also often simpler once you get used to it and
start seeing the pattern

def mycmp(a, b):
return cmp(mykey(a), mykey(b))

in many of your custom comparison functions.

Peter

Fredrik Lundh
Guest
Posts: n/a

 12-14-2006
Brian Mills wrote:
>

>> but using a compare function instead of a key mapper is not good advice,
>> in general. brief discussion here:
>> http://effbot.org/pyfaq/i-want-to-do...form-in-python

>
> Is this mostly because of the stability problem described here:
> http://aspn.activestate.com/ASPN/Coo...n/Recipe/52234 ?

as mentioned in the comments to that recipe, Python's sort has been
stable since 2.3.

> Or is it more a performance issue due having to make so many function

calls?

exactly (see the last sentence in the FAQ entry).

</F>