Well fine. I should have realised the question was just a pretense and that
there really never was any intention to consider the reactions, because
the answer is already fixed.
Antoon Pardon, 25.03.2011 10:21:
I don't think it is. It's just not as simple as "see, I have an
artificial use case here, so you *must* put the feature back in the
language".
Steven D'Aprano, 25.03.2011 06:46:
I think that touches it already. We have a "math" module, so why is there a
*builtin* for doing special math? How much code is there really that only
uses pow() and does not import "math"?
Stefan
pow() and math.pow() are different.
Well fine. I should have realised the question was just a pretense and
that there really never was any intention to consider the reactions,
because the answer is already fixed. Of course a key function can always
be written, it may just need a specific class to implement the specific
order. Likewise there is no reason to expect the order-functions to
preform worse when implemented in a class, rather than in a function.
Look we are provided with the cmp_to_key function. If something doesn't
work with that function or performs realy bad with that function, it
means either the function has a bug in it or something the function
relies on, has a bug in it. In either case you just fix the bug.
The reason Guido is considering re-introducing cmp is that somebody at
Google approached him with a use-case where a key-based sort did not
work. The use-case was that the user had masses of data, too much data
for the added overhead of Decorate-Sort-Undecorate (which is what key
does), but didn't care if it took a day or two to sort.
So there is at least one use-case for preferring slowly sorting with a
comparison function over key-based sorting. I asked if there any others.
It seems not.
Steven said:On Fri, 25 Mar 2011 10:21:35 +0100, Antoon Pardon wrote:
The reason Guido is considering re-introducing cmp is that somebody
at Google approached him with a use-case where a key-based sort did
not work. The use-case was that the user had masses of data, too
much data for the added overhead of Decorate-Sort-Undecorate (which
is what key does), but didn't care if it took a day or two to sort.
So there is at least one use-case for preferring slowly sorting
with a comparison function over key-based sorting. I asked if there
any others. It seems not.
1. You asked for a specific kind of use case. Antoon gave you a use
case, you told him that wasn't the kind of use case you were asking for,
then you turn around and say "I guess there are no use cases" (without
the mentioning qualification).
3. You evidently also overlooked the use-case example posted on Python-
dev that you followed up to.
2. I posted two use cases in this thread that fit your criteria, and you
followed up to that subthread so you most likely read them. Here they
are again so you won't overlook them this time:
"You have are given an obscure string collating function implented in a
C library you don't have the source to." (Fits your criterion "can't be
done with key=".)
"I'm sitting at an interactive session and I have a convenient cmp
function but no convenient key, and I care more about the four minutes
it'd take to whip up a clever key function or an adapter class than the
0.2 seconds I'd save to on sorting time." (Fits your criterion
"performs really badly when done so".)
Call me crazy, but you seem to be overlooking a lot of things in your
zeal to prove your point.
Westley Martínez, 25.03.2011 14:39:
I don't find that a good excuse for pow() being a builtin. Why not just
rename it to "math.powmod" instead?
And what point would that be?
+1 (modulo bikeshedding about the name). I've long thought that three-
argument pow belongs in the standard library rather than the core.
And then the existence of the ** operator obviates the need for two-
argument pow.
No, it means that the trade-offs made by cmp_to_key, or by sorting with a
key function, do not interact well with what you are trying to do.
[analgy of python lists, that double in size when full vs
memory management on a 8K device ]
So the question is, being completely general, as there any *real-world*
(not artificial, made-up) uses where sorting with a comparison function
works but a key function doesn't? I'm not limiting you to cases where you
have a shortage of memory but lots of time available. There may be other
design choices where key-based sorting sucks. We already know that some
people just prefer the look and feel of writing and using cmp functions.
Is there anything else?
So and if you find something like that, what stops the dev team from
saying that python is just not suited to deal with such a problem?
Asking for *real-world* uses is just how the python community smothers
requests.
Forcing people to use a key-function, will produce cases where python
will ask for more memory and take longer to sort, than allowing to
provide a cmp function.
This for the simple reason that for some
order-functions, the only way to write a key-function will be to write a
specific class, that will implement the order with the same kind of code
that otherwise would have been put in the cmp function,
making the trade off: memory use vs speed no longer a trade off.
If the existance alone of such cases isn't enough to reverse the
decision about the cmp-argument of the sort-method. My guess is that
nothing will.
The reason Guido is considering re-introducing cmp is that somebody at
Google approached him with a use-case where a key-based sort did not
work. The use-case was that the user had masses of data, too much data
for the added overhead of Decorate-Sort-Undecorate (which is what key
does), but didn't care if it took a day or two to sort.
So there is at least one use-case for preferring slowly sorting with a
comparison function over key-based sorting. I asked if there any others.
It seems not.
I tried to sort lists of 10000 elemens. Each element a tuple two items
that was to be sorted first according to the first item in ascending
order, then according to the second item in descending order. This was
done on python 2.6 so I had to write my own cmp_to_key function.
I then sorted these lists of 10000 elements a 1000 times with the
following methods.
from random import random, shuffle
from operator import itemgetter
from timeit import Timer
from functools import cmp_to_key
def make_data(n):
x = range(n)*2
y = range(n)*2
shuffle(x)
shuffle(y)
data = zip(x, y)
assert len(data) == 2*n
return data
# Sort according to the first item in ascending order, then by second item
# in descending order:
def cmp_func(t1, t2):
return cmp(t1[0], t2[0]) or cmp(t2[1], t1[1])
def key_func(t):
return (t[0], -t[1])
def sorter(d):
d = sorted(d, key=itemgetter(1), reverse=True)
return sorted(d, key=itemgetter(0))
# Check that all sort methods give the same result.
data = make_data(20)
assert sorted(data, cmp=cmp_func) == sorted(data, key=key_func) == \
sorter(data) == sorted(data, key=cmp_to_key(cmp_func))
data = make_data(5000)
assert len(data) == 10000
setup = "from __main__ import cmp_to_key, cmp_func, key_func, sorter,
data"
t1 = Timer("sorted(data, cmp=cmp_func)", setup)
t2 = Timer("sorted(data, key=key_func)", setup)
t3 = Timer("sorter(data)", setup)
t4 = Timer("sorted(data, key=cmp_to_key(cmp_func))", setup)
print "Comparison function:",
print min(t1.repeat(number=100, repeat=7))
print "Key function:",
print min(t2.repeat(number=100, repeat=7))
print "Double sort:",
print min(t3.repeat(number=100, repeat=7))
print "cmp_to_key:",
print min(t4.repeat(number=100, repeat=7))
[end code]Asking for *real-world* uses is just how the python community smothers
requests.
Should someone come with a use case, I expect the following
to happenr: One will go over the case with magnifying glasses in
search for any possible way in which it could be rewritten so as not
to need the cmp anyway. This will probably not be a big problem because
the person with the use case will probably have given a simplified example
to explain the overal picture. However most people responding will
ingnore the overal picture and focus on details that may very well work
on the simplified example but may not in the specific real-world case.
But since going over all details to argue the case will be too time
consuming, in the end the person with the use case will simply fail to
convince.
Forcing people to use a key-function, will produce cases where python
will ask for more memory and take longer to sort, than allowing to provide
a cmp function. This for the simple reason that for some order-functions,
the only way to write a key-function will be to write a specific class,
that will implement the order with the same kind of code that otherwise
would have been put in the cmp function, making the trade off: memory use
vs speed no longer a trade off.
If the existance alone of such cases isn't enough to reverse the decision
about the cmp-argument of the sort-method. My guess is that nothing will.
Thank you for spending the time to get some hard data, but I can't
replicate your results since you haven't shown your code. Rather than
attempt to guess what you did and duplicate it, I instead came up with my
own timing measurements. Results are shown here, my code follows below:
[steve@sylar ~]$ python2.7 sort_test.py
Comparison function: 12.1256039143
Key function: 3.51603388786
Double sort: 2.33165812492
cmp_to_key: 28.1129128933
By far the best result comes from two calls to sort. Not far off is the
key function solution. (Admittedly, coming up with a key function for non-
numeric data would be challenging.) The comparison function, and the
cmp_to_key solution, are clearly *much* slower.
Thank you for spending the time to get some hard data, but I can't
replicate your results since you haven't shown your code. Rather than
attempt to guess what you did and duplicate it, I instead came up with my
own timing measurements. Results are shown here, my code follows below:
[steve@sylar ~]$ python2.7 sort_test.py
Comparison function: 12.1256039143
Key function: 3.51603388786
Double sort: 2.33165812492
cmp_to_key: 28.1129128933
By far the best result comes from two calls to sort. Not far off is the
key function solution. (Admittedly, coming up with a key function for non-
numeric data would be challenging.) The comparison function, and the
cmp_to_key solution, are clearly *much* slower.
Steven D'Aprano said:There are lots of problems that Python is not well-suited for.
It is not well-suited for writing the driver to a graphics card.
It is not well-suited to calculating pi to a trillion decimal places.
...
99% of requests should be smothered. That is a *good thing*.
More memory yes; take longer to sort, almost certainly not (except,
perhaps, for a very narrow window where the addition of a key causes
data.sort(key=functools.cmp_to_key(myfunc))
which is a little longer to type, and uses a little more memory, but
otherwise is no worse than using cmp.
[...]Forcing people to use a key-function, will produce cases where python
will ask for more memory and take longer to sort, than allowing to
provide a cmp function.
More memory yes; take longer to sort, almost certainly not (except,
perhaps, for a very narrow window where the addition of a key causes the
application to page out to virtual memory, but a comparison function
wouldn't -- and even then, the key function might still be faster).
But we've already covered the "more memory" angle to death. We already
understand that. This is why I have asked if there are any *other* use-
cases for a comparison function.
Dan Stromberg has suggested that another use-case would be lazy-
comparisons, where you might not be able to generate a single key
cheaply, but you can perform a comparison lazily.
This for the simple reason that for some
order-functions, the only way to write a key-function will be to write a
specific class, that will implement the order with the same kind of code
that otherwise would have been put in the cmp function,
There is a recipe for that on ActiveState's website, google for
cmp_to_key. That recipe has been added to Python's standard library for
version 3.2. Please stop flogging that dead horse.
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.