Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Q: sort's key and cmp parameters

Reply
Thread Tools

Q: sort's key and cmp parameters

 
 
kj
Guest
Posts: n/a
 
      10-01-2009


Challenge: to come up with a sorting task that cannot be achieved
by passing to the sort method (or sorted function) suitable values
for its key and reverse parameters, but instead *require* giving
a value to its cmp parameter.

For example,

from random import random
scrambled = some_list.sort(cmp=lambda x, y: cmp(random(), 0.5))

can be achieved (to a very good approximation at least) with

scrambled = some_list.sort(key=lambda x: random())

Is there a real-life sorting task that requires (or is far more
efficient with) cmp and can't be easily achieved with key and
reverse?

Many thanks in advance,

G.

P.S. I guess that, if sort is going to produce a non-trivial,
*consistent* order, a function CMP passed as the value of its cmp
parameter must satisfy the following properties:

0. CMP(x, y) must be non-zero for some elements x, y of the list;
1. anti-symmetry: sign(CMP(x, y)) must be equal to -sign(CMP(y, x));
2. transitivity: if sign(CMP(x, y)) equals sign(CMP(y, z)), then
sign(CMP(x, z)) must be equal to sign(CMP(x, y)).

In (1) and (2), sign() stands for the function

-1 if x < 0
sign(x) = 0 if x == 0
1 if x > 0

I suppose that all bets are off if these properties are not satisfied,
though the documentation does not make this entirely clear, as far
as I can tell. (If I'm wrong about this alleged omission, please
point me to the part of the docs that I missed.)
 
Reply With Quote
 
 
 
 
Peter Otten
Guest
Posts: n/a
 
      10-01-2009
kj wrote:

> Challenge: to come up with a sorting task that cannot be achieved
> by passing to the sort method (or sorted function) suitable values
> for its key and reverse parameters, but instead *require* giving
> a value to its cmp parameter.
>
> For example,
>
> from random import random
> scrambled = some_list.sort(cmp=lambda x, y: cmp(random(), 0.5))


The above violates the transitivity requirement as stated below. The result
will have a bias.

> can be achieved (to a very good approximation at least) with
>
> scrambled = some_list.sort(key=lambda x: random())
>
> Is there a real-life sorting task that requires (or is far more
> efficient with) cmp and can't be easily achieved with key and
> reverse?


The core developers don't think there is one. list.sort() no longer supports
the cmp parameter in 3.x.

> Many thanks in advance,
>
> G.
>
> P.S. I guess that, if sort is going to produce a non-trivial,
> *consistent* order, a function CMP passed as the value of its cmp
> parameter must satisfy the following properties:
>
> 0. CMP(x, y) must be non-zero for some elements x, y of the list;
> 1. anti-symmetry: sign(CMP(x, y)) must be equal to -sign(CMP(y, x));
> 2. transitivity: if sign(CMP(x, y)) equals sign(CMP(y, z)), then
> sign(CMP(x, z)) must be equal to sign(CMP(x, y)).
>
> In (1) and (2), sign() stands for the function
>
> -1 if x < 0
> sign(x) = 0 if x == 0
> 1 if x > 0
>
> I suppose that all bets are off if these properties are not satisfied,
> though the documentation does not make this entirely clear, as far
> as I can tell. (If I'm wrong about this alleged omission, please
> point me to the part of the docs that I missed.)



 
Reply With Quote
 
 
 
 
Laszlo Nagy
Guest
Posts: n/a
 
      10-01-2009
Is this a homework?

> Challenge: to come up with a sorting task that cannot be achieved
> by passing to the sort method (or sorted function) suitable values
> for its key and reverse parameters, but instead *require* giving
> a value to its cmp parameter.
>

Let me put up this question: how do you define the difference between an
object to be sorted in the list, and the passed "suitable value" that is
used for finding the position for the object in the list. If the only
difference is that they need to be different Python objects, then you
can always use [x] instead of x. This value is perfectly suitable.

If you could give us somewhat stronger requirements regarding keys and
objects, we may give you a different answer.

Best,

Laszlo


 
Reply With Quote
 
Laszlo Nagy
Guest
Posts: n/a
 
      10-01-2009

>> can be achieved (to a very good approximation at least) with
>>
>> scrambled = some_list.sort(key=lambda x: random())
>>
>> Is there a real-life sorting task that requires (or is far more
>> efficient with) cmp and can't be easily achieved with key and
>> reverse?
>>

>
> The core developers don't think there is one. list.sort() no longer supports
> the cmp parameter in 3.x.
>

LOL

BTW if you really want to sort a list then you can. Using keys or
values, it doesn't matter. The op's question has no practical usage.
REALLY looks like a homework.

L

 
Reply With Quote
 
Ethan Furman
Guest
Posts: n/a
 
      10-01-2009
Laszlo Nagy wrote:
>
>>> can be achieved (to a very good approximation at least) with
>>>
>>> scrambled = some_list.sort(key=lambda x: random())
>>>
>>> Is there a real-life sorting task that requires (or is far more
>>> efficient with) cmp and can't be easily achieved with key and
>>> reverse?
>>>

