Q: sort's key and cmp parameters
Peter Otten
__peter__ at web.de
Thu Oct 1 19:51:02 CEST 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.)
More information about the Python-list
mailing list