Q: sort's key and cmp parameters
Raymond Hettinger
python at rcn.com
Thu Oct 1 16:54:35 EDT 2009
On Oct 1, 10:08 am, kj <no.em... at please.post> 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
More information about the Python-list
mailing list