>>
>>
>> The core developers don't think there is one. list.sort() no longer
>> supports the cmp parameter in 3.x.
>>

>
> LOL
>
> BTW if you really want to sort a list then you can. Using keys or
> values, it doesn't matter. The op's question has no practical usage.
> REALLY looks like a homework.
>
> L
>


If it is, it's one he's contemplating giving his students.

~Ethan~
 
Reply With Quote
 
Carsten Haese
Guest
Posts: n/a
 
      10-01-2009
kj wrote:
>
> Challenge: to come up with a sorting task that cannot be achieved
> by passing to the sort method (or sorted function) suitable values
> for its key and reverse parameters, but instead *require* giving
> a value to its cmp parameter.


Such a task can't exist, because any arbitrary comparison function can
be transformed into a key function. The idea behind the transformation
is to construct wrapper objects that can compare themselves to other
wrapper objects by invoking the given comparison function on their
wrapped originals.

Google for "Hettinger cmp2key" if you want to see the code that does
this transformation.

HTH,

--
Carsten Haese
http://informixdb.sourceforge.net

 
Reply With Quote
 
Paul Rubin
Guest
Posts: n/a
 
      10-01-2009
kj <(E-Mail Removed)> writes:
> Is there a real-life sorting task that requires (or is far more
> efficient with) cmp and can't be easily achieved with key and
> reverse?


Yes, think of sorting tree structures where you have to recursively
compare them til you find an unequal pair of nodes. To sort with
key=... you have to wrap a class instance around each tree, with
special comparison methods. Blecch.
 
Reply With Quote
 
Bearophile
Guest
Posts: n/a
 
      10-01-2009
Paul Rubin:

> Yes, think of sorting tree structures where you have to recursively
> compare them til you find an unequal pair of nodes.


That's cute. In what situations do you have to perform such kind of
sort?

Bye,
bearophile
 
Reply With Quote
 
Raymond Hettinger
Guest
Posts: n/a
 
      10-01-2009
On Oct 1, 10:08*am, kj <(E-Mail Removed)> wrote:
> Challenge: to come up with a sorting task that cannot be achieved
> by passing to the sort method (or sorted function) suitable values
> for its key and reverse parameters, but instead *require* giving
> a value to its cmp parameter.


If you're assuming a consistent sort-order (transitivity, not
evolving over time, etc), then the cmp method and key method
are mathematically equivalent (you could always do a compare
sort first, record the order produced, and assign the position
number as a key function):

# constructive proof of the existence of a key function
# corresponding to a given cmp function
tmplist = sorted(s, cmp=mycmp)
pos = dict(zip(map(id, tmplist), range(len(tmplist))))
result = sorted(s, key=lambda x: pos[id(x)])
assert tmplist == result

Given equivalence, what is really at stake is convenience.

If you're starting point is a cmp function (for instance,
asking a dating service member whether they prefer
mate x to mate y), then having to convert to a key function
can be inconvenient.

If you need to sort by an ascending primary key and a descending
secondary key, you may find it easiest to sort in two passes
(taking advantage of guaranteed sort stability):

sorted(s, key=secondary, reversed=True)
sorted(s, key=primary)

With a cmp function, the above could be achieved in a single pass:

def mycmp(x, y):
p = cmp(primary(a), primary(b))
return p if p else cmp(secondary(b), secondary(a))

sorted(s, cmp=mycmp)

Also, as Paul pointed-out, there are some structures such as tree
comparisons that may be challenging to express directly as a key
function. As Carsten pointed-out, the cmp2key function allows
cmp functions to trivially (though indirectly) be recast as key
functions.

All that being said, for many everyday uses, a key function is
simpler to write and faster to run than a cmp function approach.


Raymond
 
Reply With Quote
 
kj
Guest
Posts: n/a
 
      10-01-2009
In <(E-Mail Removed)> Raymond Hettinger <(E-Mail Removed)> writes:

<snip>

Thanks for an extremely helpful reply!

>If you need to sort by an ascending primary key and a descending
>secondary key, you may find it easiest to sort in two passes
>(taking advantage of guaranteed sort stability):


> sorted(s, key=secondary, reversed=3DTrue)
> sorted(s, key=primary)


In the special case where the value returned by secondary is
numeric, I suppose one could do this in one go with

sorted(s, key=lambda x: (primary(x), -secondary(x)))

....but I can't think of a way to generalize this...

kj
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Q: sort's key and cmp parameters gb345 Perl Misc 1 10-01-2009 05:05 PM
Replacing cmp with key for sorting George Sakkis Python 8 11-03-2008 09:40 PM
Using s.sort([cmp[, key[, reverse]]]) to sort a list of objects based on a attribute cjt22@bath.ac.uk Python 7 09-10-2007 11:10 AM
no cmp field defined in cmp ejb Andrea Sansottera Java 0 07-16-2004 02:24 PM
CMR/CMP and Compound Primary Key Damir Mikoc Java 1 07-04-2003 03:27 AM



Advertisments