Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: Python: Python

Sorting on multiple values, some ascending, some descending

 

 

Python python RSS feed   Index | Next | Previous | View Threaded


dwoogle at gmail

Jan 3, 2007, 10:48 AM

Post #1 of 12 (869 views)
Permalink
Sorting on multiple values, some ascending, some descending

I have successfully used the sort lambda construct described in
http://mail.python.org/pipermail/python-list/2006-April/377443.html.
However, how do I take it one step further such that some values can be
sorted ascending and others descending? Easy enough if the sort values
are numeric (just negate the value), but what about text?

Is the only option to define an external sorting function to loop
through the list and perform the comparisons one value at a time?

--
http://mail.python.org/mailman/listinfo/python-list


python at rcn

Jan 3, 2007, 11:30 AM

Post #2 of 12 (858 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

dwelden wrote:
> I have successfully used the sort lambda construct described in
> http://mail.python.org/pipermail/python-list/2006-April/377443.html.
> However, how do I take it one step further such that some values can be
> sorted ascending and others descending? Easy enough if the sort values
> are numeric (just negate the value), but what about text?
>
> Is the only option to define an external sorting function to loop
> through the list and perform the comparisons one value at a time?

The simplest way is to take advantage of sort-stability and do
successive sorts. For example, to sort by a primary key ascending and
a secondary key decending:

L.sort(key=lambda r: r.secondary, reverse=True)
L.sort(key=lambda r: r.primary)

A less general technique is to transform fields in a way that reverses
their comparison order:

L.sort(key=lambda r: (-r.age, r.height)) # sorts descending age
and ascending height


Raymond

--
http://mail.python.org/mailman/listinfo/python-list


carsten at uniqsys

Jan 3, 2007, 11:43 AM

Post #3 of 12 (855 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

On Wed, 2007-01-03 at 10:48 -0800, dwelden wrote:
> I have successfully used the sort lambda construct described in
> http://mail.python.org/pipermail/python-list/2006-April/377443.html.
> However, how do I take it one step further such that some values can be
> sorted ascending and others descending? Easy enough if the sort values
> are numeric (just negate the value), but what about text?
>
> Is the only option to define an external sorting function to loop
> through the list and perform the comparisons one value at a time?

If by "external sorting function" you mean a custom comparison function
to pass to sort as the cmp argument, then that's one option, but not the
only one.

If you know in advance which columns contain strings, you could write a
function that operates on strings and is strictly monotonically
decreasing, i.e. it behaves such that f(x) < f(y) if and only if x > y.
This function could then be used in the sort key for sorting on a string
column in descending order. The following function does the trick:

def antistring(x):
return [256-ord(c) for c in x]+[257]

(Proof by vigorous handwaving.)

Lastly, if your array is small enough that you can tolerate the
performance hit of multiple passes, you could exploit the fact that
sort() is guaranteed to be stable in sufficiently recent releases of
CPython. Split your sort on n columns into n separate sorts on a single
column each, and use the 'reverse' parameter to specify whether to sort
forward or backwards.

Hope this helps,

Carsten.


--
http://mail.python.org/mailman/listinfo/python-list


bearophileHUGS at lycos

Jan 3, 2007, 12:10 PM

Post #4 of 12 (853 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

Raymond Hettinger:
> The simplest way is to take advantage of sort-stability and do
> successive sorts. For example, to sort by a primary key ascending and
> a secondary key decending:
> L.sort(key=lambda r: r.secondary, reverse=True)
> L.sort(key=lambda r: r.primary)

That's probably the faster and simpler way.
The following solution is probably slow, memory-hungry, and it's not
tested much so it may be buggy too, but it shows my idea, and bugs can
be fixed:

class Inverter:
def __init__(self, item, reversed=False):
self.item = item
self.reversed = reversed
def __cmp__(self, other):
if self.reversed:
return cmp(other.item, self.item)
else:
return cmp(self.item, other.item)

data = [[1, "a", "b"], [1, "b", "d"], [1, "d", "a"]]
reverses = [True, False, False]

print sorted(data, key=lambda subseq: map(Inverter, subseq, reverses))

Bye,
bearophile

--
http://mail.python.org/mailman/listinfo/python-list


__peter__ at web

Jan 3, 2007, 12:16 PM

Post #5 of 12 (872 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

Raymond Hettinger wrote:

