Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Perl Misc (http://www.velocityreviews.com/forums/f67-perl-misc.html)
-   -   Q: sort's key and cmp parameters (http://www.velocityreviews.com/forums/t911487-q-sorts-key-and-cmp-parameters.html)

 gb345 10-01-2009 05:04 PM

Q: sort's key and cmp parameters

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.)

 kj 10-01-2009 05:05 PM

Re: Q: sort's key and cmp parameters

My apologies!

Please disregard this post. I sent it to the wrong newsgroup.

G.

>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