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

# 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?

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
point me to the part of the docs that I missed.)

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.

>
> 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
> point me to the part of the docs that I missed.)

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

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

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~

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

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.

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

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

kj
Guest
Posts: n/a

 10-01-2009
In <(E-Mail Removed)> Raymond Hettinger <(E-Mail Removed)> writes:

<snip>

>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