> dwelden wrote:
>> I have successfully used the sort lambda construct described in
>> http://mail.python.org/pipermail/python-list/2006-April/377443.html.
>> However, how do I take it one step further such that some values can be
>> sorted ascending and others descending? Easy enough if the sort values
>> are numeric (just negate the value), but what about text?
>>
>> Is the only option to define an external sorting function to loop
>> through the list and perform the comparisons one value at a time?
>
> The simplest way is to take advantage of sort-stability and do
> successive sorts. For example, to sort by a primary key ascending and
> a secondary key decending:
>
> L.sort(key=lambda r: r.secondary, reverse=True)
> L.sort(key=lambda r: r.primary)
>
> A less general technique is to transform fields in a way that reverses
> their comparison order:
>
> L.sort(key=lambda r: (-r.age, r.height)) # sorts descending age
> and ascending height

You can get generality if you are willing to pay the performance penalty:

>>> items
[.(3, 1), (2, 2), (1, 1), (1, 3), (2, 1), (2, 3), (1, 2)]
>>> class Reverse:
... def __cmp__(self, other):
... return -cmp(self.value, other.value)
... def __init__(self, value):
... self.value = value
...
>>> items.sort(key=lambda (x, y): (x, Reverse(y)))
>>> items
[.(1, 3), (1, 2), (1, 1), (2, 3), (2, 2), (2, 1), (3, 1)]

Peter
--
http://mail.python.org/mailman/listinfo/python-list


george.sakkis at gmail

Jan 3, 2007, 12:24 PM

Post #6 of 12 (853 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

dwelden wrote:

> I have successfully used the sort lambda construct described in
> http://mail.python.org/pipermail/python-list/2006-April/377443.html.
> However, how do I take it one step further such that some values can be
> sorted ascending and others descending? Easy enough if the sort values
> are numeric (just negate the value), but what about text?

You got already some good replies; here's yet another less-than-optimal
way:

class revstr(str):
def __lt__(self, other):
return str.__gt__(self,other)
def __gt__(self, other):
return str.__lt__(self,other)

L.sort(key=lambda i: (i.somestring, revstr(i.someotherstring),
i.anotherkey))


George

--
http://mail.python.org/mailman/listinfo/python-list


dwoogle at gmail

Jan 3, 2007, 3:46 PM

Post #7 of 12 (852 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

> The simplest way is to take advantage of sort-stability and do
> successive sorts. For example, to sort by a primary key ascending and
> a secondary key decending:
>
> L.sort(key=lambda r: r.secondary, reverse=True)
> L.sort(key=lambda r: r.primary)
>
Excellent! That looks just like what I needed.

> A less general technique is to transform fields in a way that reverses
> their comparison order:
>
> L.sort(key=lambda r: (-r.age, r.height)) # sorts descending age
> and ascending height
This one I had figured out, but could not see how to get it to work for
strings.

Much obliged.

--
http://mail.python.org/mailman/listinfo/python-list


bearophileHUGS at lycos

Jan 3, 2007, 5:18 PM

Post #8 of 12 (855 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

dwelden wrote:
> > L.sort(key=lambda r: r.secondary, reverse=True)
> > L.sort(key=lambda r: r.primary)
> Excellent! That looks just like what I needed.

Note that there is the (probably little used) operator.attrgetter()
too, with that you can avoid the possibly slow lambda:
L.sort(key=attrgetter("primary")

operator.itemgetter(n) is when you have items that can be be accessed
by index.

Bye,
bearophile

--
http://mail.python.org/mailman/listinfo/python-list


chris.cavalaria at free

Jan 4, 2007, 2:21 AM

Post #9 of 12 (847 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

bearophileHUGS [at] lycos a écrit :
> Raymond Hettinger:
>> The simplest way is to take advantage of sort-stability and do
>> successive sorts. For example, to sort by a primary key ascending and
>> a secondary key decending:
>> L.sort(key=lambda r: r.secondary, reverse=True)
>> L.sort(key=lambda r: r.primary)
>
> That's probably the faster and simpler way.
> The following solution is probably slow, memory-hungry, and it's not
> tested much so it may be buggy too, but it shows my idea, and bugs can
> be fixed:
>
> class Inverter:
> def __init__(self, item, reversed=False):
> self.item = item
> self.reversed = reversed
> def __cmp__(self, other):
> if self.reversed:
> return cmp(other.item, self.item)
> else:
> return cmp(self.item, other.item)
>
> data = [[1, "a", "b"], [1, "b", "d"], [1, "d", "a"]]
> reverses = [True, False, False]
>
> print sorted(data, key=lambda subseq: map(Inverter, subseq, reverses))

Nice trick, but don't get too caught up using classes ;) Try that one
instead for much better performance :

class Inverter:
def __init__(self, item):
self.item = item
def __cmp__(self, other):
return cmp(other, self.item)

def invert_if(item, reversed=False):
if reversed:
return Inverter(item)
return item

data = [[1, "a", "b"], [1, "b", "d"], [1, "d", "a"]]
reverses = [True, False, False]

print sorted(data, key=lambda subseq: map(invert_, subseq, reverses))
--
http://mail.python.org/mailman/listinfo/python-list


horpner at yahoo

Jan 4, 2007, 8:23 AM

Post #10 of 12 (845 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

On 2007-01-03, dwelden <dwoogle [at] gmail> wrote:
> I have successfully used the sort lambda construct described in
> http://mail.python.org/pipermail/python-list/2006-April/377443.html.
> However, how do I take it one step further such that some
> values can be sorted ascending and others descending? Easy
> enough if the sort values are numeric (just negate the value),
> but what about text?
>
> Is the only option to define an external sorting function to
> loop through the list and perform the comparisons one value at
> a time?

Another trick is to factor the key application out of the sort.
This may be a good idea if when you want to minimize the number
of times your key function is called.

The idea is to mangle the list temporarily so you can use an
unkeyed sort, and then unmangle the sorted data. Here's a silly
example using a phone directory that's not stored in a format
that's easy to sort.

>>> a = [("Neil Cerutti", "8025552954"), ("Ted Smith", "8025552281"), ("Barny Fife", "8025551105")]
>>> b = [(" ".join(reversed(x.split())), y) for (x, y) in a]
>>> b
[('Cerutti Neil', '8025552954'), ('Smith Ted', '8025552281'), ('Fife Barny', '8025551105')]
>>> b.sort()
>>> b
[('Cerutti Neil', '8025552954'), ('Fife Barny', '8025551105'), ('Smith Ted', '8025552281')]
>>> a = [(" ".join(reversed(x.split())), y) for (x, y) in b]
>>> a
[('Neil Cerutti', '8025552954'), ('Barny Fife', '8025551105'), ('Ted Smith', '8025552281')]

--
Neil Cerutti
Eddie Robinson is about one word: winning and losing. --Eddie Robinson's agent
Paul Collier
--
http://mail.python.org/mailman/listinfo/python-list


__peter__ at web

Jan 4, 2007, 9:02 AM

Post #11 of 12 (842 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

Neil Cerutti wrote:

> Another trick is to factor the key application out of the sort.
> This may be a good idea if when you want to minimize the number
> of times your key function is called.
>
> The idea is to mangle the list temporarily so you can use an
> unkeyed sort, and then unmangle the sorted data. Here's a silly
> example using a phone directory that's not stored in a format
> that's easy to sort.

No need to jump through these hoops; list.sort(key=keyfunc) calls keyfunc()
exactly once per list item:

>>> from random import shuffle
>>> items = range(-5, 10)
>>> shuffle(items)
>>> count = 0
>>> def key(value):
... global count
... count += 1
... return abs(value)
...
>>> items.sort(key=key)
>>> count
15

Peter
--
http://mail.python.org/mailman/listinfo/python-list


horpner at yahoo

Jan 4, 2007, 10:13 AM

Post #12 of 12 (845 views)
Permalink
Re: Sorting on multiple values, some ascending, some descending [In reply to]

On 2007-01-04, Peter Otten <__peter__ [at] web> wrote:
> Neil Cerutti wrote:
>> Another trick is to factor the key application out of the
>> sort. This may be a good idea if when you want to minimize the
>> number of times your key function is called.
>>
>> The idea is to mangle the list temporarily so you can use an
>> unkeyed sort, and then unmangle the sorted data. Here's a
>> silly example using a phone directory that's not stored in a
>> format that's easy to sort.
>
> No need to jump through these hoops; list.sort(key=keyfunc)
> calls keyfunc() exactly once per list item:
>
>>>> from random import shuffle
>>>> items = range(-5, 10)
>>>> shuffle(items)
>>>> count = 0
>>>> def key(value):
> ... global count
> ... count += 1
> ... return abs(value)
> ...
>>>> items.sort(key=key)
>>>> count
> 15

Thanks for the correction! That's very useful information.

--
Neil Cerutti
--
http://mail.python.org/mailman/listinfo/python-list

Python python RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.